约瑟夫问题分析

2018-12-19刘薇陈文

现代计算机 2018年32期

刘薇，陈文

（福州职业技术学院，福州 350108）

1 约瑟夫问题

约瑟夫问题是计算机算法中的经典问题，对约瑟夫问题的研究由来已久[1]，对约瑟夫问题的算法分析对于计算机程序设计的教学具有重要的作用[2]。约瑟夫问题的描述方式有多种形式[3]，但其本质是一样的。以下对约瑟夫问题给出一种描述方式：编号为1到n的n个人，按编号顺序围成一圈，即初始状态时，第n个的下一个为第1个。从1开始往后报数，报到k的倍数的人离开。如此继续，直到只剩最后一人为止。问最后留下的是n个人中的哪一个。

对于约瑟夫问题，最直观和最常用的方法便是顺序存储的数组标记法和利用循环链表的结点删除法。本文着重介绍除此之外的约瑟夫问题的其他解法，包括顺推法、逆推法、递归法等，进一步拓展解决问题的思路。并对各种方法进行分析对比，提高程序设计能力。

2 约瑟夫问题的解决方法

2.1 数组标记法

数组标记法是较为直观的一种算法[4]。它的基本思想就是直接用数组data[1],data[2],…,data[n]标记n个人的状态，值为1时，表示该元素已出局。初始状态data[1],data[2],…,data[n]的值均为0。当前编号current=0。从当前位置往后找非1元素。找k次后，将当前位置的数组值置为1。如此重n-1次，则，数组中值为0的下标编号即为所求。算法如下：

（1）从当前位置 current处寻找下一个值为 0位置。

int nextZero（int data[],int n,int current）{

current=current%n+1;//后移一位

while（data[current]!=0）

current=current%n+1;

return current;

}

