把我上學(xué)時(shí)候在csdn上的筆記搬過來了

經(jīng)典的約瑟夫問題

題目：假設(shè)下標(biāo)從0開始，0，1，2 .. n-1共n個(gè)人，從1開始報(bào)數(shù)，報(bào)到m則此人從環(huán)中退出，下一個(gè)人重新從1開始報(bào)數(shù)，以此類推，問最后剩下的一個(gè)人的編號(hào)是多少？

分析：
看到這個(gè)題目，我想最簡(jiǎn)單的思路就是寫個(gè)程序模擬這個(gè)過程，最終產(chǎn)生結(jié)果。
首先我們需要一個(gè)長(zhǎng)度為n的數(shù)組，每個(gè)位置有兩個(gè)狀態(tài)分別表示該處的人是否退出，可以選擇boolean型。需要一個(gè)變量i來移動(dòng)反復(fù)遍歷數(shù)組，變量s來計(jì)數(shù)是否達(dá)到m，還需要一個(gè)變量count來計(jì)數(shù)環(huán)內(nèi)到底還有幾個(gè)人，以終止遍歷。

算法如下：

public static int yueSe(int n, int m) {
        //true 表示退出 ，false表示沒有退出
        boolean[] arr = new boolean[n];
        int i = 0;
        int s = 1;
        int count = n;
        while (count > 0) {
            i++;
            if (i > n - 1) {
                i = 0;
            }
            if (!arr[i]) {
                s++;
                if (s == m) {
                    s = 0;
                    arr[i] = true;
                    System.out.print(i+" ");
                    count--;
                }
            }
        }
        return i;
    }

但是這種算法我們分析出它每刪除一個(gè)元素循環(huán)就要進(jìn)行m次，那么總的時(shí)間復(fù)雜度就是O(mn) ，并不理想。題目只是要求我們求出最后一個(gè)人的編號(hào)，我們可以另辟蹊徑。

我們知道第一個(gè)人（編號(hào)一定是(m-1)%n) 出列之后，剩下的n-1個(gè)人組成了一個(gè)新的約瑟夫環(huán)（以編號(hào)為k=m mod n的人開始）：
k ，k+1， k+2 … n-2, n-1, 0, 1, 2 , … ，k-2
我們把他們的編號(hào)做一下轉(zhuǎn)換：
k –> 0
k+1 –> 1
k+2 –> 2
…
…
k-2 –> n-2

那么變換之后問題變成了和原問題一樣的問題只是規(guī)模變成了n-1，照這個(gè)思路下去最終數(shù)組長(zhǎng)度變?yōu)?，轉(zhuǎn)換之后的角標(biāo)為0；這時(shí)候只要我們倒著推0轉(zhuǎn)換前的角標(biāo)為x，x轉(zhuǎn)換前的角標(biāo)為x’,x’轉(zhuǎn)換前的角標(biāo)為x”，有靈感了沒有這么遞推的話只要我們遞歸n-1次即可得到我們想要的角標(biāo)。

關(guān)鍵是這個(gè)遞推公式是什么呢？
我們可以先看正著遞推的思路，假設(shè)當(dāng)前角標(biāo)為x那么改變后的角標(biāo)y為
y=(x+n-k)%n ,其中k=m
那么倒推得公式即為
x=(y+k)%n ,這里對(duì)于一般情況我們要理解n是刪除前的數(shù)組長(zhǎng)度。
算法如下：

public static int yueSe2(int n,int m){
        int f=0;
        for(int i=2;i<=n;i++){
            f=(f+m)%i;
        }
        return f;
    }

網(wǎng)易筆試題（約瑟夫問題變形）

題目：小明同學(xué)把1到n這n個(gè)數(shù)字按照一定的順序放入了一個(gè)隊(duì)列Q中。現(xiàn)在他對(duì)隊(duì)列Q執(zhí)行了如下程序：

while(!Q.empty())              //隊(duì)列不空，執(zhí)行循環(huán)

{

    int x=Q.front();            //取出當(dāng)前隊(duì)頭的值x

    Q.pop();                 //彈出當(dāng)前隊(duì)頭

    Q.push(x);               //把x放入隊(duì)尾

    x = Q.front();              //取出這時(shí)候隊(duì)頭的值

    printf("%d\n",x);          //輸出x

    Q.pop();                 //彈出這時(shí)候的隊(duì)頭

}

做取出隊(duì)頭的值操作的時(shí)候，并不彈出當(dāng)前隊(duì)頭。
小明同學(xué)發(fā)現(xiàn)，這段程序恰好按順序輸出了1,2,3,…,n?，F(xiàn)在小明想讓你構(gòu)造出原始的隊(duì)列，你能做到嗎？

這個(gè)題目雖然是取出一個(gè)放到隊(duì)列尾，刪除接下來一個(gè)，但是仔細(xì)一想其實(shí)這個(gè)問題和約瑟夫問題是一樣的，而且m=2。但是這個(gè)題是要確定所有位置的出場(chǎng)順序，目前博主沒有找到O(n)的解法，不多做分析啦，相信大家一看就懂，代碼如下

public static void answer(int n) {
        int[] arr = new int[n];
        int count = 0;
        int i = 0;
        int s = 1;
        while (count < n) {
            i++;
            if (i > n - 1) {
                i = 0;
            }
            if (arr[i] == 0) {
                s++;
            }
            if (s == 2) {
                s = 0;
                count++;
                arr[i] = count;
            }
        }
        for (int j = 0; j < n - 1; j++) {
            System.out.print(arr[j] + " ");
        }
        System.out.print(arr[n - 1]);
    }