2023年《資料結構與演算法》課程設計
學院： 數學與資訊科學學院
專業： 數學與應用數學
班級： 2013級1班
姓名： 解堅傑
課題名稱： 猴子的選王問題
指導老師： 覃美珍
2023年 8 月 22 日
猴子選王問題
猴子選王問題求解：
一堆猴子都有編號，編號是1，2，3 ...m ,這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數，每數到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最後乙隻猴子，則該猴子為大王。
【基本要求】
(1)利用單迴圈鍊錶作為儲存結構模擬此過程；
(2)輸入資料：輸入m,n, m,n 為整數，n(3)輸出形式：中文提示按照m個猴子，數n 個數的方法，輸出為大王的猴子是幾號 ，建立乙個函式來實現此功能。
【選做內容】
(1)新增在順序結構上實現的部分；
(2)介面設計的優化。
對題意進行分析後，可以畫出整個過程的流程圖。
具體流程圖:
這個問題屬於約瑟夫環問題，我們對這個題目進行具體分析：
假如現在m=5,n=2,即有5只猴子，按照迴圈數2的方法，我們演變這個過程：
第一次：1 2 3 4 5
2號出局
第二次：1 2 3 4 5
4號出局
第三次：1 2 3 4 5
1號出局
第四次：1 2 3 4 5
5號出局
最後得到猴王的序號是3號。那麼一般化，對於m猴子，n只猴子設計程式
以資料結構（c語言）中的迴圈單鏈表為主要的設計支柱，利用了c語言簡潔緊湊、靈活方便，語法限制不太嚴格，程式設計自由度大，生成目標**質量高，程式執行效率高等方面的優點。迴圈單鏈表是單鏈表的另一種形式，其結構特點是鍊錶中最後乙個結點的指標域不再是結束標記，而是指向整個鍊錶的第乙個結點，從而使鍊錶形成乙個環，基於這樣的特點，它適合處理具有環形結構的資料元素序列。
typedef struct lnodemonkey;
演算法函式中定義了單鏈表的結構體struct lnode，其中data域用來存放資料素，next域用來存放乙個結點的指標。monkey是struct lnode型別的變數。
①標頭檔案說明 #include<> 此程式主要以c語言為編寫語言，因此在程式中要用到系統提供的標準庫函式中的輸入，輸出函式，例如：scanf()函式,printf()函式。所以必須在程式開頭一行寫上#include<>。
② #include<> 在這個程式中，用到的主要是資料結構中的迴圈單鏈表方面的相關知識。我們把由乙個資料元素域及乙個或若干個指標域組成的結構體稱為乙個結點。而在單鏈表中的每個結點，實在需要時才向系統申請的，也就是所謂的動態記憶體空間申請。
動態申請的記憶體空間，當不再需要時，必須由申請者自己釋放。c語言提供了動態申請記憶體空間的函式malloc（）和動態釋放記憶體空間的函式free（）。這些函式都包含在標頭檔案中。
所以也必須在程式開頭寫上#include<>。 例如：head=q=p=(monkey *)malloc(sizeof(monkey))； 這一句就是申請占用位元組個數為sizeof(monkey)的monkey型別的乙個結點，並且讓head，q，p三個指標同時指向這個結點。
③ main() 主程式，包括輸入輸出和主要函式的呼叫。
呼叫 link_solve() 用鍊錶解決這個問題的方法。
呼叫array_solve() 用陣列解決這個問題的方法。
typedef int datatype; 我們都知道，沒有實際含義的資料元素稱作抽象資料元素。在設計時遇到抽象資料元素，我們將用datatype表示該抽象資料元素的資料型別；而當軟體設計問題具體確定時，抽象資料元素的資料型別將被具體的資料型別所取代。在本程式中，要求線性表的資料型別為int型別，可以通過重新定義抽象資料元素為int型別，來確定該抽象資料元素的資料型別。
迴圈鍊錶：首先生成乙個空鍊錶，並給n個結點分配空間，讓單鏈表的表尾指標指向頭結點則生成乙個帶有n個結點的迴圈單鏈表。再給每只猴子建立順序的編號。
現從第乙個結點開始報數，依次順序查詢出報數為m的待出列的結點（猴子）通過q->next=p->next刪除該結點後繼續執行否則讓q成為p的前驅指標。最後當p->next==p時停止執行，得到p所指向的結點即為猴子選出大王的編號。
陣列：定義乙個空的陣列，有足夠多的元素並分配空間。給所有元素賦值為1表示猴子存在。執行for迴圈，淘汰的猴子賦值為0，直到只剩乙隻猴子，即為猴王。
#include<>
#include<>
int m,n;
typedef int datatype;
typedef struct lnode
monkey;//定義結點
void link_solve()
printf("第%d位猴子的編號是：%d\n",i,i);
q->next=head;
head->data=m;
p=head;
q=p->next;
printf("\n");
if(m==1)
printf("\n按照1個猴子，猴子大王的編號是:1\n");
else if(m!=1)
}void array_solve()
printf("\n\n");
x=0;//令x初始值為零
y=m;
for(i=0;y!=1;i++)// 執行迴圈，淘汰的猴子值為0，直到只剩乙隻猴子，即為猴王
for(i=0;i<=m;i++) //輸出值不為0的猴子，即猴王
if(a[i]!=0)
printf("\n按照%d個猴子，數%d個數\n猴子大王的編號是:%d \n",m,n,i+1);
}void main()
資料結構 猴子分桃
設計題目 猴子分桃 動物園裡的n 只猴子編號為1，2，n，依次排成一隊等待飼養員按規則分桃。動物園的分桃規則是每只猴子可分得m個桃子，但必須排隊領取。飼養員迴圈地每次取出1 個，2 個，k個桃放入筐中，由排在隊首的猴子領取。取到筐中的桃子數為k 後，又重新從 1 開始。當筐中桃子數加上隊首猴子已取得...
資料結構大作業猴子吃桃問題
課程設計說明書 課程名稱資料結構 設計題目 猴子吃桃問題 學院 電腦科學與資訊工程學院 學生姓名 學生學號 專業班級軟體工程 指導教師宋強 2014年06月15日 課程設計任務書 猴子吃桃問題 摘要 資料結構是一門結合c 知識的重要課程，因此我們要學會用平時課本的知識運用到我們的現實生活當中，這樣才...
王紅梅資料結構答案
1.填空 是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。解答 資料元素 是資料的最小單位，是討論資料結構時涉及的最小資料單位。解答 資料項，資料元素 分析 資料結構指的是資料元素以及資料元素之間的關係。從邏輯關係上講，資料結構主要分為和 解答 集合，線性結構，樹結構，圖結構 資料的儲...