首页 > 代码库 > 1748:约瑟夫问题
1748:约瑟夫问题
总时间限制: 1000ms 内存限制: 65536kB描述约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。输入每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是：0 0输出对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号样例输入6 212 48 30 0样例输出517
约瑟夫问题的递推公式是ｆ［１］＝０，ｆ［ｉ］＝（ｆ［ｉ－１］＋ｍ）ｍｏｄ ｉ。不过是一个“数据结构之指针和链表”里面的问题，所以还是先用链表和指针解决。因为要移除中间元素，所以需要一个双向链表，这里用一个数组来模拟：
１、构建结构和数组：
struct node{ int id; node *pre; node *next;}lst[302];
２、初始化数组元素的ｉｄ：
for(m=1;m<=302;m++){ lst[m].id=m; }
３、初始化数组元素的指针：
for(i=1;i<=n;i++){ lst[i].next=&lst[i+1]; lst[i].pre=&lst[i-1]; } lst[n].next=&lst[1]; lst[1].pre=&lst[n];
４、查询需要删除的元素，直到当前元素和下一个元素都指向同一个元素：
node *cur=&lst[1]; while(cur->next!=cur){ for(i=2;i<=m;i++){ cur=cur->next; } cur->pre->next=cur->next; cur->next->pre=cur->pre; cur=cur->next; }
此时，ｃｕｒ－＞ｉｄ就是那个猴子王的初始编号。多组数据步骤２只需要进行一次，然后重复步骤３、４就可以了。但无论如何，这种方法的时间复杂度明显大于直接用数学方法进行求解，并且编码也多出很多。完整代码如下：
#include<iostream>#include<cstring>using namespace std;struct node{ int id; node *pre; node *next;}lst[302];int getking(int n,int m){ int i; //1、设置前后指针 for(i=1;i<=n;i++){ lst[i].next=&lst[i+1]; lst[i].pre=&lst[i-1]; } lst[n].next=&lst[1]; lst[1].pre=&lst[n]; //2、查询 node *cur=&lst[1]; while(cur->next!=cur){ //2.1、向后数到m for(i=2;i<=m;i++){ cur=cur->next; } //2.2、更新前后元素指针和当前数1的 cur->pre->next=cur->next; cur->next->pre=cur->pre; cur=cur->next; } return cur->id;}int main(){ int m,n; //初始化数组里的编号 for(m=1;m<=302;m++){ lst[m].id=m; } //获得输入并求解 cin>>n>>m; while(m!=0 && n!=0){ cout<<getking(n,m)<<endl; cin>>n>>m; }}
然后，我们来考虑一下不模拟报数过程来求解，当一个人出局之后，剩下ｎ－１人继续这个游戏，直到剩余１人。递推：１人时进行这个游戏，他不会出局的，两人呢？剩下的人是下次还能报数的那个，谁下次还能报数？同样，考虑３个人的情况，可以得出递推公式。核心代码如下：
s=0;
for(i=2;i<=n;i++){ s=(s+m)%i;
} cout<<s+1;
1748:约瑟夫问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。