poj1012.Joseph(数学推论）

 1 #include <stdio.h>
 2 
 3 int main()
 4 {
 5     //freopen ("a.txt" , "r" , stdin ) ;
 6     int people[50] = {0}, k, Joseph[14] = {0};//Joseph用于打表，不然超时
 7     while(scanf("%d", &k) != EOF && k != 0)
 8     {
 9         if (Joseph[k] != 0)
10         {
11             printf("%d\n", Joseph[k]);
12             continue;
13         }
14         int n = 2 * k;
15         int m = 1;
16         people[0] = 0;//people[0] = 0表示编号从0开始
17         for (int i = 1; i <= k; i++)
18         {
19             //每次枚举完毕将剩下的人按从0到n - i编号，只要好人没有杀掉，则前面k - 1个编号是不变的
20             people[i] = (people[i - 1] + m - 1) % (n - i + 1);
21           //  printf ("[%d] = %d , " , i , people[i] ) ;
22             if (people[i] < k)//第k个人的编号为k - 1,所以这里是<而不是<=
23             {
24                 i = 0 ;
25                 m++;
26             }
27         }
28        // printf ("\n") ;
29         Joseph[k] = m;
30         printf("%d\n", m);
31     }
32     return 0;
33 }