Question

数据结构课程设计题目：猴子选大王问题

数据结构课程设计题目：
课题要求：输入数据：输入m,n 其中m,n 为整数，n输出形式：提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号
课题内容：任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1到m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

课题难度：80

Answer 1

一：实验内容：
M只猴子要选大王，选举办法如下：所有猴子按1，2……n编号围成一圈，从第一号开始顺序1,2……m,凡是报m号的退出圈外，如此循环报数直到圈内只剩一只猴子时这只猴子就是大王。
二：实验要求：
利用单向循环链表模拟此过程，输出选出的大王编号。
三：程序的设计思想：
（1） 问题分析：“猴子选大王”问题是约瑟夫环问题的一个特例。由于本题目的数据元素个数不可知，所以可使用链表来动态的分配内存空间。而该问题又是一个不断的循环问题所以用循环链表来实现。
（2） 总体设计：首先生成一个空链表，并给n个结点分配空间，让单链表的表尾指针指向头结点则生成一个带有n个结点的循环单链表。再给每只猴子建立顺序的编号。现从第一个结点开始报数，依次顺序查找出报数为m的待出列的结点（猴子）通过q->next=p->next删除该结点后继续运行否则让q成为p的前驱指针。最后当p->next==p时停止运行，得到p所指向的结点即为猴子选出大王的编号。
四、源程序

#include <stdio.h>

#include <stdlib.h>

/* 定义链表节点类型 */

typedef struct node

{

int data;

struct node *next;

}linklist;

int main()

{

int i, n, k, m, total;

linklist *head, *p, *s, *q;

/* 读入问题条件 */

printf("Please enter the number of monkeys:");

scanf("%d", &n);

printf("Please enter from the monkeys began to count off the first of several:");

scanf("%d", &k);

printf("Please enter the number out:");

scanf("%d", &m);

/* 创建循环链表，头节点也存信息 */

head = (linklist*) malloc(sizeof(linklist));

p = head;

p->data = 1;

p->next = p;

/* 初始化循环链表 */

for (i = 2; i <= n; i++)

{

s = (linklist*) malloc(sizeof(linklist));

s->data = i;

s->next = p->next;

p->next = s;

p = p->next;

}

/* 找到第 k 个节点 */

p = head;

for (i = 1; i < k; i++)

{

p = p->next;

}

/* 保存节点总数 */

total = n;

printf("\nOut of sequence:");

q = head;

/* 只剩一个节点时停止循环 */

while (total != 1)

{

/* 报数过程，p指向要删除的节点 */

for (i = 1; i < m; i++)

{

p = p->next;

}

/* 打印要删除的节点序号 */

printf("[%d] ", p->data);

/* q 指向 p 节点的前驱 */

while (q->next != p)

{

q = q->next;

}

/* 删除 p 节点 */

q->next = p->next;

/* 保存被删除节点指针 */

s = p;

/* p 指向被删除节点的后继 */

p = p->next;

/* 释放被删除的节点 */

free(s);

/* 节点个数减一 */

total--;

}

/* 打印最后剩下的节点序号 */

printf("\n\n King of the Monkey is the No. [%d] \n\n", p->data);

free(p);

system("pause");

return 0;

}

Answer 2

我使用了另一种方法，不需要构建环形链表也可以，只需要用一个数组标记已离开的猴子即可，相对比较简单。这个程序输出猴子离开的顺序，最后输出的即为大王。
#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;
}