josephus問題

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)作業(yè) 12015/4/81 / 16、需求分析1) 設(shè)有 n 個(gè)人圍坐在一個(gè)圓桌周圍，現(xiàn)從第 s 個(gè)人開始報(bào)數(shù)，數(shù)到第 m 的人出列，然后從出列的下一個(gè)人開始報(bào)數(shù)，數(shù)到第 m 的人又出列，如此反復(fù) 直到所有的人都出列為止。 Josephus問題是：對(duì)于任意給定的 n、 s、m，求出 按出列次序得到的 n 個(gè)人員的序列。試在計(jì)算機(jī)上模擬 Josephus問題的求解過 程。2) 輸入形式，輸入值范圍：輸入 n、s、m 三個(gè)整型數(shù)值，三個(gè)整型數(shù)值 均大于 0。3) 輸出形式：按出列順序輸出。4) 程序功能： 程序運(yùn)行時(shí)，先按規(guī)定輸入三個(gè)適當(dāng)?shù)臄?shù)， 由 create 函數(shù)創(chuàng) 建順序表， J

2、osephus函數(shù)實(shí)現(xiàn) Josephus問題，在實(shí)現(xiàn)過程中按在順序表中出列 的次序一次輸出。5) 測(cè)試數(shù)據(jù)：正確輸入： n=12， m=3，s=5 ，輸入正確，結(jié)果按順序顯示2 / 16錯(cuò)誤輸入：輸入 n=0，顯示輸入錯(cuò)誤；輸入 n=8，m=3，s=0；輸入錯(cuò)誤private:T *aList; int maxSize; int curLen;/順序表元素類型/順序表 arrList、概要設(shè)計(jì)1) ADT 定義： 順序表： template class arrList/數(shù)組 aList/表的最大長(zhǎng)度 /順序表實(shí)例的當(dāng)前長(zhǎng)度/構(gòu)造函數(shù)public:arrList(const int size)

3、maxSize = size; aList = new TmaxSize; curLen = 0;arrList( ) delete aList;int length();bool del( const int p);bool getValue(const int p, T& value ); bool create();void display();void Josephus(int s,int m);/析構(gòu)函數(shù)/返回此順序表的當(dāng)前實(shí)際長(zhǎng)度/刪除位置 p 上元素表長(zhǎng)減 1 /提取位置 p 的元素值給 value/創(chuàng)建順序表/顯示表里的內(nèi)容/ 實(shí)現(xiàn) Josephus問題鏈表： template

4、 class Link3 / 16public: T data;Link *next;Link(const T info, Link *nextValue = NULL) data = info;next = nextValue;Link(const Link * nextValue) next = nextValue;class lnkListprivate:Link *head, *tail;/Link *setPos(const int p); public:/構(gòu)造函數(shù)/析構(gòu)函數(shù)/判斷表是否是空/清空/返回表長(zhǎng)/ 在表尾追加一個(gè)元素，表長(zhǎng)自動(dòng)加 1lnkList();lnkList();

5、bool isEmpty();void clear();int length();bool append(const T value);/bool insert(const int p, const T value);/bool deletej(const int p);/bool setPos(const int i);bool create(T n);/ 創(chuàng)建長(zhǎng)度為 n 的鏈表void display();/ 顯示鏈表的內(nèi)容/bool getValue(const int p,T &value);/bool getPos(int &p,const T value);void Josephu

6、s(int m, int s);/實(shí)現(xiàn) Josephus 問題;2）主程序流程：4 / 163）各程序模塊間的調(diào)用關(guān)系 順序表：在源文件中包含兩個(gè)頭文件的聲明 #include arrList.h 和 #include，iostream是c+標(biāo)準(zhǔn)庫(kù)頭文件， arrList 是自己編寫的頭文 件，可以在源文件中通過 #include arrList.h 這種方式訪問頭文件里的類、 成員 函數(shù)等，在這個(gè)程序中，在源文件開始執(zhí)行時(shí)，用 arrList 類創(chuàng)建一個(gè)對(duì)象，通 過對(duì)象先后訪問了 arrList 里 create、 display、Josephus三個(gè)成員函數(shù)，在這三 個(gè)成員函數(shù)開始執(zhí)行時(shí)，

7、分別在 arrList 里調(diào)用了各類私有和公有的成員變量及 成員函數(shù)。鏈表：源文 件還是包 含兩個(gè)頭文件#include和 #include lnkList.h ，而在 lnkList 這個(gè)頭文件中，又包含了 Link.h 這個(gè)頭文件，在 lnkList 中創(chuàng)建節(jié)點(diǎn)用到 Link 這個(gè)抽象數(shù)據(jù)類型。源文件在執(zhí)行時(shí)，調(diào)用了 lnkList 里 的成員函數(shù)，通過參數(shù)的傳遞和函數(shù)的調(diào)用共同實(shí)現(xiàn)了 Josephus問題。三、詳細(xì)設(shè)計(jì)1）實(shí)現(xiàn) ADT 的數(shù)據(jù)類型： 程序的主要輸入輸出都是整型， 所以，實(shí)現(xiàn) ADT 的數(shù)據(jù)類型為整型。2）算法描述： 順序表：5 / 16void arrList:Josep

