約瑟夫環(huán)問題實驗報告材料

1、約瑟夫環(huán)問題實驗報告實驗課題：用循環(huán)鏈表解決約瑟夫環(huán)的問題 參與者：XX XXX班級：教育技術(shù)121班日 期：2013年10月11日上機環(huán)境：宿舍個人電腦，硬件設(shè)施如下圖所示:O電腦基本信息援作該主卡，圧瀏遵器Mi碩K34HR筆記本電孤Windows 7 5W版眾位 SP1服蘋號10.0墓本硬件展示處理器英特爾第二代匿昏i3-235OM 2.30GHz取核陽 K84HR2 GE (三星 DDR2 1333MH2 j主軽日立 HT554?550A9EMB4 ( 500 GB / 5400 劑分ATI Radnor HD 7470M tl 68 / W)京東方BQEQ5B1 (14英寸為昱 RTL

2、8168E PQ E GigabH Ethernet NIC /頤蘆卡注昱AK藥9 st持爾&兵ri科Chi戸玳高保真言瀕實驗要求【實驗?zāi)康摹渴煜語言的基本編程方法，掌握線性表的操作實現(xiàn)方法，培養(yǎng)使用線性表解決實際問題的能力。【實驗內(nèi)容】利用循環(huán)鏈表實現(xiàn)約瑟夫問題的求解。存儲結(jié)構(gòu)：循環(huán)鏈表約瑟夫問題如下：一、小孩報數(shù)問題有N個小孩圍城一圈，給他們從1開始依次編號，現(xiàn)指定從第W個開始報數(shù)，報到第 S個時，該小孩出列，然后從下一個小 孩開始報數(shù)，仍是報到第S個時出列，如此重復(fù)下去，直到所有 的小孩都出列(總?cè)藬?shù)不足 S個時將循環(huán)報數(shù))，求小孩出列的 順序。算法分析：用一個標(biāo)準(zhǔn)的輸入輸出的

3、頭文件 iostream.h，為了 統(tǒng)一對表中任意節(jié)點的操作， 循環(huán)鏈表不帶頭結(jié)點。循環(huán)鏈表的 結(jié)點定義為如下結(jié)構(gòu)類型：#i nclude<iostream.h>struct Nodeint data;struct Node *n ext;；int mai n()int m,n;cout«" 請輸入m的值"cin>>m;cout«" 請輸入n的值"cin>>n;Node *first,*last;first=last二 new Node;/生成第一個結(jié)點first->data=1;for(i

4、nt i=2;i <n+1;i+)Node *p=new Node;p->data=i;last- >n ext=p;last=p;/鏈接結(jié)點last- >n ext二first;int nu mber 二n;Node *pre=last;while( nu mber>1)for(i nt j=1;j<m;j+)pre二pre->n ext;Node *p=pre->n ext;pre->n ext=p->n ext;cout<<p->data<<""delete p;nu mber-

5、;cout<vpre->data<v"" delete pre;,ifl .1 'D:Micrti sa+t Vi sStjidi or/yPrpfectsj osephusDe bugV omphi .exe' 已*wn u key to cont imac輸出結(jié)果如下圖所示：二、Joseph（約瑟夫）問題是非常著名的。最原始的問題是：n個人，記為1，2，n，站成一圈。從第一個人開始數(shù)，數(shù)到 的第m個人將要被處死，如此反復(fù)進行，直到只剩下一個人， 而這個人會獲救。比如：當(dāng)n=6 ，m=5 ，那么這些人將以5，4， 6，2，3的次序被處死，

6、而1就獲救了。假設(shè)有k個好人和k個壞人圍成一圈，其中1到k是好人，(k+1 )到2k是壞人。你必須選擇m使得所有的壞人都先被處 死，然后才是第一個好人；并且要求m最小 #i nclude<iostream.h>struct Nodeint data;Node *pNext;；void mai n()int n,k,m,i;Node *p,*q,*head;cout<<" 輸入n的值:"；cin>>n;cout<<"輸入起始報數(shù)人號碼k的值:"cin> >k;cout<<"

7、輸入數(shù)到m出列的m的值:"cin>>m;head=(Node*)new Node;/ 確定頭結(jié)點p=head;for(i=1;i<=n-1;i+)/ 賦初值p->data=i;p->pNext=(Node* )new Node;p二p->pNext;p->data 二n;處理p->pNext二head;環(huán)鏈表p=head;/為下一個新建內(nèi)存/最后一個單獨/指向頭，形成循while(p->data!=(p->pNext)->data)p->data=(p->pNext)->data表示只剩下一個結(jié)點的while(p->data !=k)/尋找編號為k的結(jié)點p=p->pNext;if(m=1)for(i=1;i< 二n ;i+)cout<vp->data<v't'p=p->pNext ;cout«'n：return;elsefor(i=1;i<m-1;i+)p二p->pNext;q二p->pNext; cout<vq->data<v"t" k=(q->pNext)->data; p->pN