北工大數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告1

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