實驗報告1-約瑟夫環(huán)

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