约瑟夫环问题

约瑟夫环问题

科技前沿 • 2025-03-29 07:15 • 阅读 100

大家好，我是讯享网，很高兴认识大家。

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
输入
8 1 3 (n=8 k=1 m=3 )
输出
7 (剩下的那个)
样例输入
8 1 3
样例输出
7
1.分析问题：已知编好号的一群人围成一圈，做游戏，有一个数字m，从第k个人开始报数，后面的人挨着报数，报道m时，该人出局，由下一个从1开始报，以此类推，直到最后一个人结束；现在就是给你总人数n，第k个开始，特殊数字为m，找出最后一个人；
2.解决问题的思想：首先争对此问题，第一想法就是循环，一个一个出局，然后找出最后一个出局的即可完成任务；
3.解题步骤：
a.首先根据解题思想，首先由于是连续的数，判断是否出局，得需要一个bool类型的数组来储存状态（出局为false）；
b.利用循环语句，写出从第k个人开始，然后当数到m时此人出局，当循环一遍之后未出结果，然后接着进行下去（从状态还是true，那些人也就是对应的编号；）
c.当淘汰人数为n时就输出最后的编号，便为索要结果；
如下OJ上提交遇到问题的代码：
Runtime Error

讯享网

#include <iostream> using namespace std; int main() { 
    int n,k,m,count=0; cin>>n>>k>>m; bool *ch=new bool[n+1]; for(int i=1;i<=n;i++) ch[i]=true; for(int i=k,j=0;;i++) { 
    if(ch[i]) { 
    j++; if(j==m) { 
    ch[i]=false; count++; j=0; } if(count==n) { 
    cout<<i<<endl; break; } } if(i==n) i=0; } delete []ch; return 0; }

讯享网

然后ac的思路：
1.解决问题：看是否可以找出递推公式，经过上网查询找到了递推公式（默认为从第一个人开始）；
从n个人，由0开始编号，然后第一次是淘汰第m-1这个人；
然后第二次从m开始，淘汰的便是第m-1+m（在不超过总人数n的情况下）；
衍生递推公式为：f (i) = f (i-1) +m;然后考虑到超出总人数的范围，那么求模即可，所以最后为：f (i)=(f (i-1)+m)%i；
递推结束即为f（1）=0；
2.解题步骤：
a.根据导出的递推公式，从2开始推到n得出的最后一个人的序号；
b.然后根据要从第k个人开始，那么就是相当于把k前面的人放到后面，也可以在得出的序号上面直接加上一个k，大于n则取模；

讯享网#include <iostream> using namespace std; int main() { 
    int n,m,k; cin>>n>>k>>m; int count=0; for(int i=2;i<=n;i++) { 
    count=(count+m)%i; } if(count+k==n) cout<<n<<endl; else cout<<(count+k)%n<<endl; return 0; }

相关推荐