天天看点

约瑟夫环的链表解法和数学解法

   约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的,他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达伯特城达47天之久,在城市沦陷之后,他和40名死硬的将士在附近的一个洞穴中避难。在那里,这些叛乱者表决说“要投降毋宁死”。于是,约瑟夫建议每个人轮流杀死他旁边的人,而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签,并且,作为洞穴中的两个幸存者之一,他说服了他原先的牺牲品一起投降了罗马。

约瑟夫环问题的具体描述是:设有编号为1,2,……,n的n(n>0)个人围成一个圈,从第1个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈,……,如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。 

解法一:

[cpp]  view plain copy

约瑟夫环的链表解法和数学解法
约瑟夫环的链表解法和数学解法
  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. typedef struct Node  
  4. {  
  5.        int data;  
  6.        struct Node *next;  
  7. } Node;  
  8. void JOSEPHUS(int total, int from, int count)  
  9. {  
  10.     // pcur为当前结点,pre为辅助结点,指向pcur的前驱结点,head为头节点  
  11.     Node *pcur, *pre, *head;  
  12.     head = NULL;  
  13.     int i;  
  14.     // 建立循环链表  
  15.     for(i = 1; i <= total; i++)  
  16.     {  
  17.         pcur = (Node *)malloc(sizeof(Node));  
  18.         pcur->data = i;  
  19.         if(NULL ==head)  
  20.          {  
  21.            head = pcur;  
  22.          }  
  23.         else  
  24.          {  
  25.             pre->next = pcur;  
  26.          }  
  27.          pre = pcur;  
  28.     }  
  29.     pcur->next = head;      // 尾节点连到头结点,使整个链表循环起来  
  30.     pcur = head;            // 使pcur指向头节点  
  31.     // 把当前指针移动到第一个报数的人,即第k位的下一位  
  32.     for(i = 1; i < from; i++)  
  33.     {  
  34.         pre = pcur;  
  35.         pcur = pcur->next;  
  36.     }  
  37.     // 循环地删除队列结点,每隔m-1个结点删一个  
  38.     while(pcur->next != pcur)  
  39.     {  
  40.         for(i = 1; i < count; i++)  
  41.         {  
  42.             pre = pcur;  
  43.             pcur = pcur->next;  
  44.         }  
  45.         pre->next =pcur->next;  
  46.         printf("deletenumber: %d\n", pcur->data);  
  47.         free(pcur);  
  48.         pcur = pre->next;  
  49.     }  
  50.     printf("Thelast one is No.%d\n", pcur->data);  
  51. }  
  52. int main()  
  53. {  
  54.        // 总共有13人,从第1位开始报数,每隔两位踢出1个。  
  55.        JOSEPHUS(13,1,3);  
  56. }  

运行结果:

delete number: 3

delete number: 6

delete number: 9

delete number: 12

delete number: 2

delete number: 7

delete number: 11

delete number: 4

delete number: 10

delete number: 5

delete number: 1

delete number: 8

Thelast one is No.13

解法二:

假设下标从0开始,0,1,2 … m-1共m个人,从第0个开始报数,报到k则此人从环出退出,问最后剩下的一个人的编号是多少?

现在假设m=10

01 2 3 4 5 6 7 8 9    k=3

第一个人出列后的序列为:

01 3 4 5 6 7 8 9

即:

34 5 6 7 8 9 0 1(*)

我们把该式转化为:

01 2 3 4 5 6 7 8 (**)

则你会发现: ((**)+3)%10则转化为(*)式了

也就是说,我们求出9个人中第9次出环的编号,最后进行上面的转换就能得到10个人第10次出环的编号了。这样,9个人中第9次出环(或10个人中第10次出环)的编号,就是最后的结果。

设f(m,k,i)为m个人的环,报数为k,第i个人出环的编号,则f(10,3,10)是我们要的结果

当i=1时,  f(m,k,i) = (m+k-1)%m(这里减1是因为从0开始计数)

当i!=1时,  f(m,k,i)= ( f(m-1,k,i-1)+k )%m

源程序如下:

[cpp]  view plain copy

约瑟夫环的链表解法和数学解法
约瑟夫环的链表解法和数学解法
  1. #include <stdio.h>  
  2. int fun(int m,int k,int i)  
  3. {  
  4.        if(1 == i)  
  5.        {  
  6.          return (m + k - 1) % m;  
  7.        }  
  8.        else  
  9.        {  
  10.          return (fun(m - 1, k, i - 1) + k) % m;  
  11.        }  
  12. }  
  13. int main(int argc, char* argv[])  
  14. {  
  15.        for(int i = 1; i <= 13; i++)  
  16.        {  
  17.          printf("第%d次出环:%d\n", i, fun(13, 3, i));  
  18.        }  
  19.        return 0;  
  20. }  

运行结果:

第1次出环:2

第2次出环:5

第3次出环:8

第4次出环:11

第5次出环:1

第6次出环:6

第7次出环:10

第8次出环:3

第9次出环:9

第10次出环:4

第11次出环:0

第12次出环:7

第13次出环:12

zz  http://blog.csdn.net/haishu_zheng/article/details/17220429