首页 > > 程序设计 > C/C++ >

从“约瑟夫问题”谈起

2019-08-16 07:54:59来源：博客园阅读 ()

从“约瑟夫问题”谈起

约瑟夫问题是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想自杀。为避免与其他39个决定自杀的犹太人发生冲突，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行，直到仅余15个人为止。问怎样的?排法，才能使每次投入大海的都是非教徒。

【例1】约瑟夫问题。

N个人围成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，…M”报数，报到M的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人，该人就是优胜者。输入N和M，输出出圈顺序。
例如，N=6、M=5，出圈的顺序是：5，4，6，2，3，1。

（1）编程思路。

为输出出圈顺序，采用一个数组来进行模拟。

定义int circle[N+1]，并按circle[i]=i+1的方式赋予各元素初值。该值代表两个含义：1）值为0，代表编号i+1的人不再圈中；2）值非0，代表圈中第i个位置的人编号为i+1。

定义变量i代表报数位置的流动，i的初值为0，代表编号为1的人的位置，i的变化方式为：

i=(i+1)%(n)，即0-->1-->2……->n-1 ->0-->1……。

i流动到了位置i后，该位置的人若已出圈（circle[i]==0），显然无法报数，得跳过该位置；若该位置的人在圈中，则报数（定义一个表示报数的变量p，初值为0，每次报数p++）。

当报数到m（即p==m）时，位置i的人出圈，记录出圈人数cnt++，同时p置为0。当出圈人数等于N时循环结束。

（2）源程序。

#include <stdio.h>
int main()
{
int n,m,i,p,cnt;
int circle[50];
while (scanf("%d%d",&n,&m) && n!=0)
{
for (i=0;i<n;i++)
circle[i]=i+1;
i=0; // 报数指示
p=0; // 报数计数器
cnt=0; // 出队人数
while (cnt<n)
{
if (circle[i]!=0) p++;
if (p==m)
{
printf("%d ",circle[i]);
cnt++;
circle[i]=0;
p=0;
}
i=(i+1)%(n);
}
printf("\n");
}
return 0;
}

下面我们从例1的基础上进行扩展讨论。

例如，运行例1的程序时，输入41 3，则输出为：

3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37

41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31

为这个输出结果进行的模拟是需要耗时的。实际上，在大多数问题中，我们不关心中间的结果，只关心某个最终结果。例如，在Josephus 的故事中，Josephus 和他的朋友不想自杀，Josephus 需要关心的是最后一个和倒数第2个出圈的编号是多少，至于中间过程（39个犹太人谁先自杀，谁后自杀）对Josephus 来说无意义。因此，Josephus 需要的是快速确定最后一个和倒数第2个出圈的编号，然后站到对应位置即可。而无需耗时模拟整个过程。

【例2】猴子选大王。

一堆猴子都有编号，编号是1，2，3 ...m，这群猴子(m个)按照1~m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。已知猴子数m和报数间隔n（设1<=n<=m<=50），问编号为多少的猴子当大王？

（1）编程思路1。

将例1的源程序略作修改，增加一个变量last记录最后获胜者编号，不输出中间过程。显然，

if (cnt==n) last=circle[i];

（2）源程序1。

#include <stdio.h>
int main()
{
int n,m,i,p,cnt,last;
int circle[50];
while (scanf("%d%d",&n,&m) && n!=0)
{
for (i=0;i<n;i++)
circle[i]=i+1;
i=0; // 报数指示
p=0; // 报数计数器
cnt=0; // 出队人数
while (cnt<n)
{
if (circle[i]!=0) p++;
if (p==m)
{
cnt++;
if (cnt==n) last=circle[i];
circle[i]=0;
p=0;
}
i=(i+1)%(n);
}
printf("%d\n",last);
}
return 0;
}

（3）编程思路2。

源程序1中采用数组模拟，由于猴子在圈中还是出圈是通过数组元素circle[i]的值非0还是0来判断，位置并未真正删除，因此当n和m很大时，程序的执行效率很低。例如，仅求最后一个出圈的元素，循环就得执行m*n次（p从1报到m，每次报数流动i得走完整一圈，其中n-1个已出圈，圈中仅一个元素）。

为提高运行效率，可以考虑采用循环链表来进行模拟，这样每次出圈就将链表中的相应元素删除。循环链表只剩最后一个元素时，输出胜者编号。

（4）源程序2。

#include <stdio.h>
struct Jose
{

int code; // 编号
Jose *next;
};
int main()
{
Jose *head,*p1,*p2;
int n,m,i,cnt,tmp;
scanf("%d%d",&n,&m);
while (n!=0 && m!=0)
{
head=new Jose;
head->code=1;
p2=head;
for (i=2;i<=n;i++) // 创建循环链表
{
p1=new Jose;
p1->code=i;
p2->next=p1;
p2=p1;
}
p2->next=head;
p1=head;
cnt=n;
while (cnt>1)
{
tmp=m%cnt; // 提高效率之举，当m大于圈中人数时会循环多圈，可以不用
if (tmp==0) tmp=cnt;
i=1;
while (i<tmp) // 报数m-1次
{
i++;
p2=p1;
p1=p1->next;
}
p2->next=p1->next; // 报m的结点出圈
delete p1; // 释放出圈结点的空间
cnt--;
p1=p2->next;
}
printf("%d\n",p1->code);
delete p1;
scanf("%d%d",&n,&m);
}
return 0;
}

（5）编程思路3。

本例中的源程序2相比源程序1可以提高运行效率，但毕竟也是采用过程模拟，因此对于n和m较大的情况，效率仍然不高。有没有可以根据n和m的值直接推出最后出圈人编号的办法呢？

为了讨论方便，先把问题稍微改变一下，并不影响原意。

　　问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
　　我们知道第1个人（编号一定是(m-1)%n）出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%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-3 --> n-3　　k-2 --> n-2
　　变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据转换把这个x变回去不刚好就是n个人情况的解吗？

下面我们来推导变回去的公式。

序列1： 1 , 2 , 3 , 4 , …k-1 , k , k+1 ,…， n-2 , n-1 , n
　　序列2： 1 , 2 , 3 , 4 , … k-1 , k+1 , … , n-2 , n-1 , n
　　序列3： k+1 , k+2 , k+3 , …, n-2 , n-1 , n , 1 , 2 , 3 ,… , k-2 , k-1
　　序列4： 1 , 2 , 3 , 4 , … , 5 , 6 , 7 , 8 , …, n-2 , n-1
　　∵ k=m%n;

　∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n

　　∴ x'= (x+ m%n)%n = (x+m)%n 。
　　如何知道(n-1)个人报数的问题的解f(n-1)呢？显然只要知道(n-2)个人的解f(n-2)就行了。(n-2)个人的解呢？当然是先求f(n-3) ---- 这显然就是一个倒推问题！
　　令 f[i] 表示i个人玩报m退出的约瑟夫环游戏的最后胜利者的编号，则有递推公式：
　　f[1] = 0 ;
　　f[i] = (f[i-1]+m)%i; (i>1)
　　有了这个递推公式，我们就很容易求得n个人报m退出的约瑟夫问题的最后胜利者编号f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1即可。

编写程序时，我们可以采用数组递推以便保存中间结果，也可以不保存中间任何结果采用迭代直接得到最后胜利者编号。

（6）采用迭代方式实现的源程序3。

#include <stdio.h>
int main()
{
int n,m,i,s;
scanf("%d%d",&n,&m);
while (n!=0 && m!=0)
{
s=0;
for (i=2;i<=n;i++)
s=(s+m) % i;
printf("%d\n",s+1);
scanf("%d%d",&n,&m);
}
return 0;
}

（7）采用递推方式实现的源程序4。

// 采用打表的方式，先将所有的值求出来保存在二维数组f[51][51]中。
// f[n][m]的值代表n个人报m游戏的最后胜利者编号。
// 则有 f[i][m]=0, (i=1)
// f[i][m]= (f[i-1][m]+m)%i (i>1)
#include <stdio.h>
int main()
{
int n,m,i,j,f[51][51];
for (i=1;i<51;i++)
f[1][i]=0;
for (i=1;i<51;i++)
{
for (j=2;j<51;j++)
f[j][i]=(f[j-1][i]+i)%j;
}
scanf("%d%d",&n,&m);
while (n!=0 && m!=0)
{
printf("%d\n",f[n][m]+1);
scanf("%d%d",&n,&m);
}
return 0;
}

