#include<stdio.h> // 本题属于 :约瑟夫环问题 // 法2:动态规划的的递推解法 //法1:可以用数组模拟循环链表,从而求解 int main() { int n; while (scanf("%d", &n) != EOF) { if (n == 0) break; // 1~n个人,我们把第一个编号为1,最后一个人编号为n long long dp[n]; dp[1] = 1; //当i=1,即只有一个人的时候,编号为1; 这是初始情况 dp[2] = 2; //当有两个人的时候,最后留下来的是第二个人,第二个人编号为2 for(int i = 3; i <=n; i++){ dp[i] = (dp[i-1] + 3) % i; // 递推公式为 f(n) = (f(n-1) + m) % n,此处m=3 } printf("%lld\n", dp[n]); } return 0; } |
Double click to view unformatted code.