（2）求解约瑟夫问题的主程序为：int main（）{

定义变量，输入n，k;

初始数组data[1]---data[n];

current=0;

for（kill=1;kill

{

for（i=1;i<=k;i++） //报 k 次

current=nextZero（data,n,current）;

data[current]=1;//当前位置出局

}

for（i=1;i<=n;i++）{

if（data[i]==0）{输出i;break;}

//查找数据值为0的数组下标

}

2.2 链式查找法

利用循环链表的方法解决约瑟夫问题，也是较为常用的方法之一。有学者对此算法的优劣做了较为详细的分析[5]，也有学者利用不同的程序设计语言进行相应的描述。本文利用《C语言程序设计》给出算法的描述。它的基本思想是：建立如下循环链表。

图1 循环链表示意图

当前位置current初始状态时为head，则算法描述为：当前位置current往后移k-1次后，将current的下一个元素删除。如此重复n-1次，则current的值即为所求。

（1）结点结构：struct node

{

int data;

struct node*next; //下一结点的地址

};

typedef struct node Llist;

（2）链表创建

Llist*creat（int n）{

Llist*head,*rear,*t;

head=（Llist*）malloc（sizeof（node））;

head->data=n;

rear=head;

int i;

for（i=1;i<=n-1;i++）{

t=（Llist*）malloc（sizeof（node））;

t->data=i;

rear->next=t;

rear=t;

}

rear->next=head;

return head;

}

求解约瑟夫问题的主程序为：int main（）{

定义参数，输入n,k

Llist*h,*t;

h=creat（n）;//创建初始链

for（kill=1;kill

for（i=1;i

h=h->next;

t=h->next;//t为第k个元素位置h->next=t->next;

free（t）;//将第 k 个元素删除}

printf（"i=%d ",h->data）;

2.3 顺推法

对于约瑟夫问题，从1开始往后报数。显然，当报数报到（n-1）*k时，必然有n-1个人离开，所以，最后一人报数必然是（n-1）*k+1。因此，约瑟夫问题可以描述为：编号为1到n的n个人，按顺序围成一圈，从1往后开始报数，报k的倍数的人离开。问：最后报数为（n-1）*k+1的是哪一个。

顺推法的基本思想是，从1到n逐个分析当前报数为m时，最后一次报数能否达到（n-1）*k+1。分析如下：

（1）当m为k的倍数时，m即为最后一次报数。

（2）当m不为k的位数时，此时，必有m/k个人不参与报数，即参数报数的人数为n-m/k个。所以，下轮的报数必然是m+（n-m/k）。于是，当前报数为m,求最后一次所报数的算法如下：

int lastNum（int n,int k,int m）{

while（m%k!=0&&m<（n-1）*k+1）

m=m+n-m/k;

return m;

}

求解约瑟夫问题的主程序为：

int main（）{

定义变量，输入n，k

}

for（i=1;i<=n;i++） //逐个判断最后一个报数能否达到（n-1）*k+1

if（lastNum（n,k,i）>=（n-1）*k+1）

{

输出i，程序结束

}

2.4 倒推法

约瑟夫问题，可归结为n个人，从1开始顺序报数，每报k的倍数的离开，问哪个数报到（n-1）*k+1。倒推法的基本思想是：从（n-1）*k+1倒推到上一轮的报数值，继续倒推到上一轮的报数值，直到报数值在1到n的范围中。

核心问题：当前报数为m，问上一轮的报数为多少解法一：设上轮报数为x,显然，x不为k的倍数，可将x表示为：

此时，已有p个人不参与报数。所以，

将式（1）代入式（2）可得：

m=p*k+r+n-p，进一步可化为：

m-n-1=p*（k-1）+（r-1），其中：r-1:0…（k-2）

于是：p=（m-n-1）/（k-1）;

r=（m-n-1）%（k-1）+1

所以，当前报数为m，求上轮报数值的算法如下：int preNum（int n,int k,int m）{

int x,p,r;

p=（m-n-1）/（k-1）;

r=（m-n-1）%（k-1）+1;

x=p*k+r;

return x;

}

求解约瑟夫问题的主程序为：

int main（）{

定义变量，输入n，k

num=（n-1）*k+1;

while（num>n）

num=preNum（n,k,num）;

输出num

}

解法二：由式（2）得：

2.5 递归法

递归法的基本思想是将n个人的约瑟夫问题转化为n-1个人的约瑟夫问题。将n个人围成一圈，从1开始报数，报k的倍数的人出局的约瑟夫问题记为f（n,k）。递归法的基本思想便是寻找f（n,k）与f（n-1,k）之间的关系。核心问题是：n>1时，已知f（n-1,k）=m求f（n,k）。

对f（n,k）的求解分析如下，第一个出局的编号记为a1。

（1）当n>=k时，a1=k。a1出局后，剩余的n-1个便形成了n-1个的约瑟夫问题。由于f（n-1,k）=m，所以，f（n,k）的解应该是a1往后m个。由于a1+m的值可能大于n，所以，必须将a1+m通过取余运算转化为1到n的范围。

于是：f（n,k）=（a1+m-1）%n+1，即：f（n,k）=（k+m-1）%n+1。

（2）当 n

f（n,k）=（a1+m-1）%n+1=（（k-1）%n+m）%n+1

即：f（n,k）=（k+m-1）%n+1;

综上可得：无论n与k的大小关系如何，均有f（n,k）=（k+m-1）%n+1。

也就是,当n>1时，f（n,k）=（k+f（n-1,k）-1）%n+1;

递归法算法如下：

int f（int n,int k）{

if（n==1）return 1;

else

return（k+f（n-1,k）-1）%n+1;

}

求解约瑟夫问题的主程序为：

int main（）{

输入 n，k;

p=n-m+x，代入式（1）得：

x=（n-m+x）*k+r，展开得：

x=n*k-m*k+k*x+r

m*k-n*k-1=x*（k-1）+（r-1）

x=（m*k-n*k-1）/（k-1）

于是算法描述为：

int preNum（int n,int k,int m）{

return（m*k-n*k-1）/（k-1）;

}

输出f（n,k）;

}

3 约瑟夫问题解决方法对比

数组标记法直观易懂，但运行效率低。利用链式结构的查找与删除，在运行时间上略有改进。但未有实质性的改进与突破。递归法虽然代码简单，但其运行机理是借助于栈的存储，运行时所占用的内存资源却是巨大的。而递推法尤其倒推法则是解决约瑟夫问题较为有效的方法。表1是约瑟夫问题不同方法的运行时间对比（k值取999）。从表1中可以看出。倒推法效率最高。数组标记法效率最低。