約瑟夫環(huán)問題源代碼(C語言)

1、約瑟夫環(huán)問題如下：已知n個人(n=1)圍桌一園桌周圍，從1開始順序編號。從序號為1的人開始報數(shù)，順時針數(shù)到m的那個人出列。他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列。依此規(guī)則重復(fù)下去，直到所有人全部出列。求解最后一個出列的人的編號。本次實驗是以順序表求解約瑟夫環(huán)問題，程序流程圖及程序運行結(jié)果如下：存儲并建立一個約瑟夫環(huán)通過循環(huán)結(jié)構(gòu)依次查找每次出列的人的編號并輸出輸入人數(shù)、所報數(shù)、第一個報數(shù)人編號輸出最后一個出列的人的編號程序代碼如下：#include#include#includeusing namespace std;struct Node /循環(huán)節(jié)點的定義 int number; /

2、編號 Node *next;Node *CreateList(Node *L,int &n,int &m); /建立約瑟夫環(huán)函數(shù)void Joseph(Node *L,int n,int m); /輸出每次出列號數(shù)函數(shù)Node *DeleteList(Node *L,int i,Node *q); /尋找每次出列人的號數(shù)int LengthList(Node *L); /計算環(huán)上所有人數(shù)函數(shù)void main() /主函數(shù) system(color 75); /設(shè)置顏色以美觀 Node *L; L=NULL; /初始化尾指針 int n, m; coutn; /環(huán)的長度 if(n1)cout請

3、輸入正整數(shù)!; /人數(shù)異常處理 else coutm; if(m1)cout請輸入正整數(shù)!; /號數(shù)異常處理 else L=CreateList(L,n,m); /重新給尾指針賦值 Joseph(L,n,m); system(pause);Node *CreateList(Node *L,int &n,int &m) /建立一個約瑟夫環(huán)（尾插法） Node *q; for(int i=1;inumber=i; p-next=NULL; if(i=1) L=q=p; /工作指針的初始化 else q-next=p; q=q-next; q-next=L; if(L!=NULL)return(L)

4、; /返回尾指針 else cout尾指針異常!endl; /尾指針異常處理void Joseph(Node *L,int n,int m) /輸出每次出列的人 int k; coutk; if(kn)cout請輸入1-n之間的數(shù)endl; else coutn出列順序:n; for(int i=1;in;i+) Node *q = new Node; if(i=1) q=DeleteList(&L,k+m-1,q); /第一個出列人的號數(shù) else q=DeleteList(&L,m,q); cout號數(shù)：numberendl; delete q; /釋放出列人的存儲空間 cout最后一個出

5、列號數(shù)是：numberendl; /輸出最后出列人的號數(shù) Node *DeleteList(Node *L,int i,Node *q) /尋找每次出列的人 if(i=1) i+=LengthList(*L); /順序依次出列情況的處理方式 Node *p; p=*L; int j=0; while(jnext;j+; q = p-next; p-next=p-next-next; *L = p-next; return(q);int LengthList(Node *L) /計算環(huán)上的人數(shù)if(L)cout尾指針錯誤!next; while(p!=L) i+; p=p-next; return(i); 實驗體會：通過對本問題的分析，我進(jìn)一步熟悉了對各種邏輯表達(dá)