约瑟夫问题（Josephus problem）又称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，约瑟夫问题类似问题又称为约瑟夫环、“丢手绢问题”。约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。
问题来源
据说著名犹太历史学家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个人被扔下海为止。
约瑟夫环运作如下：
1、一群人围在一起坐成环状（如：N）
2、从某个编号开始报数（如：K）
3、数到某个数（如：M）的时候，此人出列，下一个人重新报数
4、一直循环，直到所有人出列，约瑟夫环结束
一般形式
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。
分析：
（1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。
（2）开始时每个人都是活的，所以数组初值全部赋为false。
（3）模拟杀人过程，直到所有人都被杀死为止。
C++代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<iostream> usingnamespacestd; main () { boola[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 < a[t]=1;//此处人已死，设置为空 f++;//死亡人数+1 } } while (f!=n);//直到所有人都被杀死为止 } |
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm），当n，m非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人（编号一定是（m-1） mod n) 出列之后，剩下的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=0;
f=(f+m) mod i; (i>1）
有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f，程序也是异常简单：
c++
|
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
⑥c:=c-b{退到前一组}
⑦x:=a-c{算出目标为所在组的第几个元素}
⑧ans:=x*2-1{求出该元素}
⑨write(ans)
有了思路，再加上高精度就可以了。我写的代码比较猥琐，因为是先把上面的思路敲进去，再写过程，又把一些简单的过程合到主程序中了，所以有点乱，也有点猥琐。起提供思路的作用还是完全可以的吧~~~
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
vara,b,c:array[1..105]ofinteger; la, lb ,lc,i:integer; s:string; procedureincc; vari:integer; begin fori:=1to105doc:=c+b; fori:=1to104doifc>9then begin c:=c+cdiv10; c:=cmod10; end; end; functioncxiaoa:boolean; vari:integer; begin cxiaoa:=false; fori:=105downto1do ifc break;end elseifc>athenbreak; end; proceduredoubleb; vari:integer; begin fori:=1to105dob:=b*2; fori:=1to104doifb>9then begin b:=b+bdiv10; b:=bmod10; end; end; procedure decc ; vari,j:integer; begin fori:=1to104do ifc>=bthenc:=c-belse begin j:=i+1; whilec[j]=0doinc(j); whilej> ido begin c[j]:=c[j]-1; c[j-1]:=c[j-1]+10; dec(j); end; c:=c-b; end; end; procedurefua; vari:integer; begin fori:=1to104do ifa>cthena:=a-celse begin a:=a-1; a:=a+10; a:=a-c; end; end; procedureoutit; vari,j:integer; begin fori:=1to105doa:=a*2; fori:=1to104doifa>9then begin a:=a+adiv10; a:=amod10; end; ifa[1]>0thena[1]:=a[1]-1else begin j:=2; whilea[j]=0doinc(j); whilej>1do begin a[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; begin readln(s); la:=length(s); fori:=ladownto1doa:= ord (s[la+1-i])-ord('0'); b[1]:=1; c[1]:=1; whilecxiaoado begin doubleb; incc; end; decc; fua; outit; end. |
猴子选王
问题表述
一． 问题描述：
一堆猴子都有编号，编号是1，2，3 …m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
约瑟夫
"密码问题"
问题描述：编号为1、2、3、…、N的N个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。从指定
编号为1的人开始，按顺时针方向自1开始顺序报数，报到指定数M时停止报数，报M的人出列，并将
他的密码作为新的M值，从他在顺时针方向的下一个人开始，重新从1报数，依此类推，直至所有的
人全部出列为止。请设计一个程序求出出列的顺序，其中N≤30，M及密码值从键盘输入。
二． 基本要求：
（1） 输入数据：输入m,n m,n 为整数，n
（2）中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能
编程解决
1.C程序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<stdio.h> #include<malloc.h> #defineLENsizeof(structmonkey)//定义structmonkey这个类型的长度 structmonkey { int num ; structmonkey*next; }; structmonkey*create(intm) { structmonkey* head ,*p1,*p2; inti; p1=p2=(structmonkey*)malloc(LEN); head=p1; head->num=1; for(i=1,p1->num=1;i<m;i++) { p1=(structmonkey*)malloc(LEN); p1->num=i+1; p2->next=p1; p2=p1; } p2->next=head; returnhead; } structmonkey*findout(structmonkey*start,intn) { inti; structmonkey*p; i=n; p=start; for(i=1;i<n-1;i++) p=p->next; returnp; } structmonkey*letout(structmonkey*last) { structmonkey*out,*next; out=last->next; last->next=out->next; next=out->next; free (out); returnnext; } intmain() { intm,n,i, king ; structmonkey*p1,*p2; printf("请输入猴子的个数m://n"); scanf ("%d",&m); printf("每次数猴子的个数n://n"); scanf("%d",&n); if(n==1） { king=m; } else { p1=p2=create(m); for(i=1;i<m;i++) { p2=findout(p1,n); p1=p2; p2=letout(p1）; p1=p2; } king=p2->num; free(p2）; } printf("猴王的编号是：%d//n",king); return0; } |
C语言程序2
?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
//猴子选大王问题（约瑟夫环问题） #include<stdio.h> #include<string.h> #include<stdlib.h> intfre( char mok[],intk) { inti; printf("//n猴子编号：//n"); for(i=0;mok[i]!='//0';i++) printf("%d//t",mok[i]);//输出为踢出之前的编号，测试用 for(i=k;mok[i]!='//0';i++) { mok[i]=mok[i+1]; }//一个循环，将k以后的元素前移 putchar('//n'); for(i=0;mok[i]!='//0';i++) printf("%d//t",mok[i]);//输出踢出之后的编号，测试用 printf("//n按回车继续下一轮://n"); getch();//暂停，测试用 return0; } intmain() { charmok[50]; inti; intn,s,b;//n表示猴子总数；s表示步进；b表示元素个数及大王编号 intj,k;//j,k都是计数器 mok[0]=1;//初始化mok[0],让后面编号更简单的进行 printf("请输入猴子的总数：//n"); scanf("%d",&n);//输入猴子的总数 for(i=1;i<n;i++) { mok[i]=i+1; }//对猴子进行编号 mok[n]='//0';//用0来表示数组的结尾 printf("请输入 循环单位 ：//n"); scanf("%d",&s);//单位长度 b=n;//统计猴子的个数 for(j=1,k=0;; j++ ,k++) { if(b==1) { b=mok[0]; break ; }//如果元素只剩下一个，那么退出循环 if(j==s) { printf("//n它出列了：%d//n",mok[k]); fre(mok,k);//用于元素前移的函数 b–; j=1; }//将猴子从数组中踢出，并重置计数器J。 if(mok[k+1]=='//0') k=-1;//重置计数器k，因为后面有k++所以k要在重置基础上-1. }//判断是否为数组最后元素，重置计数器k。 system("colorc");//无聊，改变cmd环境颜色。 printf("//n最终大王是他：%d//n",b); return0; } |
C语言程序3: 用数组模拟链表
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include<stdio.h> #include<malloc.h> intmain() { int*person,i,node,n,m; scanf("%d%d",&n,&m); person=(int*)malloc(sizeof(int)*(n+1)); for(i=1;i<=n;i++)//初始化圈 { person[i]=i+1;//i表示编号为i的人,person[i]的值表示编号为i的人的下一个人的编号 } person[n]=1;//编号为n的下一个人的编号是1 node=1; while (node!=person[node])//如果某个人的下一个人不是自己,意味着人数超过1人 { for(i=1;i<m-1;i++)//这个循环终止于被杀的人的前一个人 { node=person[node];//下一个人的编号为node,node的值来自于前一个人的person[node] } printf("%d",person[node]);//输出被杀的人编号 person[node]=person[person[node]];//修改被杀的人的前一个人的person[node]为被杀的人的后一个人的编号 node=person[node];//这句话中的node是被杀的人后一个人 } printf("%d",node);//输出 最后幸存者 的编号 return0; } |
pascal程序：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
var a:array[1..10000]ofinteger; n,s,i,j:integer; begin read (m,n); fori:=1tomdoa[i]:=1; j:=0; fori:=1tomdo begin s:=0; whiles<ndo begin ifj<mtheninc(j) elsej:=1; s:=s+a[j]; end; write (j); a[j]:=0; end; end. |
c++程序
|
1 2 3 4 5 6 7 8 9 |
#include<stdio.h> intmain() { intn,m,i,s=0; printf("NM=");scanf("%d%d",&n,&m); for(i=2;i<=n;i++)s=(s+m)%i; printf("Thewinneris%d//n",s+1）; return0; } |
约瑟夫数学算法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include<stdio.h> #include<conio.h> intmain( void ) { intn,i=0,m,p; scanf("%d%d",&n,&m);//n总人数，m步长 while(++i<=n) { p=i*m; while(p>n) p=p-n+(p-n-1）/(m-1）; printf("%d//n",p); } getch(); return0; } |
约瑟夫递推算法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include<iostream> usingnamespacestd; intking(intM,intN) { intk=0; for(inti=2;i<=M;i++) k=(k+N)%i; return++k;}i ntmain() { intn,m; while(scanf("%d%d",&n,&m)&&n&&m) { cout < } return0; } |
2、PHP模拟算法
php有非常完善的数据结构模拟方案,可以非常简洁的解决这样的问题!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
functionking($n,$m){ $monkey=range(1,$n);//模拟建立一个连续数组 $i=0; while(count($monkey)>1){ $i+=1;//开始查数 $head=array_shift($monkey);//直接一个一个出列最前面的猴子 if($i%$m!=0){ array_push($monkey,$head);//如果没数到m或m的倍数,则把该猴放回尾部去. }//否则就抛弃掉了 } return$monkey[0]; } echo'剩余',king(3,4),'号猴子'; |
笔算解决
笔算解决约瑟夫问题
在M比较小的时候，可以用笔算的方法求解，
M=2
即N个人围成一圈，1，2，1，2的报数，报到2就去死，直到只剩下一个人为止。
当N=2^k的时候，第一个报数的人就是最后一个死的，
对于任意的自然数N都可以表示为N=2^k+t，其中t
于是当有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/3]个人，[]表示取整，还剩下n-[n/3]个人
设这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/3]）个人
若n mod 3≠0 且f(n-[n/3])<=n mod 3则最后死的人为新一轮的第n-[n/3]+F(n-[n/3])-（n mod 3）人
若n mod 3≠0 且f(n-[n/3])>n mod 3则最后死的人为新一轮的第F(n-[n/3])-（n mod 3）人
3、新一轮第k个人对应原来的第 3*[(k-1）/2]+(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-[n/3])<=n mod 3时 k=n-[n/3]+F(n-[n/3])-（n mod 3），F(n)=3*[(k-1）/2]+(k-1）mod 2+1
当f(n-[n/3])>n mod 3时 k=F(n-[n/3])-（n mod 3） ，F(n)=3*[(k-1）/2]+(k-1）mod 2+1
这种算法需要计算 [log（3/2）2009]次 这个数不大于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）=634
原创文章，作者：来自网友投稿，如若转载，请注明出处：https://www.ladyww.cn/article/20221222125022.html