猴子選大王課程設計模塊設計

F. 猴子選大王程序設計

這是一個約瑟夫環的問題，這里有一個寫好的程序，功能能實現，但是如果你想把它寫成函數就自己去改吧，應該很簡單，這里我就不修改了。 #include<iostream> //定義結構體 typedef struct Joseph { int date; struct Joseph *next; struct Joseph *forie; }JOS; void main() { JOS *p,*head,*tail;//結構體指針，用來對結構體進行操作 int num,count,i; p = new JOS; head = p; tail = p; //約瑟夫環內有多少節點 cout<<"輸入循環總數："; cin>>num; cout<<"輸入循環跳轉的個數："; cin>>count; //建立約瑟夫還 cout<<"請輸入數據："; cin>>p->date; p->next = head; cout<<endl; for(i=1;i<num;i++) { p = new JOS; cout<<"請輸入數據:"; cin>>p->date; p->next=head; p->forie = tail; tail->next = p; tail = p; cout<<endl; }//建立結束 //開始循環，數到count個數，就刪除，然後繼續數 head->forie=p; p=head; while(p->next!=p) { for(i=1;i<count;i++) p=p->next; cout<<"刪除的數是："<<p->date<<endl; p->forie->next = p->next; p->next->forie = p->forie; p=p->next; } cout<<"最後剩餘的數是："<<p->date; }

麻煩採納，謝謝!

G. 數據結構課程設計——猴子選大王問題，我有程序，幫我解釋下

#include <stdio.h>
#include <stdlib.h>
#define n 19
#define m 4

typedef struct monkey
{
int num;
struct monkey *next;
} Monkey,*LINK;

void main()
{
LINK p,head,p2;
int i;
head=p=p2=(LINK)malloc(sizeof(Monkey));//三個指針指向同一塊內存

for(i=1;i<n;i++)
{
p=(LINK)malloc(sizeof(Monkey));
p2->next=p;
p2=p;
}

p2->next=head;//把鏈表的首尾相連
p=head;//p指向了第一個結點

printf("對猴子進行編號！\n");
for(i=1;i<=n;i++)
{
p->num=i;//從第一個結點到最後一個結點依次給猴子編號
printf("%d號猴子：%d\n",p->num,p->num);
p=p->next;
}//循環結束，p指向了最後一個結點

i=0;
p=head;//再把p指向第一個結點

while(1)
{
i++;
printf("%d號猴子報：%d\n",p->num,i);
if(p->next==p)
break;//此為while循環的出口

if(i==m)//if語句中是刪除結點的過程
{
i=0;
printf("%d號猴被淘汰\n",p->num);
printf("\n");
p2->next=p->next;//在此刪除結點p
p=p2->next;//p指向它的下一個結點
continue;
}
else
{
if(i==m-1)
p2=p;//保存將要退出結點的前一個結點（存到p2中）
p=p->next;
}
}

printf("勝出:%d",p->num);//最後剩下的結點就是獲勝的結點

}

這個程序其實就是形成了一個有19個結點的循環鏈表，當碰到m的時候，用這兩句話p2->next=head;p=head刪除當前的結點，然後再繼續判斷。
還有不明白的地方可以問我！

H. 猴子選大王的課程實驗報告

任務：一堆猴子都有編號，編號是1，2，3 ...m ,這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數，每數到第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最後一隻猴子，則該猴子為大王。
要求：
輸入數據：輸入m,n m,n 為整數，n<m
輸出形式：中文提示按照m個猴子，數n 個數的方法，輸出為大王的猴子是幾號 ，建立一個函數來實現此功能

#include <stdio.h>
#include <stdlib.h>

typedef struct monkey
{
int num;
struct monkey *next;
} Monkey,*LINK;

/*創建循環鏈表，容納M個猴子。返回指向鏈表頭結點的指針*/
LINK createList(int M)
{ LINK p,head1,p2;
int i;
head1=p=p2=(LINK)malloc(sizeof(Monkey));
for(i=1;i<M;i++)
{
p=(LINK)malloc(sizeof(Monkey));
p2->next=p;
p2=p;
}
p2->next=head1;
p=head1;
printf("對猴子進行編號！\n");
for(i=1;i<=M;i++)
{
p->num=i;
printf("%d號猴子：%d\n",p->num,p->num);
p=p->next;
}
return head1;
}

/*形成循環鏈表*/

/*從headP指向的循環鏈表中選大王，數到N的猴子淘汰，將依次淘汰出來的猴子插入到headPtr2指向的鏈表中*/
void selectKing(LINK head,int N,int M)/*N>=2*/
{
LINK p,p2,head2=NULL;
int i;
i=0;
p=head;//p指向第一個結點

while(1)
{
i++;
printf("%d號猴子報：%d\n",p->num,i);
if(p->next==p)
break;//此為while循環的出口

if(i==N)//if語句中是刪除結點的過程
{
i=0;
printf("%d號猴被淘汰\n",p->num);
printf("\n");
p2->next=p->next;//在此刪除結點p
p=p2->next;//p指向它的下一個結點
continue;
}
else
{
if(i==N-1)
p2=p;//保存將要退出結點的前一個結點（存到p2中）
p=p->next;

}

}
}

int main()
{
LINK head=NULL;
int M,N;

printf("輸入猴子數量:");
scanf("%d",&M); /*猴子個數*/
printf("輸入選定的一個小於猴子總數的數:");
scanf("%d",&N); /*count＝3，表示每次數到3的猴子出局*/

head=createList(M);/*創建循環鏈表*/

selectKing(head,N,M);/*選大王*/
return 0;
}

I. 數據結構課程設計題目：猴子選大王問題

我使用了另一種方法，不需要構建環形鏈表也可以，只需要用一個數組標記已離開的猴子即可，相對比較簡單。這個程序輸出猴子離開的順序，最後輸出的即為大王。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int main()
{
int m,n;
int *not_in;
int pos;
int i;
int j;

printf("m n = ");
scanf("%d%d", &m, &n);
assert(m > 0);
assert(n > 0);
not_in = (int *)malloc(sizeof(int)*(m + 1));
memset(not_in, 0, sizeof(int)*(m + 1));

pos = m;
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
do
{
pos++;
if (pos == m + 1)
pos = 1;
}
while (not_in[pos]);
}
printf("%d ", pos);
not_in[pos] = 1;
}
printf("\n");

return 0;
}