• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

详解约瑟夫环问题C/C++

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

约瑟夫问题:n个人围坐成一圈,从1开始顺序编号;游戏开始,从第一个人开始由1到m循环报数,

报到m的人退出圈外,问最后剩下的那个人原来的序号。

 

问题分析:面对这样循环报数的数据,我们最容易想到的就是用数组进行报数的模拟,最后把存活的人的编号输出。

先贴上这种思路的代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 #include<algorithm>  // find() 函数
 6 
 7 int main(){
 8     int m,n;
 9     cin>>n>>m;
10     vector<bool> s(n, 1);
11     int dead(0), cnt(0);
12     auto it=s.begin();
13     while(dead < n-1){
14         if(it == s.end())   it = s.begin();
15         if(*it) cnt++;
16         if(cnt == m){
17             *it = 0;
18             cnt = 0;
19             dead++;
20         }
21         it++;
22     }23     it=find(s.begin(), s.end(), 1);
24     cout<<it-s.begin()+1;
25     return 0;
26 }

 

代码思路是采用 vector<bool> 容器来存储每一个人的存在状态,如果在圈内参与报数,则值为1,退出圈后为0 。dead 是退出圈不参与报数的人数,作为报数停止的条件,即当 dead == n-1 时,报数停止。cnt 是每一个人报的数,当 cnt == m 时,报该数的人退出圈不再参与报数,在vector数组中的位置变为 0。

第十行,使用vector的迭代器来表示报数成员所对应的下标,while循环中即报数的模拟过程。

第十四行,因为迭代器运行过程中,可能指向 s.end() ,这一位置并不在vector 内,且没有有意义的数据,于是把迭代器重新指向 s.begin() ,这一过程解决了环形报数中第一个人和最后一个人连接的问题。

第十五行,表示报数过程,vector 数组中,此成员参与报数的话,cnt++ ,模拟报数的进行。

第十六行开始,遇到报到 m 的人,vector 中所对应的数据变为0,dead++ ,表示不再参与报数。cnt 置 0 ,表示所报数字重新从1开始(为什么不让cnt=0:因为下一个人出现时,才会自增1)。

第二十三行,得到最后那个人的迭代器指向。由于 vector 迭代器是随机访问迭代器,支持加减运算,所以刚才得到的迭代器指向减去 s.begin() ,就是最后留下的人所对应的下标(为什么不是他的原序号:因为下标从 0 开始计数),该结果再加一就是最后留下的人的原序号。

 

模拟的效率似乎不是很高,而且代码量也不算少,那有什么简单的办法呢?

先贴代码:

  递归调用:

#include<iostream>
#include<cstdio>
int joseph(int n, int m){
    return n==1 ? 0 : (joseph(n-1, m)+m)%n;
}
int main(){
    int m,n;
    cin>>n>>m;
    cout<<joseph(n, m) +1;
    return 0;
}
 
题目要求出最后剩下的人的原序号,即该人所对应的下标 +1 。设 f (n , m) 是幸存者所对应的下标,
则找出 f (n , m) 与 f(n-1 , n) 的递推关系便可以写出递归函数。
以f(4, 2)举例:
       1  2  3  4
       3  4  1
       1  3
       1
我们只需要关注下标的变化即可。当 n=1 时,f(1 , m)必然等于 0 。而当 f (4 , 2) 变为 f (3 , 2) 时,
数组整体向左移动了 m=2 。反过来可知,当 f (3 , 2) 变为 f (4 , 2) 时,数组整体向右移动了 m=2。
即 f (3 , 2)+2 = f (4 , 2)。
考虑到实际情况为环形报数,处理后的数据可能存在溢出,所以每次结果对所剩人数 n 取余,从而得到
实际的下标。
即 ( f (3 , 2)+2 ) % 4 = f (4 , 2)
即 ( f (n-1 , m)+m ) % n = f (n , m)
此时已得到递推关系,则可得到幸存者所对应的下标。又因为报数时从 1 开始报数,所以下标+1便是幸存者的原序号。
 
由上述关系,同样可以写出递推的代码:
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int main(){
 6     int m,n;
 7     cin>>n>>m;
 8     int location(0);  //若只有一个玩家,则幸存者必然是他,且下标为0
 9     for(int q=2; q<n+1; q++){
10         location = (location+m)%q;
11     }
12     location++;        //下标加一就是成员原序号
13     cout<<location;
14     return 0;
15 }

第九行中的 q ,作为循环条件的同时,也是每一次游戏中的所剩人数,协助完成第一个成员和最后一个成员的连接。

 

如果游戏规则拓展后,情况又应该是怎样的呢?可以看另一篇博客:

约瑟夫环问题拓展 C/C++


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
c++实现栈的push、pop、min发布时间:2022-07-14
下一篇:
oracle函数RAWTOHEX(c1)发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap