约瑟夫问题的问题来历？利用C++解决约瑟夫问题

约瑟夫问题的问题来历

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个**和15 个非**在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非**。*问题分析与算法设计约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。题目中30个人围成一圈，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。

利用C++解决约瑟夫问题

这里补充一下约瑟夫问题的描述：N个人围成一圈，从第一个开始报数，数到M的人出队，然后他的下一位继续从1开始报数，数到M的出队，如此循环直到剩下一个人，求最后剩下的那个人最初是队伍中的第几位。

解决这道题可以采用模拟报数的方法，建立一个大小为N的数组，数组的第N个元素表示第N个人是否还在队伍中，首先将每个元素都置为1，表示全员都在队伍中。如果第N个人出队，则将第N个元素置为0。

模拟报数可以使用一个累加计数器，用它表示这轮报数已有多少人报数，然后循环访问每个人，若其在队伍中，则将计数器+1，如果累加到M，则这个人出队。如此循环，直到N-1个人出队，仅剩1人。

最后遍历一下那个数组，找到还在队伍中的人就可以。

代码如下：

#include 《iostream》using namespace std;int main(){int m, n, i, s = 0, rem;//s为计数器, rem为剩余人数int *a;cout 《《 "输入总人数和出队的序号：" ;cin 》》 n 》》 m;rem = n;a = new int;for (i = 0; i 《 n; i++)a = 1;i = 0;while (rem 》 1){s += a;if (s == m)//第i个人出队，重置累加计数器{s = 0;rem--;a = 0;}i++;i %= n;}for (i = 0; i 《 n; i++)if (a){cout 《《 "剩下的人为：" 《《 i 《《 endl;break;}delete a;return 0;}

约瑟夫问题

