c语言实现约瑟夫环

一般有循环链表和数组模拟两种方式，貌似还有递归实现的呢！这里主要介绍数组模拟方式。

一. 最简单的约瑟夫环问题

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

如果用数组模拟这个过程，就要考虑两个问题：

1.怎样实现尾部和头部的无缝连接这个循环过程？

意思就是当第n个人报完数时，下一个报数的应该又是1而不是n+1。如果用循环链表确实好做，但用数组的话可以通过while+for来实现，来看看。

while(1){ for(int i=1;i<=n;i++) cout<<i<<" "; }

这段程序可以不断地输出1到n的所有值，这不就完成了尾部和头部的无缝连接嘛，我们只需将条件改改就行了。

2.怎么模拟数到m这个过程？

开始时把所有的值状态标记为1，代表这个人在循环的队列中。我们可以不断地遍历这n个值，每当遇到在队列中的人时，计数器num++（这个计数器num只在遇到status[i]==1时自增），当num==m时，这个人出列，计数器清0，状态标记为0（代表这个人出列了，不在循环的队列中），同时用来记录出列人数的count++。当count==n时，n个人已经全部出列，可以退出for和while了。

代码如下：

#include<bits/stdc++.h> const int maxn = 1111; using namespace std; int main(){ int n,m; int status[maxn]; int count = 0; int num = 0; cin>>n>>m; memset(status,0,sizeof(status)); for(int i=1;i<=n;i++) status[i] = 1; while(count<n){ for(int i=1;i<=n;i++){ if(status[i] == 1) num++; if(num == m){ cout<<i<<" "; status[i] = 0; count++; num = 0; } if(count == n) break; } } return 0; }

二. 简单的约瑟夫环问题

这个问题和上面的一样，不过这里的问题变成了每个人有一个可以输入的编号，而不再是1~n这样编号了。其实本质和上面是一样的，无非是加一个sum[ ]数组记录这n个人的编号罢了，输出的时候不再输出i了，而是输出i对应的编号sum[ i ]。

直接瞧代码吧：

#include<bits/stdc++.h> const int maxn = 1111; using namespace std; int main(){ int n,m; int status[maxn]; int sum[maxn]; int count = 0; int num = 0; cin>>n>>m; memset(status,0,sizeof(status)); for(int i=1;i<=n;i++) cin>>sum[i]; for(int i=1;i<=n;i++) status[i] = 1; while(count<n){ for(int i=1;i<=n;i++){ if(status[i] == 1) num++; if(num == m){ cout<<sum[i]<<" "; status[i] = 0; count++; num = 0; } if(count == n) break; } } return 0; }

三.稍稍复杂一丢丢的约瑟夫环问题

这个问题又比上面问题多了一个条件，从第k个人开始报数而不是从1开始报数。那么完整问题是：已知n个人（这n个人的编号可以自己输入）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

实现这个只需要在第二个问题的基础上加上一个flag就行了，具体的窍门自己看，直接上代码：

#include<bits/stdc++.h> const int maxn = 1111; using namespace std; int main(){ int n,m,k; int status[maxn]; int sum[maxn]; int count = 0; int num = 0; int flag = 0; cin>>n>>m>>k; memset(status,0,sizeof(status)); for(int i=1;i<=n;i++) cin>>sum[i]; for(int i=1;i<=n;i++) status[i] = 1; while(count<n){ for(int i=1;i<=n;i++){ if(i == k) flag=1; if(flag==0) continue; if(status[i] == 1) num++; if(num == m){ cout<<sum[i]<<" "; status[i] = 0; count++; num = 0; } if(count == n) break; } } return 0; }

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/231765.html原文链接：https://javaforall.net