/* *Copyright (c) 2017,煙臺大學計算機與控制工程學院 *All rights reserved. *文件名稱：項目5-一群猴子，編號是1，2，3 …m，這群猴子（m個）按照1-m的順序圍坐一圈。從第1只開始數(shù)，每數(shù)到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。輸入m和n，輸出為大王的猴子是幾號。 提示： （1）鏈表解法：可以用一個循環(huán)單鏈表來表示這一群猴子。表示結(jié)點的結(jié)構(gòu)體中有兩個成員：一個保存猴子的編號，一個為指向下一個人的指針，編號為m的結(jié)點再指向編號為1的結(jié)點，以此構(gòu)成環(huán)形的鏈。當數(shù)到第n個時，該結(jié)點被刪除，繼續(xù)數(shù)，直到只有一個結(jié)點。 （2）使用結(jié)構(gòu)數(shù)組來表示循環(huán)鏈：結(jié)構(gòu)體中設(shè)一個成員表示對應(yīng)的猴子是否已經(jīng)被淘汰。從第一個人未被淘汰的數(shù)起，每數(shù)到n時，將結(jié)構(gòu)中的標記改為0，表示這只猴子已被淘汰。當數(shù)到數(shù)組中第m個元素后，重新從第一個數(shù)起，這樣循環(huán)計數(shù)直到有m-1被淘汰。 （3）該問題為計算機科學中的經(jīng)典問題，很多實際的問題可以抽象到這種模型上來。感興趣的同學請搜索“約瑟夫問題” *作 者：邵雪源 *完成日期：2017年12月13日 *版 本 號：v1.0 */ #include <iostream> using namespace std; struct Monkey {int num; //猴子的編號struct Monkey *next; //下一只猴子 };int main() {int m,n,i,j,king;Monkey *head, *p1,*p2;cin>>m>>n;if(n==1){king=m;}else{//建立猴子圍成的圓圈p1=p2=new Monkey;head = p1;p1->num=1;for(i=1; i<m; i++) //其余m-1只猴子{p1=new Monkey; //p1是新增加的p1->num=i+1;p2->next=p1;p2=p1; //p2總是上一只}p2->next=head; //最后一只再指向第一只，成了一個圓圈//下面要開始數(shù)了p1=head;for(i=1; i<m; i++) //循環(huán)m-1次，淘汰m-1只猴子{//從p1開始，數(shù)n-1只就找到第n只了for(j=1; j<n-1; j++) //實際先找到第n-1只，下一只將是被淘汰的p1=p1->next; //圍成圈的，可能再開始從第一只數(shù)，如果還未被淘汰的話//找到了，p2=p1->next; //p2將被刪除//cout<<"第"<<i<<"輪淘汰"<<p2->num<<endl; //可以這樣觀察中間結(jié)果p1->next=p2->next; //p2就這樣被“架空了”p1=p2->next; //下一輪數(shù)數(shù)的新起點delete p2; //將不在鏈表中的結(jié)點放棄掉}king=p1->num;delete p1;}cout<<king<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的第四周实践项目5 猴子选大王（循环链表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。