Josephus問題的不同實現方法與總結

  1 /************************************************************************/  2 /*                   Josephus問題——數組實現                           */  3 /************************************************************************/  4 #include <stdio.h>  5 #include <malloc.h>  6   7 int Josephus(int times, int number, int id){  8     int *a;  9     int i, count = 0, t = 0; 
 10     a = (int *)malloc(sizeof(int) * number); 11  12     for(i = 0; i < number; i++) 13         a[i] = i + 1;             // 數組a用于儲存每個元素的編號 14     i = id - 1; 15  16     while(count < number - 1){ 17         if(a[i] != 0) 18             t++; 19         if(t == times){ 20             t = 0; 
 21             count++; 22             printf("%4d", a[i]); 23             a[i] = 0;                // 當該元素被剔除時，該數組元素置為0 24         } 25         i++; 26         if(i == number) 27             i = 0; 28     } 29     for(i=0;i<number;i++) 30         if(a[i]!=0) 31         { 32             printf("\n最后剩余的結點是:%4d\n",a[i]); 33             return; 34         } 35  36 } 37  38 int main(){ 39     int times, number, id; 40     printf("請輸入總人數："); 41     scanf("%d", &number); 42     printf("請輸入報數周期:"); 43     scanf("%d", &times); 44     printf("請輸入開始報數的編號："); 45     scanf("%d", &id); 46     Josephus(times, number, id); 47  48     return 0; 49 } 50  51 /************************************************************************/ 52 /* 總結： 53         優點為可以得出每次被剔除的元素編號 54         缺點為內存空間占用較大，沒有數學歸納法快速                        */ 55 /************************************************************************/ 56  57  58 /************************************************************************/ 59 /*                   Josephus問題——循環鏈表實現                       */ 60 /************************************************************************/ 61 #include <stdio.h> 62 #include <malloc.h> 63  64 typedef struct LNode 65 { 66     int data; 67     struct LNode *next; 68 }LNode,*Linkhead; 69 void Josephus(int m,int n,int k) 70 { 71     Linkhead p,r,head = NULL; 72     int i; 73     for(i = 1;i <= n;i++) 74     { 75         p = (Linkhead)malloc(sizeof(LNode));//申請一個新的鏈結點 76         p->data = i;//存放第i個結點的編號 77         if(head == NULL) 78             head = p; 79         else 80             r->next = p;      // 因為Insert和Del操作都需要之前一個節點的地址，故用r來存儲。其作用類似棧的top 81         r = p; 82     } 83     p->next = head;//至此，建立一個循環鏈表 84  85     p = head; 86     for(i = 1;i < k;i++) 87     { 88         r=p; 89         /*請注意，此行不是多余的，因為當k!=1,但m=1時如果沒有這條語句，此時刪除動作無法完成*/ 90         p=p->next; 91     }        //此時p指向第1個出發結點 92  93     while(p->next != p) 94     { 95         for(i = 1;i < m;i++) 96         { 97             r = p; 98             p = p->next; 99         }                        //p指向第m個結點,r指向第m-1個結點100         r->next = p->next;        //刪除第m個結點101         printf("%4d",p->data);    //依次輸出刪除結點的編號102         free(p);                //釋放被刪除結點的空間103         p = r->next;            //p指向新的出發結點104     }105     printf("\n最后剩余的結點是:%4d\n",p->data);//輸出最后一個結點的編號106 }107 108 int main(){109     int times, number, id;110     printf("請輸入總人數：");111     scanf("%d", &number);112     printf("請輸入報數周期:");113     scanf("%d", &times);114     printf("請輸入開始報數的編號：");115     scanf("%d", &id);116     Josephus(times, number, id);117 118     return 0;119 }120 121 /************************************************************************/122 /* 總結：123         優點為可以得出每次被剔除的元素編號124         缺點為相較數組方法需要更多的計算量125         總體而言與數組方法相差無幾                                        */126 /************************************************************************/127 128 /************************************************************************/129 /*             Josephus問題——數學歸納法直接計算                       */130 /************************************************************************/131 #include <stdio.h>132 int main() {  
133     int answer = 0;  
134     int times, number, i, id;    // number為環內總元素個數，times為報數周期， id為從第幾個元素開始報數135     printf("請分別輸入總人數和循環次數：");136     scanf("%d %d", &number, &times);137     printf("起始報號者的編號：");138     scanf("%d", &id);139     for(i = 1; i <= number; i++) {  
140         answer = (answer + times) % i;      // 核心算法，利用數學歸納法得出141     }142     if(answer + id == number)143         printf("Survial: %d\n", number);    // 防止當幸存者為最后一個編號時輸出0的情況144     else145         printf("Survival: %d\n",(answer + id) % number);  
146         // 這邊利用number對answer進行取余操作以防止編號數值超過最大編號（溢出）147     148     return 0;149 }

                                           對于Josephus問題有兩個地方是可以進行優化的。 (總人數為N，編號為從0~N-1；經過M次報數去除一個成員，剩余成員個數為numleft， 記M%numleft為mPrime)

　1、被移除的成員離上一個成員之間的距離是M%numleft-1（報數次為M%numleft）.當M大于N時，該計算方式將節省大量時間
 2、當mPrime大于numleft的時候可以反向遍歷該表來查找要去除的成員。這樣可以節省時間。同樣這也就要求了該表必須是一個雙向表才行。（即含有Previous方法）
 　該算法實現原理即為：

　　第一輪，必定為編號M%N-1的成員被去除，第二輪為在第一輪的基礎上即從編號為M%N的成員開始正移mPrime-1個單位（或者反移numleft-mPrime-1個單位）。若將M%N即為編號0，開始重新編號，那么第二輪被刪除的成員編號便是M%（numleft）-1，由此可得該輪要被刪除的成員與上一輪去除成員之間的距離為M%numleft，這里可利用迭代器來實現。

  這里我們便可以得到成員編號與該輪成員數目的關系是：（n表示該輪所剩余的成員數目，Index（n）表示該輪成員的編號（從0開始））
   Index(n) = (Index(n - 1) + m) % n。
    那么按照這個過程，我們這樣一直移除元素下去，肯定能夠找到最后一個被移除的元素。
    這個元素則對應只有一個元素的環，很顯然，它的值為0。也就是Index(1) = 0。
    對于這個元素的索引，它對應兩個元素的索引是多少呢？
   按照前面的過程，我們倒推回去就是了。Index(2) = (Index(1) + m) % 2。
   那么對應3個，4個元素的呢？我們這樣一路繼續下去就可以找到對應到n個元素的索引了。
    所以，我們發現了一個有意思的數學歸納關系：
    f(1) = 0,  f(n) = (f(n - 1) + m) % n。
    按照這個關系，我們可以得到最后一個被取出來的元素對應到n個元素的環里的索引值。 

至此，我們可以發現，利用count計數從而刪除成員的方法與此相比起來遜色不少，故之后我們將采用此方法來解決問題。