Description
Let’s play a stone removing game.
Initially, n stones are arranged on a circle and numbered 1, …, n clockwise (Figure 1). You are also given two numbers k and m. From this state, remove stones one by one following the rules explained below, until only one remains. In step 1, remove stone m. In step 2, locate the k-th next stone clockwise from m and remove it. In subsequent steps, start from the slot of the stone removed in the last step, make k hops clockwise on the remaining stones and remove the one you reach. In other words, skip (k − 1) remaining stones clockwise and remove the next one. Repeat this until only one stone is left and answer its number. For example, the answer for the case n = 8, k = 5, m = 3 is 1, as shown in Figure 1.
http://blog.csdn.net/code_or_code/article/details/38702275Initially, n stones are arranged on a circle and numbered 1, …, n clockwise (Figure 1). You are also given two numbers k and m. From this state, remove stones one by one following the rules explained below, until only one remains. In step 1, remove stone m. In step 2, locate the k-th next stone clockwise from m and remove it. In subsequent steps, start from the slot of the stone removed in the last step, make k hops clockwise on the remaining stones and remove the one you reach. In other words, skip (k − 1) remaining stones clockwise and remove the next one. Repeat this until only one stone is left and answer its number. For example, the answer for the case n = 8, k = 5, m = 3 is 1, as shown in Figure 1.
 Initial state |  Step 1 |  Step 2 |  Step 3 |  Step 4 |
 Step 5 |  Step 6 |  Step 7 |  Final state |
数字1到n成环，先叉数字m，往下数k个，直到最后只有一个数字，输出它。
http://www.bkjia.com/ASPjc/866918.html
经典的约瑟夫环问题嘛。有点小小的变形而已。给你N个人围成一个环（编号1~N），从第M个人开始，每隔K个人报一次数，报数的人离开该环。
求最后剩下的人的编号。
约瑟夫问题的数学递推解法：
（1）第一个被删除的数为 (m - 1) % n。
（2）假设第二轮的开始数字为k，那么这n - 1个数构成的约瑟夫环为k, k + 1, k + 2, k +3, .....,k - 3, k - 2。做一个简单的映射。
k -----> 0
k+1 ------> 1
k+2 ------> 2
...
...
k-2 ------> n-2
这是一个n -1个人的问题，如果能从n - 1个人问题的解推出 n 个人问题的解，从而得到一个递推公式，那么问题就解决了。假如我们已经知道了n -1个人时，最后胜利者的编号为x，利用映射关系逆推，就可以得出n个人时，胜利者的编号为 (x + k) % n。其中k等于m % n。代入(x + k) % n <=> (x + (m % n))%n <=> (x%n + (m%n)%n)%n <=> (x%n+m%n)%n <=> (x+m)%n
（3）第二个被删除的数为(m - 1) % (n - 1)。
（4）假设第三轮的开始数字为o，那么这n - 2个数构成的约瑟夫环为o, o + 1, o + 2,......o - 3, o - 2.。继续做映射。
o -----> 0
o+1 ------> 1
o+2 ------> 2
...
...
o-2 ------> n-3
这是一个n - 2个人的问题。假设最后的胜利者为y，那么n -1个人时，胜利者为 (y + o) % (n -1 )，其中o等于m % (n -1 )。代入可得 (y+m) % (n-1)
要得到n - 1个人问题的解，只需得到n - 2个人问题的解，倒推下去。只有一个人时，胜利者就是编号0。下面给出递推式：
f [1] = 0;
f [ i ] = ( f [i -1] + m) % i; (i>1)
- int n,m,k;
- while(~scanf("%d%d%d",&n,&k,&m))
- {
- if(n==0 && m==0 && k==0)
- break;
- int s=0;
- for(int i=2;i<=n-1;i++)
- s=(s+k)%i;
- printf("%d\n",(s+m)%n+1);
- }
- struct Link{
- int data;
- Link* next;
- Link* pre;
- }node[10001];
- int main()
- {
- int n,k,m;
- while(scanf("%d%d%d",&n,&k,&m),n||k||m)
- {
- for(int i=1;i<=n;i++) //构建双向循环链表
- {
- node[i].data=i;
- node[i].next=(i==n)?&node[1]:&node[i+1];
- node[i].pre=(i==1)?&node[n]:&node[i-1];
- }
- Link* p=&node[m];
- p->pre->next=p->next;
- p->next->pre=p->pre;
- p=p->next;
- int loop=k;
- int t=1;
- while(p->next!=p)
- {
- if(k%(n-t)==0) //优化，若无会TLE
- loop=k;
- else
- loop=k%(n-t);
- for(int i=1;i<loop;i++)
- p=p->next;
- p->pre->next=p->next;
- p->next->pre=p->pre;
- p=p->next;
- t++;
- }
- printf("%d\n",p->data);
- }
- return 0;
- }
Read full article from 3517 -- And Then There Was One
