题目:
Josephus有过的故事:39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀。然后下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
一、使用循环链表模拟全过程
#include<iostream>
using namespace std;
/************约瑟夫问题****************/
typedef struct CLinkList
{
int data;
struct CLinkList *next;
}node;
int main()
{
///建立循环链表
node *L,*r,*s;
L = new node;
r =L;
int n = 41,i;
int k = 3;
for(i = 1;i<=n;i++) //尾插法建立链表
{
s = new node;
s->data = i;
r->next = s;
r= s;
}
r->next =L->next; //让最后一个结点指向第一个有数据结点
node *p;
p = L->next;
delete L; //删除第一个空的结点
///模拟解决约瑟夫问题
while(p->next != p) //判断条件:因为最后肯定剩下一个人, 循环链表的最后一个数据的next还是他本身
{
for(i = 1;i<k-1;i++)
{
p = p->next; //每k个数死一个人
}
cout<<p->next->data<<"->";
p->next = p->next->next; //将该节点从链表上删除。
p = p->next;
}
cout<<p->data<<endl;
return 0;
}
二、公式法
1、最开始我们有这么多人:
[ 0 1 2 3 4 5 ... 37 38 39 40 ]
2、第一次自杀,则是(3-1)%41=2 这个人自杀,则剩下:
[ 0 1 3 4 5 ... 37 38 39 40 ]
3、然后就是从编号为3%41=3的人开始从1报数,那么3号就相当于头,既然是头为什么不把它置为0,这样从它开始就又是与第1,2步一样的步骤了,只是人数少了一个,这样不就是递归了!!!就可以得到递归公式。想法有了就开始做:
4、把第2步中剩下的人编号减去3映射为:
[ -3 -2 0 1 2 ... 34 35 36 37 ]
5、出现负数了,这样不利于我们计算,既然是环形,37后面报数的应该是-3,-2,那么把他们加上一个总数(相当于加上360度,得到的还是它)
[ 38 39 0 1 2 3 ... 34 35 36 37 ]
6、这样就是一个总数为40个人,报数到3杀一个人的游戏。
这次自杀的是第5步中的(3-1)%40=2号,但是我们想要的是第2步中的编号(也就是最初的编号)
那最初的是多少?对应回去是5;
这个5是如何得到的呢?是(2+3)%41得到的。大家可以把第5步中所有元素对应到第2步都是正确的。
7、接下来是
[ 35 36 37 38 0 1 2... 31 32 33 34 ]
自杀的是(3-1)%39=2,先对应到第5步中是(2+3)%40=5,对应到第2步是(5+3)%41=8。
8、这下看出来规律了把:
我们是正着推的,如果反过来推导,每次剩下的人的编号为f(i),剩一个人的时候编号一定为0,两个人为0,1,以此类推,则利用以下公式可以推导出每次剩下的人。
f(1)=0;
f(i)=(f[i-1]+m)%i;(i>1)
代码如下:
#include<iostream>
using namespace std;
///推导公式方法
int yuesefu(int n,int m){
if(n == 1){
return 0; //这里返回下标,从0开始,只有一个元素就是剩余的元素0
}
else{
return (yuesefu(n-1,m) + m) % n; //我们传入的n是总共多少个数
}
}
int main(void){
int a=41,b=3;
//递归求最后一个存活的编号
//使用从正向思考
cout<<"最后一个人是"<<yuesefu(a,b)+1<<endl;
//反向思考,从自杀的最后一人向前
int result = 2;
//第一个自杀的人3号
cout<<3;
//每次自杀的都是2号,但是不同的2号换算到最初序号所需的的次数是不同的
//外循环是循环不同的换算次数
for(int i = a; i >= 2 ; i-- )
{
result = 2;
//内循环是开始换算
for(int j = i; j <= a; j++)
{
result = (result+b) %j;
}
cout<<"->"<<result+1;//0开始变1开始,所以加1
}
return 0;
}
结果是一样的:
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/9182.html