1.cpp

josephus算法 n个人围成一圈报数

/*设n个人围成一圈，标号为0..n-1，从第一个人开始依次从1到k循环报数，当报到k的时候此人出圈。
设J(n, k, i)表示第i个出圈的人的标号。

定理一:
J(n, k, 1) = (k-1) mod n, (n >= 1, k >= 1)             ………… （1）
证明：
由定义直接得证。		Q.E.D.

定理二：
J(n+1，k, i+1) = (k + J(n, k, i)) mod (n+1),  (n >= 1, k >= 1, 1<= i <= n) ………… （2）
证明：
设J(n, k, i) = g，因此如果有n个人，从0开始报号，第i个出圈的标号为g。现在考虑J(n+1, k,i+1)，
因为J(n+1, k, 1) = (k-1) mod (n+1)，即第一步的时候删除数字(k-1) mod (n+1)，第二步的时候从数
字k开始数起。因而问题变为了找到剩下的n个数字中从k开始数起被删除的第i个数字
（注意这时(k-1) mod (n+1)已经被删除了），而这恰好就是(g+k) mod (n+1)，(2)成立。 */
#include <iostream>
using namespace std;
int josephus(int n, int k, int i)
{
	if(i == 1)
		return (k - 1) % n;
	else
		return (josephus(n - 1, k, i - 1) + k) % n;
}

void main()
{
	cout<<"输入人数:";
	int n;
	cin>>n;
	cout<<"输入报数:";
	int k;
	cin>>k;
	for(int i = 0; i < n; i++)
		cout<<josephus(n, k,  i+1)<<endl;
}