约瑟夫问题（Josephus Problem）4：第k个出列的人是谁

本文主要是介绍约瑟夫问题（Josephus Problem）4：第k个出列的人是谁，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

版权所有。所有权利保留。

欢迎转载，转载时请注明出处：

http://blog.csdn.net/xiaofei_it/article/details/16813419

本文是论述约瑟夫问题的第四部分，约瑟夫问题的描述在第一部分，本文用到了第三部分的算法。请先阅读第一部分和第三部分。

现在要求输出第k个出列的人的编号。

由第三部分的算法分析可知，规模为i-1的队列的任意一人的编号为p，规模为i的队列的任意一人的编号为q。

则q=(p+c-1)%i+1。

另外，第k个出列的人出列前，队列规模为N+1-k。并且此人在这个队列中的编号为C mod (N+1-k)，同样要改进一下，变为(C-1) mod (N+1-k)+1。

这样，我们一步步递推，便可以得出此人本来的编号。

代码如下：

#include <iostream>
using namespace std;
int main()
{int n,c,k;cout<<"Input n:"<<endl;cin>>n;cout<<"Input c:"<<endl;cin>>c;cout<<"Input k:"<<endl;cin>>k;k=n+1-k;int pos=(c-1)%k+1;for (int i=k+1;i<=n;i++)pos=(pos+c-1)%i+1;cout<<pos<<endl;return 0;
}

这篇关于约瑟夫问题（Josephus Problem）4：第k个出列的人是谁的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---