View Code of Problem 80

#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; 
}