實(shí)驗(yàn)報(bào)告1-約瑟夫環(huán)

PAGEPAGE1華北水利水電學(xué)院約瑟夫環(huán)實(shí)驗(yàn)報(bào)告2010～2011學(xué)年第一學(xué)期09級(jí)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)班級(jí)：2009119學(xué)號(hào)：200911902姓名：萬婷婷實(shí)驗(yàn)?zāi)康囊笤O(shè)計(jì)一個(gè)程序模擬約瑟夫環(huán)問題過程，求出出列編號(hào)序列。二、實(shí)驗(yàn)要求1）利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號(hào)。2）建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。3）建立一個(gè)輸出函數(shù)，將正確的輸出序列測(cè)試數(shù)據(jù)：m的初值為20，n=7,7個(gè)人的密碼依次為3，1，7，2，4，7，4三、實(shí)驗(yàn)內(nèi)容基本算法以及分析：本程序主要是以建立單循環(huán)鏈表的形式，建立起一個(gè)約瑟夫環(huán)，然后根據(jù)之前創(chuàng)立的結(jié)點(diǎn)，輸入結(jié)點(diǎn)里的一些數(shù)據(jù)，如下typedefstructNode{ intIndex;在當(dāng)前環(huán)中所處的位置，即編號(hào) intPassword;在當(dāng)前環(huán)中的所帶的密碼 structNode*next;}JosephuNode;程序有主函數(shù)開始，首先，提示輸入創(chuàng)建約瑟夫環(huán)環(huán)數(shù)以及每個(gè)環(huán)上所帶的密碼。然后,利用單循環(huán)鏈表建立起約瑟夫環(huán)，p->next=head->next;就是將最后一個(gè)結(jié)點(diǎn)的后繼指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，然后主函數(shù)調(diào)用Josephu函數(shù)，并實(shí)現(xiàn)如下功能：編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。四、程序源代碼1．約瑟夫環(huán)問題#include<iostream.h>#include<malloc.h>#include<stdio.h>typedefstructLNode{ intM;//當(dāng)前出局人的編號(hào) intPassword;//當(dāng)前出局人所帶密碼 structLNode*next;}JosephuNode;voidJosephu(intn,intm){ inti,j,password; JosephuNode*head,*p,*q,*L; head=p=(JosephuNode*)malloc(sizeof(JosephuNode)); for(i=1;i<=n;i++) {q=(JosephuNode*)malloc(sizeof(JosephuNode));p->next=q; q->M=i; printf("請(qǐng)輸入第%d號(hào)所帶密碼:", i); scanf("%d",&password); q->Password=password; p=q; } p->next=head->next; free(head); L=q->next; printf("出列者的編號(hào)順序是：");while(p!=L) { for(j=1;j<m;j++) { p=L; L=L->next; } p->next=L->next; printf("%d,",L->M); m=L->Password; free(L); L=p->next; } printf("%d\n",p->M); free(L); }voidmain(){ intn,m; printf("約瑟夫環(huán)問題\n"); printf("輸入的n和m值不小于1：\n"); printf("請(qǐng)輸入?yún)⒓拥娜藬?shù)n:"); scanf("%d",&n); printf("請(qǐng)輸入起始報(bào)數(shù)上限值m:"); scanf("%d",&m); Josephu(n,m);}五、運(yùn)行結(jié)果六、小結(jié)（不少于100字）通過這次實(shí)驗(yàn)，使我更加知道自己的不足和需要加強(qiáng)的地方，指針仍然是自己需要去加強(qiáng)鞏固的地方。每次看到自己寫的程序和網(wǎng)上的比較發(fā)現(xiàn)自己需要