约瑟夫环问题

View Code

 1 #include <iostream>
 2 #include <list>
 3 using namespace std;
 4 // 约瑟夫环问题
 5 // 问题描述：将m个孩子从0到m-1编上号，按序号围坐成一个圈，从0号孩子开始数，
 6 // 每数到n-1时，被数到的孩子即离开圈子，然后从下一个孩子开始，再从0开始数，
 7 // 如此不断地数下去，直到孩子都出圈。问题孩子的出圈秩序。
 8 
 9 typedef struct List // 循环链表
10 {
11     int data;
12     struct List *next;
13 }List;
14 
15 void  main()
16 {
17     int m,n;
18     cin >> m >> n;
19     
20     if(n > m ) return ; // 完整性判断
21     
22     List *head,*q,*p; // 建立循环链表
23     for(int i=0;i<m;i++)
24     {
25         p = new List;
26         if(p != NULL)
27         {
28             p->data = i+1;
29             p->next = NULL;
30             if(i == 0)
31             {
32                 head = p;
33                 q = p;
34             }
35             else
36             {
37                 q->next = p;
38                 q = p;
39             }
40         }        
41     }
42     if(q->next == NULL) // 循环的建立
43     { 
44         q->next = head;
45     }
46 
47     // 删除节点，完成出圈的操作
48     p = head;
49     while(p->next != p)
50     {
51         for(int i=0;i<n;i++)
52         {
53             q= p;
54             p = p->next;
55         }
56         cout << p->data << endl;
57         q->next = p->next;
58         p = p->next;
59     }
60 
61     cout << p->data << endl;
62 
63 }

输入：5 2

输出：

以上是直接的求解方法。建立循环链表，然后通过指针的后继后继，然后是删除指向的节点，最后完成操作。

还有一个动态规划的算法实现。见该链接：http://www.cnblogs.com/EricYang/archive/2009/09/04/1560478.html

2、动态规划方法

 1 #include <stdio.h>
 2  int main()
 3  {
 4      int n, m, i=1, s = 0; // i=1时，s=0
 5      printf ("N M = ");
 6      scanf("%d%d", &n, &m);
 7      for (i = 2; i <= n; i++)
 8      {
 9          s = (s + m) % i;// 递推式
10      }
11      printf ("\nThe winner is %d\n", s+1);
12  }