POJ——3517

　　题目链接：http://poj.org/problem?id=3517

　　其实基本就是约瑟夫环问题，最终accepted的answer是看过相关资料才写出来的：

　　无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，

当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:

k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2 并且从k开始报0。现在我们把他们的编号做一下转换：

k --> 0

k+1 --> 1

k+2 --> 2

... ...

k-2 --> n-2

k-1 --> n-1

　　变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：

例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！

变回去的公式很简单，相信大家都可以推出来：

x=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！

代码：Accepted：

 1 #include<iostream>
 2 #define MAX 100
 3 
 4 using namespace std;
 5 
 6 int main(){
 7     int n = 1, k = 1, m = 1, cnt =0;
 8     int rel[MAX] = { 0 };
 9     while((n!=0) && (k!=0) && (m!=0))
10     {
11         cin >> n >> k >> m;
12          if((n!=0) && (k!=0) && (m!=0))
13         {
14             int f=0;
15             for(int i=2;i<n;i++)
16                 f=(f+k)%i;
17             f=(f+m)%n;
18             rel[cnt] = f+1;
19             cnt++;
20         }
21     }
22     for(int i = 0;i < cnt;i++)
23     {
24         cout << rel[i] << endl;
25     }
26     return 0;
27 }

　　我用链表写的，总超时，后面我对其进行了很多优化，也通不过，我怀疑只能通过数学解法做，也列出来吧

　　链表的约瑟夫问题太有名了，以至于我神马都没想，就直接用链表做了

 1 #include <iostream>
 2 #define MAX 100
 3 using namespace std;
 4 
 5 typedef struct node
 6 {
 7     int num;
 8     node* nxt;
 9 }node;
10 typedef node* Lst;
11 
12 int Final(int n, int k, int m);
13 
14 int main()
15 {
16     int n = 1, k = 1, m = 1, cnt =0;
17     int rel[MAX] = { 0 };
18     while((n!=0) && (k!=0) && (m!=0))
19     {
20         cin >> n >> k >> m;
21         if((n!=0) && (k!=0) && (m!=0))
22         {
23             rel[cnt] = Final(n,k,m);
24             cnt++;
25         }
26 
27     }
28 
29     for(int i = 0;i < cnt;i++)
30     {
31         cout << rel[i] << endl;
32     }
33 
34      /*for(int i = 0; i < 2*n;i++)
35     {
36         cout << head->num<<endl;
37         head = head->nxt;
38     }*/
39 
40     return 0;
41 }
42 int Final(int n, int k, int m)
43 {
44     Lst L, head, tmp;
45     L = new node;
46     L->nxt = L;
47     head = L;
48     L->num = 1;
49 
50     for(int i = 1; i < n;i++)
51     {
52         //Insert(L, i+1)
53         tmp = new node;
54         tmp->num = i+1;
55         head->nxt = tmp;
56         tmp->nxt = L;
57         head = tmp;
58         //cout << head->num << " \t";
59     }
60     int stonecnt = n;
61     head = L;
62     for(int i = 0;i < (m-1)%n; i++)
63     {
64         tmp =head;
65         head = head->nxt;
66     }
67     stonecnt--;
68     Lst del = head;
69     head = head->nxt;
70     tmp->nxt = head;
71     delete del;
72     while(stonecnt > 1)
73     {
74         for(int i = 0;i < (k-1)%stonecnt; i++)
75         {
76             tmp =head;
77             head = head->nxt;
78         }
79         stonecnt--;
80         del = head;
81         head = head->nxt;
82         tmp->nxt = head;
83         delete del;
84     }
85     int rel = head->num;
86     delete head;
87     return rel;
88 }