北工大數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告1VIP

實(shí)驗(yàn)一報(bào)告姓名：學(xué)號：完成日期：2015年4月7日題目：設(shè)有n個(gè)人坐在一個(gè)圓桌周圍，現(xiàn)從第s個(gè)人開始報(bào)數(shù)，數(shù)到第m的人出列，然后從出列的下一個(gè)人重新開始報(bào)數(shù)，數(shù)到第m的人又出列，如此反復(fù)直到所有的人全部出列為止。Josephus問題是：對于任意給定的n、s、m，求出按出列次序得到的n個(gè)人員的序列。試在計(jì)算機(jī)上模擬Josephus問題的求解工程。需求分析輸入形式、輸入值的范圍：輸入的值必須為正整數(shù)輸出形式：輸出為一組正整數(shù)程序功能：對于任意給定的n、s、m，求出按出列次序得到的n個(gè)人員的序列。測試數(shù)據(jù)：正確的輸入：632正確的輸出：462531錯(cuò)誤的輸入：632錯(cuò)誤的輸出：123456概要設(shè)計(jì)主程序流程：開始開始輸入數(shù)據(jù)信息輸入數(shù)據(jù)信息創(chuàng)建數(shù)組或鏈表，并將編號存入創(chuàng)建數(shù)組或鏈表，并將編號存入是否全部出列否是否全部出列是結(jié)束結(jié)束調(diào)試分析調(diào)試中并遇到的問題：運(yùn)行結(jié)果少一個(gè)數(shù)解決方案：在while循環(huán)的限制條件中，是循環(huán)次數(shù)加1算法時(shí)空分析：O(n)用戶使用說明運(yùn)行程序后，用戶按照提示順序輸入3個(gè)正整數(shù)，然后按回車可得到結(jié)果測試結(jié)果輸入：632輸出：462531源程序以順序表實(shí)現(xiàn)：#include<iostream>usingnamespacestd;voidJJ(intn,ints,intm){int*a=newint[10000];inti;intcount=0;intt=0;for(i=0;i<n;i++){a[i]=i+1; }i=s-1; cout<<"出列次序?yàn)椋?;while(count<n-1){ if(a[i]!=0)t++;if(t==m){t=0;//記數(shù)歸0cout<<a[i]<<"";//依次輸出刪除的編號a[i]=0;//給刪除的數(shù)組賦0count++;//退出人數(shù)加1 } i++;if(i==n)i=0;//報(bào)數(shù)到末尾后i恢復(fù)為0} cout<<endl;}voidmain(){intn,s,m;cout<<"請輸入總?cè)藬?shù):"<<endl; cin>>n;cout<<"請輸入開始報(bào)數(shù)的人員序號:"<<endl; cin>>s;cout<<"請輸入出列人員的序號:"<<endl;cin>>m;JJ(n,s,m);}以鏈表實(shí)現(xiàn)：#include<iostream>usingnamespacestd;typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;voidJJ(intn,ints,intm){LinkListp,r,list=NULL;inti;//建立一個(gè)循環(huán)鏈表for(i=0;i<n;i++){p=(LinkList)malloc(sizeof(LNode));p->data=i+1;//存放第i個(gè)結(jié)點(diǎn)的編號if(list==NULL)list=p;elser->next=p;r=p;}p->next=list;p=list;for(i=1;i<s;i++){r=p;//當(dāng)m!=1,但s=1時(shí)如果沒有這條語句，此時(shí)刪除動(dòng)作無法完成p=p->next;}//此時(shí)p指向第1個(gè)出發(fā)結(jié)點(diǎn) cout<<"出列次序?yàn)椋?;while(p->next!=p){for(i=1;i<m;i++){r=p;p=p->next;}//p指向第m個(gè)結(jié)點(diǎn),r指向第m-1個(gè)結(jié)點(diǎn)r->next=p->next;//刪除第m個(gè)結(jié)點(diǎn)cout<<p->data<<"";deletep;p=r->next;}cout<<p->data; cout<<endl;}voidmain(){intn,s,m;cout<<"請輸入總?cè)藬?shù):"<<endl;scanf("%d",&n)