實(shí)驗(yàn)一約瑟夫環(huán)問題實(shí)驗(yàn)報(bào)告通信二班 雷鶴20100820207 李春陽 20100820208 李孟琪20100820209問題描述設(shè)編號(hào)為1-n的n(n>0)個(gè)人按順時(shí)針方向圍成一圈．首先第1個(gè)人從1開始順時(shí)針報(bào)數(shù)．報(bào)m的人(m為正整數(shù))．令其出列。然后再從他的下一個(gè)人開始，重新從1順時(shí)針報(bào)數(shù)，報(bào)m的人，再令其出列。如此下去，直到圈中所有人出列為止。求出列編號(hào)序列。二、需求分析1、需要基于線性表的基本操作來實(shí)現(xiàn)約瑟夫問題2、需要利用數(shù)組來實(shí)現(xiàn)線性表3、測(cè)試用例輸入：10，3輸出：36927185104三、概要設(shè)計(jì) 抽象數(shù)據(jù)類型為實(shí)現(xiàn)上述程序的功能，應(yīng)以整數(shù)存儲(chǔ)用戶的輸入，以及計(jì)算出的結(jié)果。算法的基本思想利用數(shù)組來代表一個(gè)環(huán)，然后模擬報(bào)號(hào)出圈的過程，直到所有人都出圈。程序的流程程序由三個(gè)模塊組成：輸入模塊：完成兩個(gè)正整數(shù)的輸入，存入變量n和m中。計(jì)算模塊：計(jì)算這n個(gè)數(shù)的輸出序列輸出模塊：屏幕上顯示這n個(gè)數(shù)的輸出序列。四、詳細(xì)設(shè)計(jì)程序代碼：#include<iostream>usingnamespacestd;main(){ intn,m,k,j; //n為總?cè)藬?shù)，m為出列編號(hào) cin>>n>>m; int*listArray=newint[n]; //將n個(gè)人放在大小為n的數(shù)組中 int*outArray=newint[n]; //用以存放依此出列的人的編號(hào) for(inti=0;i<n;i++) listArray[i]=i+1; //對(duì)n個(gè)人進(jìn)行編號(hào) for(i=1,j=k=0;k<n;j=++j%n) //i為報(bào)數(shù)編號(hào)，初始值為1，循環(huán)訪問數(shù)組元素，即數(shù)組元素循環(huán)報(bào)數(shù) { if(listArray[j]!=0) { if(i==m) //報(bào)數(shù)編號(hào)和出列編號(hào)相同時(shí) { outArray[k]=listArray[j];//將該元素放置到出列數(shù)組里，并輸出 cout<<outArray[k]<<""; k++; listArray[j]=0; //將出列元素置0 i=1; //下一個(gè)元素從1開始重新報(bào)數(shù) } else i++; //報(bào)數(shù)編號(hào)與出列編號(hào)不同時(shí)，繼續(xù)報(bào)數(shù) } } cout<<'\n'; return0;}物理數(shù)據(jù)類型隊(duì)列元素及出列序列都以整型數(shù)組方式存儲(chǔ)算法的具體步驟 將隊(duì)列里的元素編號(hào)循環(huán)訪問數(shù)組元素第一個(gè)元素從1開始報(bào)數(shù)，報(bào)數(shù)編號(hào)與出列編號(hào)相同時(shí)出列，并將該元素置為0下一個(gè)元素重新從1開始報(bào)數(shù)，依次循環(huán)輸入和輸出的格式輸入格式：n，m輸出格式1：在字符界面上輸出這n個(gè)數(shù)的輸出序列輸出格式2：將這n個(gè)數(shù)的輸出序列寫入到文件中五、測(cè)試結(jié)果其他程序代碼程序1#include<stdio.h>#include<stdlib.h>typedefinttype;//結(jié)點(diǎn)數(shù)據(jù)域類型為整型typedefstructLNode//結(jié)點(diǎn)類型定義{structLNode*next;//結(jié)點(diǎn)的指針域typea;//結(jié)點(diǎn)的數(shù)據(jù)域}link;voidinitLink(link*&l){l=(link*)malloc(sizeof(link));//在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)申請(qǐng)鏈表長(zhǎng)度的連續(xù)空間//初始化鏈表l->next=l;}voidinsert(link*&l)//在其后插入新成員{link*p;p=(link*)malloc(sizeof(link));p->next=l->next;l->next=p;}voiddestory(link*&l)//刪除其后面的元素{link*t;t=l->next;l->next=l->next->next;free(t);}intmain(){intm,n;charp;while(scanf("%d%c%d",&n,&p,&m)!=EOF){link*head;link*temp;initLink(head);temp=head;for(inti=0;i<n;i++){insert(temp);temp->next->a=i+1;//創(chuàng)建鏈表temp=temp->next;}temp->next=NULL;temp=head;while(head->next!=NULL){for(inti=1;i<m;i++)//模擬約瑟夫過程{ { if(temp->next==NULL)temp=head; }temp=temp->next;}if(temp->next==NULL){printf("%d",head->next->a);destory(head);}else{printf("%d",temp->next->a);destory(temp);}}printf("\n");}}程序2#include<iostream>usingnamespacestd;voidmain(){ intn,m,a[100001],k,i,j; cin>>n; if(n>100000) { cout<<"請(qǐng)重輸"; return; }cin>>m; for(i=1;i<=n;i++) { a[i]=1; } j=0; k=0; for(i=1;i<=n;i++) { if(a[i]==1) { j=j+a[i]; if(j==m) { j=0; a[i]=0; k++; cout<<i<<""; } } if(i==n) i=0; } }七、實(shí)驗(yàn)心得李孟琪：該實(shí)驗(yàn)利用數(shù)組實(shí)現(xiàn)線性表，算法簡(jiǎn)便，但產(chǎn)生很多不必要的消耗，下一步可以嘗