約瑟夫斯問題求解

1、實驗一：約瑟夫斯問題求解一、 問題描述 1 實驗題目：約瑟夫斯問題的一種描述是：編號為1，2，n的n個人按順時針方向圍坐一圈，每人持有一個密碼9(正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按照順時針方向自1開始報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他在順時針方向下一個人開始重新重新從1報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個程序，按出列順序印出各人編號。 2 基本要求：利用單向循環(huán)鏈表模擬此過程，按照出列的順序印出各人編號。3 測試數(shù)據(jù)：n=7,7個人的密碼依次為3，1，7，2，4，8，4.m的初始值為6（正確的出列順序應(yīng)為6，1，4，

2、7，2，3，5。 二、 需求分析 1 程序所能達(dá)到的基本可能：本程序能夠按出列順序印出各人編號，程序運行后顯示提示信息，提示用戶輸入人數(shù)n,初始報數(shù)值m，n個人的密碼，程序需自動考慮重復(fù)的，用戶輸入完畢后，程序自動輸出運算結(jié)果。2 輸入的形式及輸入值范圍 ：輸入人數(shù)n,初始報數(shù)值m，n個人的密碼，所有值均為正整數(shù)int型。3 輸出的形式： 輸出的是按出列順序印出各人編號，為正整數(shù)int型。4 測試數(shù)據(jù)要求 ：測試數(shù)據(jù)要求為int型 三、 概要設(shè)計 1. 所用到得數(shù)據(jù)結(jié)構(gòu)及其ADT 為了實現(xiàn)上述功能，應(yīng)以單向循環(huán)鏈表有序鏈表表示集合數(shù)據(jù)類型。 1. 單向循環(huán)鏈表抽象數(shù)據(jù)類型定義： typedef

3、 struct node ElemType data; ElemType num; struct node *next;SLNODE; 基本操作： struct node *create_sl(int n);/創(chuàng)建單向循環(huán)鏈表2. 主程序流程及其模塊調(diào)用關(guān)系 1）創(chuàng)建循環(huán)鏈表的流程圖2） 約瑟夫問題求解流程圖3） 主函數(shù)流程圖四、 詳細(xì)設(shè)計 1. 實現(xiàn)每個操作的偽碼，重點語句加注釋 主程序：void main() SLNODE *head; int n,m; head=(SLNODE *)malloc(sizeof(SLNODE); printf("/*/n"); /初始界

4、面 printf(" 學(xué)號：031350102n"); printf(" 姓名：王亞文n"); printf(" 約瑟夫斯問題求解n"); printf("/*/n"); printf("輸入總?cè)藬?shù)n=n"); scanf("%d",&n); printf("輸入初始報數(shù)值m=n"); scanf("%d",&m); head=create_sl(n); Josephus(head,n,m);2.創(chuàng)建循環(huán)單鏈表struc

5、t node *create_sl(int n) SLNODE *p,*s,*head; ElemType x; int a; head=(SLNODE *)malloc(sizeof(SLNODE); p=head; head->next=head; for(a=1;a<=n;a+) /循環(huán)直到輸入n個密碼值跳出循環(huán) s=(SLNODE *)malloc(sizeof(SLNODE); printf("請輸入第%d個人的密碼值n",a); scanf("%d",&x); s->data=x; s->num=a; if(h

6、ead->next=head) head=s; else p->next=s; p=s; p->next=head; return head;3.約瑟夫斯問題求解：void Josephus(SLNODE *head,int n,int m) SLNODE *p,*q; int i; p=head; printf("出列序列:"); while(p->next!=p) for(i=1;i<m;i+) /報數(shù)報的m時跳出循環(huán) q=p; p=p->next; m=p->data; /讀取新的密碼值 printf("%4d&qu

7、ot;,p->num); q->next=p->next; /刪除p節(jié)點 free(p); p=q->next; printf("%4dn",p->num); 4. 函數(shù)調(diào)用關(guān)系圖 主函數(shù)中調(diào)用了struct node *create_sl(int n);void Josephus(SLNODE *head,int n,int m);兩個函數(shù)五、 調(diào)試分析 1. 設(shè)計與調(diào)試過程中遇到的問題分析、體會 1）創(chuàng)建單鏈表時，一開始寫的程序是void create_sl(SLNODE *head ,int n),并沒有沒有報錯，但最后運行時卻不是想象的

8、結(jié)果，然后嘗試在主函數(shù)中寫一個printf函數(shù)看一下創(chuàng)建表是否創(chuàng)建成功，事實證明并沒有，后來改成了struct node *create_sl(int n);解決了這個問題，再次就是建表的時候發(fā)現(xiàn)最后一個數(shù)并不是我輸入的數(shù)，然后就是開始改那個循環(huán)=函數(shù)，發(fā)現(xiàn)我雖然是讀了7個數(shù)，但第7個數(shù)并沒有賦值給鏈表，原錯誤函數(shù)：p=head; head->next=head;printf("請輸入密碼值n");scanf("%d",&x);for(a=1;a<n;a+) /循環(huán)直到輸入n個密碼值跳出循環(huán) s=(SLNODE *)malloc(si

9、zeof(SLNODE); printf("請輸入密碼值n"); scanf("%d",&x); s->data=x; s->num=a; if(head->next=head) head=s; else p->next=s; p=s; 經(jīng)過修正后的函數(shù)：p=head; head->next=head; for(a=1;a<=n;a+) /循環(huán)直到輸入n個密碼值跳出循環(huán) s=(SLNODE *)malloc(sizeof(SLNODE); printf("請輸入第%d個人的密碼值n",a);

10、 scanf("%d",&x); s->data=x; s->num=a; if(head->next=head) head=s; else p->next=s; p=s; 2）建表成功之后開始解決本次的主問題約瑟夫斯求解問題，本問題主要考慮循環(huán)終止條件，一開始寫的是head->next=head;發(fā)現(xiàn)經(jīng)常運行錯誤，后來修正用p->next!=p，然后最后一個p值單獨寫一句輸出printf("%4dn",p->num);中間的句子就是找到報數(shù)值然后刪除，注意保留要刪除節(jié)點的密碼值，并沒有什么大問題。還有一

11、個問題，就是在開始的時候創(chuàng)建單鏈表并沒有想到要用序號值num，最開始定義單鏈表的語句：typedef struct node ElemType data; struct node *next;SLNODE; 然后就會在創(chuàng)建鏈表賦值時和解決約瑟夫斯問題時都要重新定義一個變量x進行計數(shù)，增加了程序的復(fù)雜度最后修正為：typedef struct node ElemType data; ElemType num; struct node *next;SLNODE; 3) 剩下的還有一些小問題，比如少打了一個字母，打錯一個字母，這些程序會報錯，不屬于邏輯錯誤，所以解決起來也比較快，2. 主要算法的時間

12、復(fù)雜度分析 創(chuàng)建單鏈表的時間復(fù)雜度為O（n）;約瑟夫斯問題的時間復(fù)雜度與n值有關(guān)，也與每個人的密碼值有關(guān),時間復(fù)雜度O（mn）;空間復(fù)雜度為O（n）;六、 使用說明程序運行后顯示提示信息，提示用戶輸入人數(shù)n,初始報數(shù)值m，n個人的密碼，用戶按照提示輸入完畢后，程序自動輸出運算結(jié)果。七、 測試結(jié)果 八、 附錄 #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <time.h> typedef int ElemType;typedef struct node Ele

13、mType data; ElemType num; struct node *next;SLNODE; /單鏈表的定義struct node *create_sl(int n);void Josephus(SLNODE *head,int n,int m);int main() /主函數(shù) SLNODE *head; int n,m; time_t rawtime; struct tm * timeinfo; time (&rawtime); timeinfo = localtime (&rawtime); head=(SLNODE *)malloc(sizeof(SLNODE)

14、; printf("/*/n"); /初始界面 printf(" 學(xué)號：031350102n"); printf(" 姓名：王亞文n"); printf(" 約瑟夫斯問題求解n"); printf("/*/n"); printf("輸入總?cè)藬?shù)n=n"); scanf("%d",&n); printf("輸入初始報數(shù)值m=n"); scanf("%d",&m); head=create_sl(n); /

15、創(chuàng)建單鏈表 Josephus(head,n,m); printf ("Current local time and date: %s", asctime(timeinfo); return 0;struct node *create_sl(int n) SLNODE *p,*s,*head; ElemType x; int a; head=(SLNODE *)malloc(sizeof(SLNODE); p=head; head->next=head; for(a=1;a<=n;a+) /循環(huán)直到輸入n個密碼值跳出循環(huán) s=(SLNODE *)malloc(si

16、zeof(SLNODE); printf("請輸入第%d個人的密碼值n",a); scanf("%d",&x); s->data=x; s->num=a; if(head->next=head) head=s; else p->next=s; p=s; p->next=head; return head; void Josephus(SLNODE *head,int n,int m)/約瑟夫斯問題求解 SLNODE *p,*q; int i; p=head; printf("出列序列:"); wh

17、ile(p->next!=p) for(i=1;i<m;i+) /程序運行到第m個人跳出循環(huán) q=p; p=p->next; m=p->data; /讀取新的密碼值 printf("%4d",p->num); q->next=p->next; /刪除p節(jié)點 free(p); p=q->next; printf("%4dn",p->num); 九、 實驗收獲和感想 通過本實驗首先是解決了約瑟夫斯問題，利用計算機快速解決這個問題，其次在程序編寫過程中慢慢掌握了循環(huán)單鏈表的一些用法以及注意事項，因為距離上次學(xué)習(xí)c語言