一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。要求:m及n从键盘输入,存储方式采用数组及链表两种方式实现该问题求解。 用c语言
时间: 2023-05-25 21:06:00 浏览: 45
数组实现:
#include <stdio.h>
#define MAX 100 //最大编号数
int monkeys[MAX]; //猴子数组
int n, m; //n为数到第n个,m为猴子数目
int main()
{
printf("请输入猴子数目m和数到第n个离开:");
scanf("%d%d", &m, &n);
int i, j, k;
for (i = 0; i < m; i++)
{
monkeys[i] = i + 1; //编号从1开始,数组下标从0开始
}
int left = m; //剩余猴子数目
int count = 0; //数数
i = -1; //从最后一只猴子开始数
while (left > 1)
{
i = (i + 1) % m; //循环计数
if (monkeys[i] != 0) //如果该猴子还在圈中
{
count++;
if (count == n) //数到第n个猴子
{
monkeys[i] = 0; //该猴子离开
count = 0; //重置计数
left--; //剩余猴子数目减1
}
}
}
//输出最后一只猴子编号
for (i = 0; i < m; i++)
{
if (monkeys[i] != 0)
{
printf("最后一只猴子编号为:%d\n", monkeys[i]);
break;
}
}
return 0;
}
链表实现:
#include <stdio.h>
#include <stdlib.h>
//定义猴子结构体
typedef struct monkey
{
int num; //猴子编号
struct monkey *next; //下一个猴子
}Monkey;
int n, m; //n为数到第n个,m为猴子数目
//生成循环链表
Monkey* createList(int m)
{
Monkey *head = NULL; //链表头指针
Monkey *prev = NULL; //前一个猴子指针
int i;
for (i = 1; i <= m; i++)
{
Monkey *p = (Monkey*)malloc(sizeof(Monkey)); //生成新猴子
p->num = i; //赋值编号
if (i == 1) //如果是第一个
{
head = p; //头指针指向它
}
else
{
prev->next = p; //前一个猴子的next指针指向它
}
p->next = head; //新猴子的next指针指向头指针,形成循环链表
prev = p; //更新前一个猴子指针
}
return head;
}
int main()
{
printf("请输入猴子数目m和数到第n个离开:");
scanf("%d%d", &m, &n);
//生成循环链表
Monkey *head = createList(m);
Monkey *p, *prev;
int left = m; //剩余猴子数目
int count = 1; //从第一个猴子开始数
prev = head; //从头指针开始计数
while (left > 1)
{
p = prev->next; //p指向下一个猴子
count++;
if (count == n) //数到第n个猴子
{
prev->next = p->next; //前一个猴子的next指针指向下下一个猴子
free(p); //该猴子离开
count = 0; //重置计数
left--; //剩余猴子数目减1
}
else
{
prev = p; //更新前一个猴子指针
}
}
//输出最后一只猴子编号
p = prev;
while (p->next != p) //循环查找最后一只猴子
{
p = p->next;
}
printf("最后一只猴子编号为:%d\n", p->num);
return 0;
}