之前寫過好多次了，再來一遍吧，先寫一個循環鏈表實現的方式。
1 #include <cstdio>
2 #include <cstdlib>
3
4 typedef struct node
5 {
6 int data;
7 struct node *next;
8 }Node;
9
10 Node *create(Node *&r, int n, int k);
11 void Josephus(Node *r, int m);
12
13 int main()
14 {
15 int n, k, m;
16 Node *Root;
17
18 scanf("%d%d%d", &n, &k, &m);
19 create(Root, n, k);
20 Josephus(Root, m);
21 return 0;
22 }
23
24 Node *create(Node *&r, int n, int k)
25 {
26 Node *p;
27 r = (Node *)malloc(sizeof(Node));
28 p = r;
29 p->data = k;
30 p->next = NULL;
31
32 for (int i = (k % n) + 1; i != k; i = (i % n) + 1)
33 {
34 p->next = (Node *)malloc(sizeof(Node));
35 p = p->next;
36 p->data = i;
37 p->next = r;
38 }
39 }
40
41 void Josephus(Node *r, int m)
42 {
43 int i;
44 Node *p = r, *q = r->next;
45
46 while (q != q->next)
47 {
48 for (i = 1; i < m; ++i)
49 {
50 p = q;
51 q = q->next;
52 }
53
54 p->next = q->next;
55 printf("%d\n", q->data);
56 free(q);
57 q = p->next;
58 }
59
60 printf("%d\n", q->data);
61 free(q);
62 }
63
其實比起數學方法，循環鏈表就是純模擬，思想相當簡單，就是考察循環鏈表的基本操作。
下面看一下數學方法：
首先看首次刪除節點后序列變為
0, 1, 2, ..., k - 2, k, k + 1, ..., n - 1
這里之所以沒有用m表示是因為如果m比n大那么首次刪除的節點編號將不會是m - 1，當時用k表示不影響我們的結果
當下一次再從k開始進行的時候k節點的編號相當于新一輪的0號，所以有如下對應關系：
0, 1, 2, ..., k - 2, k, k + 1, ..., n - 1
n - k, n - k + 1, n - k + 2, ..., n - 2, 0, 1, ..., n - k - 1
因此可以得知，在第二輪的新的編號為t的節點的原始編號實際為 (t + k) % n
所以我們就得到了遞推公式：
joseph(n, m) = (joseph(n - 1, m) + k) % n;
由于k = m % n，所以遞推公式變為：
joseph(n, m) = (joseph(n - 1, m) + (m % n)) % n = (joseph(n - 1, m) + m) % n
如果編號不是從0開始而是從1開始呢？
這也好辦，我們再看一遍對應關系：
1, 2, 3, ..., k - 1, k + 1, k + 2, ..., n
n - k + 1, n - k + 2, n - k + 3, ..., n - 1, 1, 2, ..., n - k
因此，第二輪新的編號為t的節點的原始編號實際為 (t + k - 1) % n + 1
所以遞推公式變為：
joseph(n, m) = (joseph(n - 1, m) + m - 1) % n + 1
對應的代碼都相當簡單，如下：
1 //start at 0
2 int joseph_start_at_0(int n, int m)
3 {
4 assert(n > 0);
5 assert(m > 0);
6
7 if (n == 1) return 0;
8 return (joseph_start_at_0(n - 1, m) + m) % n;
9 }
10
11 //start at 1
12 int joseph_start_at_1(int n, int m)
13 {
14 assert(n > 0);
15 assert(m > 0);
16
17 if (n == 1) return 1;
18 return (joseph_start_at_1(n - 1, m) + m - 1) % n + 1;
19 }
posted on 2011-05-03 13:02
myjfm 閱讀(152)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