约瑟夫问题的一般形式

约瑟夫问题是个有名的问题：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.