網(wǎng)站建設(shè)、成都做網(wǎng)站的開發(fā)，更需要了解用戶，從用戶角度來建設(shè)網(wǎng)站，獲得較好的用戶體驗(yàn)。創(chuàng)新互聯(lián)多年互聯(lián)網(wǎng)經(jīng)驗(yàn)，見的多，溝通容易、能幫助客戶提出的運(yùn)營建議。作為成都一家網(wǎng)絡(luò)公司，打造的就是網(wǎng)站建設(shè)產(chǎn)品直銷的概念。選擇創(chuàng)新互聯(lián)，不只是建站，我們把建站作為產(chǎn)品，不斷的更新、完善，讓每位來訪用戶感受到浩方產(chǎn)品的價(jià)值服務(wù)。

  1 /************************************************************************/  2 /*                   Josephus問題——數(shù)組實(shí)現(xiàn)                           */  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;             // 數(shù)組a用于儲(chǔ)存每個(gè)元素的編號(hào) 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;                // 當(dāng)該元素被剔除時(shí)，該數(shù)組元素置為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最后剩余的結(jié)點(diǎn)是:%4d\n",a[i]); 33             return; 34         } 35  36 } 37  38 int main(){ 39     int times, number, id; 40     printf("請(qǐng)輸入總?cè)藬?shù)："); 41     scanf("%d", &number); 42     printf("請(qǐng)輸入報(bào)數(shù)周期:"); 43     scanf("%d", &times); 44     printf("請(qǐng)輸入開始報(bào)數(shù)的編號(hào)："); 45     scanf("%d", &id); 46     Josephus(times, number, id); 47  48     return 0; 49 } 50  51 /************************************************************************/ 52 /* 總結(jié)： 53         優(yōu)點(diǎn)為可以得出每次被剔除的元素編號(hào) 54         缺點(diǎn)為內(nèi)存空間占用較大，沒有數(shù)學(xué)歸納法快速                        */ 55 /************************************************************************/ 56  57  58 /************************************************************************/ 59 /*                   Josephus問題——循環(huán)鏈表實(shí)現(xiàn)                       */ 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));//申請(qǐng)一個(gè)新的鏈結(jié)點(diǎn) 76         p->data = i;//存放第i個(gè)結(jié)點(diǎn)的編號(hào) 77         if(head == NULL) 78             head = p; 79         else 80             r->next = p;      // 因?yàn)镮nsert和Del操作都需要之前一個(gè)節(jié)點(diǎn)的地址，故用r來存儲(chǔ)。其作用類似棧的top 81         r = p; 82     } 83     p->next = head;//至此，建立一個(gè)循環(huán)鏈表 84  85     p = head; 86     for(i = 1;i < k;i++) 87     { 88         r=p; 89         /*請(qǐng)注意，此行不是多余的，因?yàn)楫?dāng)k!=1,但m=1時(shí)如果沒有這條語句，此時(shí)刪除動(dòng)作無法完成*/ 90         p=p->next; 91     }        //此時(shí)p指向第1個(gè)出發(fā)結(jié)點(diǎn) 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個(gè)結(jié)點(diǎn),r指向第m-1個(gè)結(jié)點(diǎn)100         r->next = p->next;        //刪除第m個(gè)結(jié)點(diǎn)101         printf("%4d",p->data);    //依次輸出刪除結(jié)點(diǎn)的編號(hào)102         free(p);                //釋放被刪除結(jié)點(diǎn)的空間103         p = r->next;            //p指向新的出發(fā)結(jié)點(diǎn)104     }105     printf("\n最后剩余的結(jié)點(diǎn)是:%4d\n",p->data);//輸出最后一個(gè)結(jié)點(diǎn)的編號(hào)106 }107 108 int main(){109     int times, number, id;110     printf("請(qǐng)輸入總?cè)藬?shù)：");111     scanf("%d", &number);112     printf("請(qǐng)輸入報(bào)數(shù)周期:");113     scanf("%d", &times);114     printf("請(qǐng)輸入開始報(bào)數(shù)的編號(hào)：");115     scanf("%d", &id);116     Josephus(times, number, id);117 118     return 0;119 }120 121 /************************************************************************/122 /* 總結(jié)：123         優(yōu)點(diǎn)為可以得出每次被剔除的元素編號(hào)124         缺點(diǎn)為相較數(shù)組方法需要更多的計(jì)算量125         總體而言與數(shù)組方法相差無幾                                        */126 /************************************************************************/127 128 /************************************************************************/129 /*             Josephus問題——數(shù)學(xué)歸納法直接計(jì)算                       */130 /************************************************************************/131 #include <stdio.h>132 int main() {  
133     int answer = 0;  
134     int times, number, i, id;    // number為環(huán)內(nèi)總元素個(gè)數(shù)，times為報(bào)數(shù)周期， id為從第幾個(gè)元素開始報(bào)數(shù)135     printf("請(qǐng)分別輸入總?cè)藬?shù)和循環(huán)次數(shù)：");136     scanf("%d %d", &number, &times);137     printf("起始報(bào)號(hào)者的編號(hào)：");138     scanf("%d", &id);139     for(i = 1; i <= number; i++) {  
140         answer = (answer + times) % i;      // 核心算法，利用數(shù)學(xué)歸納法得出141     }142     if(answer + id == number)143         printf("Survial: %d\n", number);    // 防止當(dāng)幸存者為最后一個(gè)編號(hào)時(shí)輸出0的情況144     else145         printf("Survival: %d\n",(answer + id) % number);  
146         // 這邊利用number對(duì)answer進(jìn)行取余操作以防止編號(hào)數(shù)值超過最大編號(hào)（溢出）147     148     return 0;149 }

                                           對(duì)于Josephus問題有兩個(gè)地方是可以進(jìn)行優(yōu)化的。 (總?cè)藬?shù)為N，編號(hào)為從0~N-1；經(jīng)過M次報(bào)數(shù)去除一個(gè)成員，剩余成員個(gè)數(shù)為numleft， 記M%numleft為mPrime)

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

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

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

至此，我們可以發(fā)現(xiàn)，利用count計(jì)數(shù)從而刪除成員的方法與此相比起來遜色不少，故之后我們將采用此方法來解決問題。

新聞標(biāo)題：Josephus問題的不同實(shí)現(xiàn)方法與總結(jié)
本文URL：http://www.chinadenli.net/article12/jcoidc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、用戶體驗(yàn)、網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)