原来写过一篇关于约瑟夫问题的链表实现解法 ,刷九度题到http://ac.jobdu.com/problem.php?pid=1356 时,再次遇到这个问题,记下用递归思想解决约瑟夫问题的方法:
初始情况: 0, 1, 2 ......n-2, n-1 (共n个人)
第一个人(编号一定是(m-1)%n,设之为(k-1) ,读者可以分m<n和m>=n的情况分别试下,就可以得出结论) 出列之后,
剩下的n-1个人组成了一个新的约瑟夫环(以编号为k==m%n的人开始):
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ...,k-3, k-2
现在我们把他们的编号做一下转换:
x‘ -> x
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗!
0 -> k
1 -> k+1
2 -> k+2
...
...
n-2 -> k-2
变回去的公式 x‘=(x+k)%n
那么,如何知道(n-1)个人报数的问题的解?只要知道(n-2)个人的解就行了。(n-2)个人的解呢?只要知道(n-3)的情况就可以了 ---- 这显然就是一个递归问题:
令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果就是f[n]
递推公式
f[1]=0;
f[i]=(f[i-1]+k)%i = (f[i-1] +m%i) % i = (f[i-1] + m) % i ; (i>1)
下面分别用递归与迭代实现算法(http://ac.jobdu.com/problem.php?pid=1356):
1.递归:
#include <stdio.h> int josephus(int n, int m) { if(n == 1) { return 0; } else { return (josephus(n-1, m) + m) % n; } } int main() { int n, m; while (scanf("%d", &n) == 1) { if (!n) { break; } scanf("%d", &m); int result = josephus(n, m); printf("%d\n", result+1); } return 0; }
2.迭代:
#include <stdio.h> int main() { int n, m, i, result; while (scanf("%d", &n) == 1) { if (!n) { break; } scanf("%d", &m); result = 0; for (i = 2; i <= n; i++) { result = (result + m) % i; } printf("%d\n", result + 1); } return 0; }