約瑟夫問題是個有名的問題：N個人圍成壹圈，從第壹個開始報數，第M個將被殺掉，最後剩下壹個，其余人都將被殺掉。例如N=6，M=5，被殺掉的順序是：5，4，6，2，3，1。
分析：
（1）由於對於每個人只有死和活兩種狀態，因此可以用布朗型數組標記每個人的狀態，可用true表示死，false表示活。
（2）開始時每個人都是活的，所以數組初值全部賦為false。
（3）模擬殺人過程，直到所有人都被殺死為止。
pascal代碼
var a:array [1..20] of integer;
n,m,i,j,k,n1,m1:integer;
begin
readln(m,n);
for i:=1 to m do
a[i]:=i;
m1:=m;
n1:=1;
while m1>0 do
begin
j:=(n+n1-1-1) mod m1 +1;
n1:=j;
m1:=m1-1;
writeln(a[j]);
for k:=j to m1 do
a[k]:=a[k+1];
end;
end.
C++代碼： #include<iostream>usingnamespacestd;main(){bool?a[101]={0};intn,m,i,f=0,t=0,s=0;cin>>n>>m;do{++t;//逐個枚舉圈中的所有位置if(t>n)t=1;//數組模擬環狀，最後壹個與第壹個相連if(!a[t])s++;//第t個位置上有人則報數if(s==m)//當前報的數是m{s=0;//計數器清零cout<<t<<'';//輸出被殺人編號a[t]=1;//此處人已死，設置為空f++;//死亡人數+1}}while(f!=n);//直到所有人都被殺死為止}無論是用鏈表實現還是用數組實現都有壹個***同點：要模擬整個遊戲過程，不僅程序寫起來比較煩，而且時間復雜度高達O(nm），當n，m非常大（例如上百萬，上千萬）的時候，幾乎是沒有辦法在短時間內出結果的。我們註意到原問題僅僅是要求出最後的勝利者的序號，而不是要讀者模擬整個過程。因此如果要追求效率，就要打破常規，實施壹點數學策略。
為了討論方便，先把問題稍微改變壹下，並不影響原意：
問題描述：n個人（編號0~(n-1）），從0開始報數，報到（m-1）的退出，剩下的人繼續從0開始報數。求勝利者的編號。
我們知道第壹個人（編號壹定是（m-1）) 出列之後，剩下的n-1個人組成了壹個新的約瑟夫環（以編號為k=m mod n的人開始）：
k k+1 k+2 ... n-2,n-1,0,1,2,... k-2
並且從k開始報0。
我們把他們的編號做壹下轉換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
變換後就完完全全成為了（n-1）個人報數的子問題，假如我們知道這個子問題的解：例如x是最終的勝利者，那麽根據上面這個表把這個x變回去不剛好就是n個人情況的解嗎？！！變回去的公式很簡單，相信大家都可以推出來：x'=(x+k) mod n
如何知道（n-1）個人報數的問題的解？對，只要知道（n-2）個人的解就行了。（n-2）個人的解呢？當然是先求（n-3）的情況 ---- 這顯然就是壹個倒推問題！好了，思路出來了，下面寫遞推公式：
令f表示i個人玩遊戲報m退出最後勝利者的編號，最後的結果自然是f[n]
遞推公式
f[1]=0;
f=(f+m) mod i; (i>1）
有了這個公式，我們要做的就是從1-n順序算出f的數值，最後結果是f[n]。因為實際生活中編號總是從1開始，我們輸出f[n]+1
由於是逐級遞推，不需要保存每個f，程序也是異常簡單：
c++ #include?<iostream>using?namespace?std;const?int?m?=?3;int?main(){int?n,?f?=?0;cin?>>?n;for?(int?i?=?1;?i?<=?n;?i++)?f?=?(f?+?m)?%?i;cout?<<?f?+?1?<<?endl;}pascal var?n,m,i,s:integer;beginwrite('N?M?=');read(n,m);for?i:=2?to?n?dos:=(s+m)?mod?i;writeln('The?winner?is?',s+1）;end.這個算法的時間復雜度為O(n），相對於模擬算法已經有了很大的提高。算n，m等於壹百萬，壹千萬的情況不是問題了。可見，適當地運用數學策略，不僅可以讓編程變得簡單，而且往往會成倍地提高算法執行效率。
約瑟夫問題10e100版（from vijios)
描述 Description
n個人排成壹圈。從某個人開始，按順時針方向依次編號。從編號為1的人開始順時針“壹二壹”報數，報到2的人退出圈子。這樣不斷循環下去，圈子裏的人將不斷減少。由於人的個數是有限的，因此最終會剩下壹個人。試問最後剩下的人最開始的編號。
輸入格式 Input Format
壹個正整數n，表示人的個數。輸入數據保證數字n不超過100位。
輸出格式 Output Format
壹個正整數。它表示經過“壹二壹”報數後最後剩下的人的編號。
樣例輸入 Sample Input
9
樣例輸出 Sample Output
3
時間限制 Time Limitation
各個測試點1s
註釋 Hint
樣例說明
當n=9時，退出圈子的人的編號依次為：
2 4 6 8 1 5 9 7
最後剩下的人編號為3
初見這道題，可能會想到模擬。可是數據實在太大啦！！
我們先拿手來算，可知n分別為1，2，3，4，5，6，7，8...時的結果是1，1，3，1，3，5，7，1...
有如下規律：從1到下壹個1為壹組，每壹組中都是從1開始遞增的奇數，且每組元素的個數分別為1，2，4...
這樣就好弄了！！
大體思路如下：
①read(a)
②b:=1,c:=1{b為某壹組的元素個數，c為累計所加到的數}
③while c<a do (b:=b*2,c:=b+c){超過目標時停止加數}
⑥c:=c-b{退到前壹組}
⑦x:=a-c{算出目標為所在組的第幾個元素}
⑧ans:=x*2-1{求出該元素}
⑨write(ans)
有了思路，再加上高精度就可以了。我寫的代碼比較猥瑣，因為是先把上面的思路敲進去，再寫過程，又把壹些簡單的過程合到主程序中了，所以有點亂，也有點猥瑣。起提供思路的作用還是完全可以的吧~~~ vara,b,c:array[1..105]ofinteger;la,lb,lc,i:integer;s:string;procedureincc;vari:integer;beginfori:=1to105doc:=c+b;fori:=1to104doifc>9thenbeginc:=c+cdiv10;c:=cmod10;end;end;functioncxiaoa:boolean;vari:integer;begincxiaoa:=false;fori:=105downto1doifc<athenbegincxiaoa:=true;break;endelseifc>athenbreak;end;proceduredoubleb;vari:integer;beginfori:=1to105dob:=b*2;fori:=1to104doifb>9thenbeginb:=b+bdiv10;b:=bmod10;end;end;proceduredecc;vari,j:integer;beginfori:=1to104doifc>=bthenc:=c-belsebeginj:=i+1;whilec[j]=0doinc(j);whilej>idobeginc[j]:=c[j]-1;c[j-1]:=c[j-1]+10;dec(j);end;c:=c-b;end;end;procedurefua;vari:integer;beginfori:=1to104doifa>cthena:=a-celsebegina:=a-1;a:=a+10;a:=a-c;end;end;procedureoutit;vari,j:integer;beginfori:=1to105doa:=a*2;fori:=1to104doifa>9thenbegina:=a+adiv10;a:=amod10;end;ifa[1]>0thena[1]:=a[1]-1elsebeginj:=2;whilea[j]=0doinc(j);whilej>1dobegina[j]:=a[j]-1;a[j-1]:=a[j-1]+10;dec(j);end;a[1]:=a[1]-1;end;fori:=105downto1doifa>0thenbeginj:=i;break;end;fori:=jdownto1dowrite(a);end;beginreadln(s);la:=length(s);fori:=ladownto1doa:=ord(s[la+1-i])-ord('0');b[1]:=1;c[1]:=1;whilecxiaoadobegindoubleb;incc;end;decc;fua;outit;end.