2025年约瑟夫问题(数组+队列+公式迭代+递归)

约瑟夫问题(数组+队列+公式迭代+递归)约瑟夫问题 数组 队列 公式迭代 递归 约瑟夫环问题起源于一个犹太故事 罗马人攻占了桥塔帕特 41 个人藏在一个山洞中躲过了这场浩劫 这 41 个人中 包括历史学家 Josephus 约瑟夫 和他的一个朋友 剩余的 39 个人为了表示不向罗马人屈服 决定****

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

约瑟夫问题(数组+队列+公式迭代+递归)

简化一下问题(不这么血腥的例题):


设有n个人围坐一圈,编号为1到n,现从编号为1的人开始报数,数到m的人出列,接着从出列的下一个编号(人)开始重新报数,数到m的人出列,如此下去,直到只剩下最后一个人,并输出其编号。


例如输入

4 5 

讯享网

输出结果

讯享网2 

用数组的思路很简单(这也是刚开始接触这道题我的做法)

#include<iostream> using namespace std; int main() { 
    int n,m;//n表示多少个人参与游戏,m表示数到多少个人出圈 cin>>n>>m; int arr[1000]= { 
   0}; //0表示人还在圈中 int k=0;//报数数到几 int c=0;//当前人的编号 int s=0;//出圈的人数和 while(s!=n) { 
    c++; if(c>n)c=1;//大于总人数时,重新开始报数 if(arr[c]==0) { 
    k++; if(m==k) { 
    arr[c]=1;//标记后下次不报数 s++; //cout<<c<<" "; k=0;//使下一个人从1开始报数 } } } cout<<c; } 

编译结果如下:
在这里插入图片描述
讯享网


队列的方法(C++)

相比于数组,队列的方法更好写,同时也很好理解。

解法:将人数按编号1-n依次存入队列中,然后做双重循环,将队头元素放到队尾,每隔m-1个退出循环,弹出队

头元素(相当于杀掉的人),再一直循环到只剩最后一人为止。

讯享网#include<iostream> #include<queue> using namespace std; int main() { 
    queue<int>Q; int i,j,n,m; cin>>n>>m; for(i=1;i<=n;i++) { 
    Q.push(i); } while(n!=1) { 
    for(j=1;j<m;j++)//相当于j<=m-1;起计数的作用 { 
    Q.push(Q.front());//队头元素放到队尾 Q.pop();//弹出队头元素 } Q.pop();//杀掉的人 n--;//总人数减一 } cout<<Q.front(); } 

运行结果如下:
在这里插入图片描述

当然这里队列queue也可以转换为数组,即用f,r++。。。来做。这里就不写了。


找规律的方法(公式法)

理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人,其实就是把这个数组向前移动了M位。然后逆过来,就可以得到这个递推式。

#include<iostream> using namespace std; int main() { 
    int n,m;//n表示多少个人参与游戏,m表示数到多少个人出圈 int k=0; cin>>n>>m;//输入n和m for(int i=2;i<=n;i++) { 
    k=(k+m)%i; } cout<<k+1;//记录的是下标,所以要加上1 } 

编译结果如下:
在这里插入图片描述

和递归的递推公式相比,似乎看上去很像,但它们之间的思想有着本质的区别。递归推导式是从上到下,不断进入

递归再回溯;而这种推导式,是从下到上,符合正常的逻辑思维,比较容易理解。


递归的思想比较复杂(其实就是公式法),但代码量炒鸡短。

f(n,k)中的n为未报过数的人数,k为报数的数,等号右边就是最后剩下的人的编号。(从编号1开始)

迭代法 k=5

f(n,k) = [f(n-1,k) + k] % n

f(4,5)=2

f(3,5)=1

这样下去,倒推向前。

拓展:

从第一个士兵开始remove ;

f(3,5)=3

f(4,5)=2

显然和前面的规则而言,相当于不是从1开始数数,而是从2开始数数。所以公式不変!只是人数记得改成n-1

f(n,k) = [f(n-1,k) + k] % (n-1)

f(4,5) = 2

= [f(3,5)+5] % (4-1)

=(3+5)%3

=2

这里遍历多加上了一个变量n用于递归结束的标志。

讯享网#include<iostream> using namespace std; int recursion(int sum,int value,int n) { 
    if(n==1)return(sum+value-1)%sum;//递归结束的标志:剩下最后一个人 else return (recursion(sum-1,value,n-1)+value)%sum; } int main() { 
    int n,m;//n表示多少个人参与游戏,m表示数到多少个人出圈 cin>>n>>m; cout<<recursion(n,m,n)+1; } 

运行结果如下:
在这里插入图片描述


当然除了以上方法外,还有就是循环链表的方法,较为繁琐。这里以后有空再更新。

主要是链表的代码较为复杂又臭又长。


总结

其实,要你直接写出约瑟夫问题的题目不多,更多的是将几种方法和约瑟夫问题结合起来的题目。因此,个人认为数组,队列的放法必须要掌握,递归和公式法因为不同题目有不同问题,会比较难理解也会很难写出来,链表嘛要是题目没明确规定,还是别了吧!

以上纯个人笔记,若有不对的地方,请及时纠正。

小讯
上一篇 2025-03-21 19:05
下一篇 2025-04-06 20:06

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/81240.html