约瑟夫问题
问题：
n个人（编号0~(n-1）），从0开始报数，报到（k-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。
1.循环链表模拟
#include <iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
int main()
{
int K,N;//N个人
cout<<"input K and number of people.\n";
cin>>K>>N;
if ( K<=0||N<1 ){
cout<<"k should >=1\n";
return 0;
}
else if( N==1) {
cout<<"remainer is "<<1<<endl;
return 0;
}
else{
Node* start = new Node;
start->data = 1;
start->next = NULL;
Node* preNode = start;
//构造循环链表
Node* temp;
for( int i=2; i<=N; ++i ){
temp = new Node;
temp->data = i;
preNode->next = temp;
preNode = temp;
}
temp->next = start;//将尾部指针指向头部
Node* p = start;
int realk = K;
while( N>1 ){
realk = K%N;
if( realk==0 )
realk =N;
Node* todele;//指向要删除的节点
Node* predele;//指向要删除节点的前一个节点
//将p指向要删除节点的前一个节点
if( 1==realk ){
Node* t = p;
while( p->next!=t )
p = p->next;
}
else{
for( int cnt=0; cnt<realk-2; ++cnt )
p=p->next;
}
predele = p;
todele = predele->next;
cout<<"to delete is : "<<todele->data<<endl;
predele->next = todele->next;
delete todele;
--N;
//p指向下一个，开始另外一轮
p = p->next;
}
cout<<"remainer is "<<p->data<<endl;
delete p;
}
return 0;
}
2.递归
#include <iostream>
using namespace std;
/*
我们知道第一个人（编号一定是( m mod n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=(m mod n)+1的人开始）：
k+1 k+2 ... n-2,n-1,0,1,2,... k-2,k-1
并且从k开始报0。
现在我们把他们的编号做一下转换：
k+1 --> 0
k+2 --> 1
...
...
k-1 --> n-2
变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x2 = [x+(k+1)] mod n
如何知道（n-1）个人报数的问题的解？对，只要知道（n-2）个人的解就行了。（n-2）个人的解呢？当然是先求（n-3）的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
递推公式
f[1]=0;
f=[ f[i-1]+(k+1) ] mod i; (i>1）
每传递k次，就淘汰拿着土豆的那个人
*/
int main()
{
int f( int num , int k);
int k,n;//n个人，
cin >> k >> n;
cout<<"递归，remainer is ";
cout<<f( n, k )+1<<endl;
cout<<"迭代法: \n";
int s=0;
for( int i=2; i<=n; i++ ){
s = (s+k)%i;
}
cout<<s+1<<endl;
return 0;
}
int f( int num ,int k ){
if( num==1 )
return 0;
return ( f(num-1,k)+k )%num;
}
3. 递归2
在每一轮报数过程中，都有 N/K 个人退出了队伍，比如N = 10， K = 3，第一轮有N / K = 3三个人退出；
上述第一种方法每次递归的步长为 1 ，这里我们利用上述关系，建立一个步长为 N / K 的递归过程；
需要注意的是，当N减少到N = K的时候就需要使用第一种递归进行计算；
N > K时的递归公式为：
ret < N mod K: ret = ret - (N mod K) + N
ret >= N mod K: ret = ret - (N mod K) + (ret - N mod K) / (K - 1)
解释一下（比较丑哈哈）：
比如，就上面这个图，在淘汰掉2，5后，还剩5个人。从6号开始重新从0开始编号。那么这时候胜利者就有两种情况：
一：胜利者的新编号小于N%K，对这个图而言，也就是处于0或1的位置，这时推算它在原来序列中的编号 = 新编号 - N%K + N； 比如0是胜利者，那么它原来序列中的编号就为：0-7%3+7 = 6。
二：胜利者的新编号不小于N%K，对这个图，也就是处于2，3，4，5（新编号）的位置，这时我们再来推算它在原序列中的编号，先减去末尾的（N%K），免受其影响，这样，2，3，4，5就变成0，1，2，3。还要考虑被淘汰的元素对新编号的影响（比如原序列中2号的淘汰对新编号中4，5号产生影响），应该减去。也就是 - (新编号- N mod K) / (K - 1)。
#include <iostream>
using namespace std;
int josephus(int n, int k)
{
int ret;
if(n == 1)
return 0;
//n < k的时候使用第一种递归算法
if(n < k)
{
int ret = 0;
for(int i = 2; i <= n; ++i)
ret = (ret + k) % i;
return ret;
}
//执行递归过程
ret = josephus(n-n/k,k);
if(ret < n % k)
{
ret = ret - n % k + n;
}
else
{
ret = ret - n % k + (ret - n % k ) / (k - 1);
}
return ret;
}
int main()
{
int num;
cin >> num;
while(num--)
{
int n, k;
cin >> n >> k;
cout << josephus(n, k)+1 << endl;
}
return 0;
}