好久沒有看有關(guān)算法的問題了底哗，今天廢了不少勁岁诉，再感嘆一句：要想學(xué)好算法就要常練習，沒什么捷徑可走跋选。廢話不多說涕癣，如下：
問題描述：有m個人,圍成一個環(huán)，編號為 0前标、1坠韩、2、3炼列、只搁、、m-1俭尖，從第一個人開始循環(huán)報數(shù)氢惋，假設(shè)數(shù)到n的那個人出列，然后從下一個人繼續(xù)數(shù)數(shù)目溉，數(shù)到n出列明肮，以此循環(huán)，最后那個人為勝利者缭付，求勝利者的編號。
分析如下：
設(shè)m為人的個數(shù) n為要數(shù)的數(shù) k為從第幾個人開始數(shù).
第一次的數(shù)列循未，記為A:
0 1 2 3 4 5 6 7 8 9 陷猫、、的妖、n%m k绣檬、、嫂粟、m-2 m-1
假設(shè)第一次出列了一個人娇未，則編號肯定為n%m-1（減1因為從零開始）。k=n%m星虹，第一次出列后的數(shù)列為:
0 1 2 3 4 5 6 7 8 9 零抬、、宽涌、k平夜、、卸亮、m-2 m-1
第二次從k開始數(shù)數(shù)那么可以組成新的數(shù)列忽妒，記為數(shù)列B:
k->0
k+1->1
k+2->2
k+3->3
、
、
段直、
k-3->m-3
k-2->m-2
如果我們知道了數(shù)列B的最終勝利者是的編號是x吃溅，那么x在原來數(shù)列A中的編號是多少呢？很容易算出來：(x+k)%m,而k=n%m,替換后為（x+n%m）%m=(x+n)%m鸯檬，(x+n)%m為數(shù)列A的勝利者罕偎。那么x又該如何求呢，我們可以求數(shù)列C京闰，就這樣這么以次類推颜及。直到只有一個人時，勝利者的編號肯定為0.
假設(shè)f(y)為勝利者：則有
f(1)=0俏站；
f(2)=（f(1)+n）%2；
f（y）= (f（y-1）+n)%y; y為數(shù)列的人數(shù),n為要數(shù)的數(shù)
以下為編程實現(xiàn)痊土，將f(y)替換為number肄扎，y替換為i
/***********************************************************************
**m總?cè)藬?shù)，則標號為0~m-1 n為要數(shù)的數(shù)
**成功返回序號1~m赁酝，失敗返回-1
***********************************************************************/
int winner(int m, int n)
{
int i;
int number;
if (m <= 0 || n <= 0) {
return -1;
}
number = 0; /* 當只有一個人時，編號為0的出圈 */
for (i = 2;i <= m;i++) { /* 循環(huán)m-1次將剩下一個人 */
number = (number + n % i) % i; /* 這樣寫易理解衡载，或(number+n)%i */
}
return number + 1; /* 程序從0編號隙袁，返回時應(yīng)+1 */
}