这是17世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事：15个**和15 个非**在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非**。 *问题分析与算法设计 约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。 题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。一般形式约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。 假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。 C++代码示例: #include《iostream》 using namespace std; void main() { int n,m,a,k,i,j,num; //计数器是从1开始的,所以100个人用101 cout《《"请输入参加游戏的玩家人数(不超过100人):"; cin》》n; cout《《"----------------------------------------"《《endl; if(n》100) { cout《《"玩家太多,请重新**此程序!"《《endl; return; } cout《《"输入游戏中要玩的数字:"; cin》》m; cout《《"----------------------------------------"《《endl; for(i=1;i《=n;i++) { a【i】=1;//注意百度百科里不让使用ASCII里的方括号，这里是中文字符集里的方括号， } j=0; k=0; for(i=1;i《=n+1;i++){ if(a【i】==1){ j=j+a【i】; if(j==m) { j=0; a【i】=0; k++; } if(k==n){ num=i; break; } } if(i==n+1) i=0; } cout《《"最后获胜的玩家是第 "《《num《《" 号玩家!"《《endl; cout《《"----------------------------------------"《《endl; } 写完密码约瑟夫就想到原来看到约瑟夫问题的一个数学解法 很巧妙很简单 不过只能推出最后一个出列的人 无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。 为了讨论方便，先把问题稍微改变一下，并不影响原意： 问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。 我们知道第一个人(编号一定是m mod n-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 k-1 --》 n-1 变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x’=(x+k) mod n 如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式： 令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f 递推公式 f=0; f=(f+m) mod i; (i》1) 有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f+1 由于是逐级递推，不需要保存每个f，程序也是异常简单： c++ #include 《stdio.h》 int main() { int n, m, i, s=0; printf ("N M = "); scanf("%d%d", &n, &m); for (i=2; i《=n; i++) s=(s+m)%i; printf ("The winner is %d\n", s+1); } pascal var n,m,i,s:integer; begin write(’N M =’); read(n,m); for i:=2 to n do s:=(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) 有了思路，再加上高精度就可以了。我写的代码比较猥琐，因为是先把上面的思路敲进去，再写过程，又把一些简单的过程合到主程序中了，所以有点乱，也有点猥琐。起提供思路的作用还是完全可以的吧~~~ var a,b,c:arrayof integer; la,lb,lc,i:integer; s:string; procedure incc; var i:integer; begin for i:=1 to 105 do c:=c+b; for i:=1 to 104 do if c》9 then begin c:=c+c div 10; c:=c mod 10; end; end; function cxiaoa:boolean; var i:integer; begin cxiaoa:=false; for i:=105 downto 1 do if c《a then begin cxiaoa:=true;break;end else if c》a then break; end; procedure doubleb; var i:integer; begin for i:=1 to 105 do b:=b*2; for i:=1 to 104 do if b》9 then begin b:=b+b div 10; b:=b mod 10; end; end; procedure decc; var i,j:integer; begin for i:=1 to 104 do if c》=b then c:=c-b else begin j:=i+1; while c=0 do inc(j); while j》i do begin c-1; c+10; dec(j); end; c:=c-b; end; end; procedure fua; var i:integer; begin for i:=1 to 104 do if a》c then a:=a-c else begin a:=a-1; a:=a+10; a:=a-c; end; end; procedure outit; var i,j:integer; begin for i:=1 to 105 do a:=a*2; for i:=1 to 104 do if a》9 then begin a:=a+a div 10; a:=a mod 10; end; if a-1 else begin j:=2; while a=0 do inc(j); while j》1 do begin a-1; a+10; dec(j); end; a-1; end; for i:=105 downto 1 do if a》0 then begin j:=i;break;end; for i:=j downto 1 do write(a); end; begin readln(s); la:=length(s); for i:=la downto 1 do a:=ord(s)-ord(’0’); b:=1; c:=1; while cxiaoa do begin doubleb; incc; end; decc; fua; outit; end.笔算解决约瑟夫问题 在M比较小的时候 ，可以用笔算的方法求解， M=2 即N个人围成一圈，1，2，1，2的报数，报到2就去死，直到只剩下一个人为止。 当N=2^k的时候，第一个报数的人就是最后一个死的， 对于任意的自然数N 都可以表示为N=2^k+t,其中t《n/2 于是当有t个人去死的时候，就只剩下2^k个人 ，这2^k个人中第一个报数的就是最后去死的。这2^k个人中第一个报数的人就是2t+1 于是就求出了当M=2时约瑟夫问题的解： 求出不大于N的最大的2的整数次幂，记为2^k，最后一个去死的人是2(N-2^k)+1 M=3 即N个人围成一圈，1，2，3，1，2，3的报数，报到3就去死，直到只剩下一个人为止。 此时要比M=2时要复杂的多 我们以N=2009为例计算 N=2009，M=3时最后被杀死的人记为F(2009,3),或者可以简单的记为F(2009) 假设现在还剩下n个人，则下一轮将杀死个人 设这n个人为a1,a2,...,a(n-1),an 从a1开始报数，一圈之后，剩下的人为a1,a2,a4,a5,...a(n-n mod 3-1),a(n-n mod 3+1),..,an 于是可得： 1、这一轮中最后一个死的是a(n-n mod 3),下一轮第一个报数的是a(n-n mod 3+1) 2、若3|n,则最后死的人为新一轮的第F(n-)个人 若n mod 3≠0 且f(n-)-（n mod 3）人 若n mod 3≠0 且f(n-)-（n mod 3）人 3、新一轮第k个人对应原来的第 3*+(k-1)mod 2+1个人 综合1，2，3可得： F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4，F(6)=1， 当f(n-+(k-1)mod 2+1 当f(n-+(k-1)mod 2+1 这种算法需要计算 次 这个数不大于22，可以用笔算了 于是： 第一圈，将杀死669个人，这一圈最后一个被杀死的人是2007，还剩下1340个人， 第二圈，杀死446人，还剩下894人 第三圈，杀死298人，还剩下596人 第四圈，杀死198人，还剩下398人 第五圈，杀死132人，还剩下266人 第六圈，杀死88人，还剩下178人 第七圈，杀死59人，还剩下119人 第八圈，杀死39人，还剩下80人 第九圈，杀死26人，还剩下54人 第十圈，杀死18人，还剩36人 十一圈，杀死12人，还剩24人 十二圈，杀死8人，还剩16人 十三圈，杀死5人，还剩11人 十四圈，杀死3人，还剩8人 十五圈，杀死2人，还剩6人 F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4，F(6)=1， 然后逆推回去 F(8)=7 F(11)=7 F(16)=8 f(24)=11 f(36)=16 f(54)=23 f(80)=31 f(119)=43 f(178)=62 f(266)=89 f(398)=130 F(596)=191 F(894)=286 F(1340)=425 F(2009

C语言：约瑟夫问题.

24 1:0 2:0 3:0 4:0 5:1 6:1 7:1 8:1 9:1 10:0 11:0 12:1 13:0 14:0 15:016:1 17:0 18:1 19:1 20:0 21:0 22:1 23:1 24:1 25:0 26:1 27:1 28:0 29:0 30:1(1为非**，0为**)Press any key to continue#include《iostream》using namespace std;void main() { int i, j, k = 1, a; for(i = 0; i 《= 30; i++) a = 0; for(i = 1; i 《= 15; i++){ for(j = 1; j 《= 9; j++, k++) while(a) if(++k 》 30) k = 1; a = 1; } printf("%d\n", k); for(i = 1; i 《= 30; i++) { printf("%2d:%d ", i, a); if(!(i%15)) putchar(’\n’); } printf("(1为非**，0为**)\n"); }/* n, s, m = 30 1 9 出圈次序: 9 18 27 6 16 26 7 19 30 12 24 8 22 5 23 11 29 17 10 2 28 25 1 4 15 13 14 3 20 21Press any key to continue*/