8、hus(int s,int m) int i=s ; while(curLen0) i=(i+m-2)%(length (); cout 出列的人是： aListi endl; del(i); i+;鏈表：void lnkList:Josephus(int m,int s) if (head != NULL)for (int i = 0; i next;Link *h=head,*p; while (!isEmpty()for (int i = 0; i next;cout 出列的人是： data next=h-next;delete h; h=p-next; delete p;6 / 16鏈

9、表：list函里建表 主數(shù)創(chuàng)鏈四、測(cè)試結(jié)果順序表：7 / 1691/8:峯搗ET TI wr 683羽尬M適鮭址區(qū)遼返？-爭(zhēng)壽 S妙3妙|知|3|丟丑旦3:痕 Invvyyyyyyyyetm _ ff壬呈呈呈呈養(yǎng)呈星呈養(yǎng)聲陽比：一：rq-6nq旳址華遜.I酗和目童隔辜宓峯封車聲訃Pdi亦l(xiāng)Alg P rus lns嵐甘。sojjj內(nèi),：!.五、程序源代碼鏈表：/Link.htemplate class Link public:T data;Link *next;Link(const T info, Link *nextValue = NULL) data = info;next = nextV

10、alue;Link(const Link * nextValue) next = nextValue;/lnkList.h#includeLink.h9 / 16template class lnkListprivate:Link *head, *tail;/Link *setPos(const int p); public:/構(gòu)造函數(shù)/析構(gòu)函數(shù)/判斷表是否是空/清空/返回表長(zhǎng)/ 在表尾追加一個(gè)元素，表長(zhǎng)自動(dòng)加1lnkList();lnkList();bool isEmpty();void clear();int length();bool append(const T value);/boo

11、l insert(const int p, const T value);/bool deletej(const int p);/bool setPos(const int i);bool create(T n);/ 創(chuàng)建長(zhǎng)度為 n 的鏈表void display();/ 顯示鏈表的內(nèi)容/bool getValue(const int p,T &value);/bool getPos(int &p,const T value);void Josephus(int m, int s);/實(shí)現(xiàn) Josephus 問題;templatebool lnkList:isEmpty()/ 判斷是否是空 i

12、f (head = NULL&head-next = NULL) return true;elsereturn false;templatevoid lnkList:clear()/ 表清空 head = tail=NULL;template bool lnkList:create(T n) int i;/賦初值/指向頭，形成循環(huán)鏈表for (i = 1; i next = head; return true;10 / 16templatevoid lnkList:display()int l = length();cout 表里的元素有： ;for (int i = 0; i l; i+)c

13、out datanext; cout endl;templateint lnkList:length()/ 返回表長(zhǎng) int i = 1;Link *h;if (head = NULL) return i-1;h = head-next;while (h != tail-next) i+; h = h-next;return i;templatebool lnkList:append(const T value)if (head = NULL)head = new Link(value, NULL); tail = head;elsetail-next = new Link(value, NU

14、LL); tail = tail-next;return true;template lnkList:lnkList()head = tail = NULL;/ 在表尾追加11 / 16 template lnkList:lnkList()Link *temp; while (head != NULL) temp = head; head = head-next; delete temp;/* template Link * lnkList:setPos(int i)int count=0;if(i=0)return 0;Link *p=new Link(head-next);while(p!

15、=NULL&countnext;count+;return p;/templatebool lnkList:insert(const int i, const T value)Link *p, *q;if (p = setPos(i - 1) = NULL)cout 非法插入點(diǎn) endl; return false;q = new Link(value, p-nxet);p - next = q;if (p = tail)tail = q;return true;*/templatevoid lnkList:Josephus(int m,int s)if (head != NULL)for (

16、int i = 0; i next;Link *h=head,*p;while (!isEmpty()12 / 16 for (int i = 0; i next;cout 出列的人是： data next=h-next;delete h;h=p-next;delete p;/jose.cpp#include#include lnkList.husing namespace std;int main()int n,m,s;cout 請(qǐng)輸入進(jìn)行游戲的人數(shù)： n;if(n=0)cout 輸入數(shù)據(jù)有錯(cuò)誤！ endl;lnkListlist;list.create(n);list.display();

17、cout 請(qǐng)輸入要報(bào)的數(shù)字： m;cout 請(qǐng)輸入從第幾個(gè)人開始： s;if(m0&s0)list.Josephus(s, m);elsecout 輸入數(shù)據(jù)有錯(cuò)誤！ endl;/system(pause);return 0;順序表：/arrList.h#include 13 / 16using namespace std;/數(shù)組 aList /表的最大長(zhǎng)度 /順序表實(shí)例的當(dāng)前長(zhǎng)度template class arrListprivate:T *aList; int maxSize; int curLen;/ 順序表元素類型 T/ 順序表 arrListpublic:arrList(const

18、int size) maxSize = size; aList = new TmaxSize; curLen = 0;arrList( ) delete aList;int length();bool del( const int p);bool getValue(const int p, T& value ); bool create();void display();void Josephus(int s,int m);/構(gòu)造函數(shù)/析構(gòu)函數(shù)/返回此順序表的當(dāng)前實(shí)際長(zhǎng)度/刪除位置 p 上元素表長(zhǎng)減 1 /提取位置 p 的元素值給 value/創(chuàng)建順序表/顯示表里的內(nèi)容/實(shí)現(xiàn) Josephus

19、問題template int arrList:length() return curLen;template void arrList:display()int k=length();cout 表里的元素有： for(int i=0;ik;i+) coutaListi coutendl;template bool arrList:del(const int p)14 / 16if (curLen=0)cout No element to delete n endl; return false;if (pcurLen-1)cout deletion is illegaln endl; return false;for (int i=p;