【例3】城市断电。

有n（3<=n<150）个城市围成圈，先将第1个城市（编号为1）断电，然后每隔m个城市使一个城市断电，直到剩下最后一个城市不断电。问使2号城市不断电的最小的m是多少？

（1）编程思路。

采用例2的求最后胜利者的方式，对n个城市，从m=1开始搜索，若当前m可使2号城市作为胜利者，则m就是所求，否则m=m+1后，继续搜索。

程序采用打表的方式，先将n=3~149的对应m值求出来并保存到数组ans[150]中。

另外，需要注意的是第1个城市先断电了，2号城市相当第1个城市，也可以把问题看成编号从1~n-1的约瑟夫问题。

（2）源程序。

#include <stdio.h>
int main()
{
int ans[150],i,j,m,tmp;
for (i = 3;i<150;i++)
{
m = 1;
while(1)
{
tmp = 1; // 注意第1个城市已经断电，相当从1~n-1个城市
for (j = 2;j < i; j++)
{
tmp = (tmp + m)%j;
if (tmp == 0)
{
tmp = j;
}
}
if (tmp == 1) // 最后胜利者是2号城市

// （编号为1一开始就断电，2号相当圈中第1个城市）
{
ans[i] = m;
break;
}
m++;
}
}
int n;
scanf("%d",&n);
while (n!=0)
{
printf("%d\n",ans[n]);
scanf("%d",&n);
}
return 0;
}

将此源程序提交给POJ 2244 “Eeny Meeny Moo”，可以Accepted。

例2、例3采用约瑟夫递推公式，直接得到的是最后胜利者的编号，中间的出圈顺序就没得到。下面我们进一步讨论一下，能否不用模拟的方式，采用递推公式计算的方法，得到例1所示的出圈顺序呢？

设有n个人（0,...,n-1），报数m出圈，则第 i 轮出圈的人为

f(i)=(f(i-1)+m-1)%(n-i+1) (i>=1), f(0)=0; f(i) 表示当前子序列中要出圈的那个人（当前序列编号为0~(n-i));

例如，设n=6,m=5

f(0)=0;

f(1)=[ f(0)+5-1]%6=4; 子序列（0,1,2,3,4,5）中的4 （也就是实际序列（1，2，3，4，5，6）中的5）

f(2)=[ f(1)+5-1]%5=3; 子序列（0,1,2,3,5）中的3 （也就是实际序列（1，2，3，4，6）中的4）

f(3)=[ f(2)+5-1]%4=3; 子序列（0,1,2,5）中的5 （也就是实际序列（1，2，3，6）中的6）

f(4)=[ f(3)+5-1]%3=1; 子序列（0,1,2）中的1 （也就是实际序列（1，2，3）中的2）

f(5)=[ f(4)+5-1]%2=1; 子序列（0,2）中的1 （也就是实际序列（1，3）中的3）

f(6)=[ f(5)+5-1]%1=0; 子序列（0）中的0 （也就是实际序列（1）中的1）

故得到的出圈顺序为：5，4，6，2，3，1。结果正确。

按照这样的思路，可以修改例1的源程序为：

#include <stdio.h>
int main()
{
int n,m,i,j,cnt,circle[51],f[51];
scanf("%d%d",&n,&m);
while (n!=0 && m!=0)
{
for (i=0;i<n;i++)
circle[i]=i+1;
f[0]=0;
for (i=1;i<=n;i++)
{
f[i]=(f[i-1]+m-1)%(n-i+1);
}
cnt=n;
for (i=1;i<=n;i++)
{
printf("%d ",circle[f[i]]);
for (j=f[i];j<cnt-1;j++)
circle[j]=circle[j+1];
cnt--;
}
printf("\n");
scanf("%d%d",&n,&m);
}
return 0;
}