本文主要是介绍约瑟夫环(本人领悟后修改的），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
约瑟夫环：约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
我认为网上一篇非常好的解析，我看懂，并理解了，所以加点自己的体会，分享给大家，文后附有最初的链接，尊重知识产权。
假设问题是从n个人编号分别为0...n-1，取第k个，
则第k个人编号为k-1的淘汰，剩下的编号为 0,1,2,3...k-2,k,k+1,k+2...
此时因为从刚刚淘汰那个人的下一个开始数起，因此重新编号
把k号设置为0,则
k 0
k+1 1
...
0 n-k
1 n-k+1
假设已经求得了n-1个人情况下的最终胜利者保存在f[n-1]中，则毫无疑问，该胜利者还原到原来的真正编号即为 (f[n-1]+k)%n （因为第二轮重新编号的时候，相当于把每个人的编号都减了k，因此重新+k即可恢复到原来编号）。由此，我们可以想象，当最终只剩下一个人的时候，该人即为胜利者，此时重新编号，因为只有一个人，所以此时f[1]=0
这样f[2]=(f[1]+k)%2,这样就可以求出最终胜利者在2个人的时候的情况下的编号，由递推公式f[n]=(f[n-1]+k)%n,可递推到最初编号序列中该胜利者的编号。
因此用这个方法，只需一遍On的扫描，即可求出最终答案
不过该题要求编号从1开始，只要把f[n]+1即可，同时，该题指定了第一个要删除的人必须为编号为m的人，其实也不难，求出f[n]之后，把原本编号为0的位置移到跟m只相距k的位置即可实现第一次删除的编号为m。所以最终 ans=(f[n]+1+m-k);
当然因为m-k可能为负数，导致整个ans为负，这样其实最后+n即可解决。
比如3个人，从1开始数，，数到3出局，第一个出局的是：3；然后1出局，最后是2出局。
#include<cstdio>
using namespace std;
int n,m,k;
int main()
{
while (scanf("%d%d%d",&n,&k,&m))
{
if (n+m+k==0) break;
int s=0;
for (int i=2;i<=n;i++)
s=(s+k)%i;
int ans;
ans=(m-k+s+1)%n;
if (ans<=0) ans+=n;
printf("%d\n",ans);
}
return 0;
}
http://www.cnblogs.com/kkrisen/p/3569281.html#undefined
这篇关于约瑟夫环(本人领悟后修改的）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
