数据结构课程设计题目:猴子选大王问题
发布网友
发布时间：2022-04-25 14:51
共2个回答
热心网友
时间：2022-04-18 22:16
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;
}
热心网友
时间：2022-04-18 23:34
#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;
}
