首页 > 代码库 > 约瑟夫问题的解法集锦

约瑟夫问题的解法集锦

约瑟夫问题的N种解法

1 问题的历史以及不同的版本

1.1 

         约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的,他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达伯特城达47天之久,在城市沦陷之后,他和40名死硬的将士在附近的一个洞穴中避难。在那里,这些叛乱者表决说“要投降毋宁死”。于是,约瑟夫建议每个人轮流杀死他旁边的人,而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签,并且,作为洞穴中的两个幸存者之一,他说服了他原先的牺牲品一起投降了罗马。

 

1.2  

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

 

1.3  

         有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1 开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编

号。

 

1.4    

         编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,直到所有人全部出列为止。编程打印出列顺序。

 

2 问题的解法

2.1 数组解法

         建立一个数组并且初始化所有的元素为1,然后开始遍历数组,遇到符合条件的就把数组中对用的元素设置为0,并且在下次循环的时候不把0包括在内。

程序如下所示:

#include <iostream>
using namespace std;
 
void main()
{
         cout<<"Pleaseinput the total number n and selected number m"<<endl;
         intn,m;
         cin>>n>>m;
         if(n<2 || m<1 )
         {
                   cout<<"n is at least equal to 2 and m must bigger than0"<<endl;
                   cin>>n>>m;
         }
 
         int*pArr = new int[n];
         for(int i=0;i<n;i++)
                   pArr[i] = i+1;
 
         inti=0;
         intj=0;
         intk=0;
         while(k<n)
         {
                   if(pArr[i] !=0 )
                            j++;
                   if(j==m )
                   {
                            j=0;
                            cout<<pArr[i]<<"       ";
                            pArr[i]=0;
                            k++;
                   }
                   if(i<n-1)
                            i++;
                   else
                            i=0;
         }
 
         delete[]pArr;
}

2.2 循环链表解法

         这个是最显而易见的想法,遇到符合条件的节点就将其删除并且输出对应的编号

程序如下:

链表创建:

#ifndef DDXX_LINK_H
#define DDXX_LINK_H
#include <iostream>
#include <cstdlib>
using namespace std;


struct Node
{
	int nId;
	Node *next;
};
Node* InitLink(int num);

#endif

#include "Link.h"

Node* InitLink(int num)
{
	if(num<1)
	{
		std::cout<<"The link is must be longer than 1"<<endl;
		return NULL;
	}
	
	Node* head = new Node;
	head->nId=1;
	head->next = NULL;

	Node* ptr = head;
	int cnt = 1;
	while( cnt<num )
	{
		ptr->next = new Node;
		if(ptr == NULL)
			return NULL;

		ptr->next->next = head;
		ptr->next->nId = ++cnt;
		ptr = ptr->next;
	}
	return head;

}

测试:

<pre name="code" class="cpp">#include <iostream>
#include "Link.h"
using namespace std;
 
void main()
{
         cout<<"Pleaseinput the total number n and the selected m"<<endl;
         intn,m;
         cin>>n>>m;
         if(n<2 || m<1)
         {
                   cout<<"n is at least equal to 2 and m is must bigger than0"<<endl;
                   cin>>n>>m;
         }
         Node *head = InitLink(n);
         if(head== NULL)
         {
                   cout<<"Init linklist failed"<<endl;
                   return;
         }
 
         intk=0;
         inti=0;
         Node *ptr = head;
         Node *p = NULL;
         while(k<n)
         {
                   if(i<m-1)
                   {
                            i++;
                            p = ptr;
                            ptr = ptr->next;
                   }
                   else
                   {
                            cout<<ptr->nId<<"   ";
                            p->next =ptr->next;
                            Node* ptmp = ptr;
                            ptr = ptr->next;
                           
                            delete ptmp;
                            ptmp = NULL;
                            k++;
                            i=0;
                   }
         }      
}



2.3  递推解法

         n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编。

我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的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-2  --> n-2

k-1  --> n-1

 

变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗?!!变回去的公式很简单,相信大家都可以推出来:x‘=(x+k)%n

 

如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)个人的解呢?当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题!好了,思路出来了,下面写递推公式:

 

令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]

 

递推公式

f[1]=0;

f[i]=(f[i-1]+m)%i; (i>1)

实现程序如下所示:

#include <iostream>
using namespace std;
 
void main()
{
         int n;
         int m;
         cout<<"Pleaseint n for total number and m for selected number"<<endl;
         cin>>n>>m;
         if(n<2|| m<=0)
         {
                   cout<<"n is at least equal to 2 and m must be bigger than0"<<endl;
                   cin>>n>>m;
         }
 
         int s =0;
         for(int i=2;i<=n;i++)
                   s = (s + m) % i;
         cout<<"Theleft number is(0 based): "<<s<<endl;
}


 

约瑟夫问题的解法集锦