之前写过好多次了，再来一遍吧，先写一个循环链表实现的方式。
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 阅读(145)
评论(0) 编辑 收藏 引用 所属分类:
算法基础