随笔-80  评论-24  文章-0  trackbacks-0
之前写过好多次了,再来一遍吧,先写一个循环链表实现的方式。
 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 *= r, *= 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 == 1return 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 == 1return 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)  编辑 收藏 引用 所属分类: 算法基础

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理