约瑟夫问题(数组+队列+公式迭代+递归)
简化一下问题(不这么血腥的例题):
设有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; }
运行结果如下:

当然除了以上方法外,还有就是循环链表的方法,较为繁琐。这里以后有空再更新。
主要是链表的代码较为复杂又臭又长。
总结
其实,要你直接写出约瑟夫问题的题目不多,更多的是将几种方法和约瑟夫问题结合起来的题目。因此,个人认为数组,队列的放法必须要掌握,递归和公式法因为不同题目有不同问题,会比较难理解也会很难写出来,链表嘛要是题目没明确规定,还是别了吧!
以上纯个人笔记,若有不对的地方,请及时纠正。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/81240.html