猴子选大王n只猴子围坐成一个圈,按顺时针方向从1到n编号.然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数,如此重复,直至剩下一个

Question

猴子选大王
n只猴子围坐成一个圈,按顺时针方向从1到n编号.然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数,如此重复,直至剩下一个猴子,它就是大王.设计并编写程序,实现如下功能：
（1）\x05要求由用户输入开始时的猴子数n、报数的最后一个数m.
（2）\x05给出当选猴王的初始编号.

Answer 1

1.需求分析：
根据问题描述可知,该问题中m个猴子围坐在一起形成首尾相接的环,因此可用循环链表解决.从第n个猴子开始出列相当于从链表中删除一个结点.该程序主要有三个模块组成,建立单链表,报数利用do-while循环实现猴子的出列,最终剩下的猴子即猴王.具体步骤如下：
第一步 首先创建循环链表.
第二步 向单链表中填入猴子的编号
第二步 找第一个开始报数的猴子.
第三步 数到n让这个猴子出列.
第四步 接着开始报数,重复第三步


2.概要设计（流程图）

开始

定义结构体,变量

建立循环单链表

在循环链表填入数据

猴子数数Count++

Count= = n-1?


释放第n个猴子


指针q指向第n+1个节点q=q->next

否

q->next= =q?




是
猴王就是第q-〉data 个猴子


结束




3.详细设计：
#include
#include
struct Node
{
int data;
struct Node *next;
};
int main()
{
struct Node *head, *s, *q, *t;
int n, m, count=0, i;
printf("input the number m:");
scanf("%d",&m);
printf(" input the number n:");
scanf("%d",&n);
for(i=0; i< i++)>
{
s=(struct Node *)malloc(sizeof(struct Node));
s->data=i+1;
s->next=NULL;
if(i= =0)
{
head=s;
q=head;
}
else
{
q->next=s;
q=q->next;
}
}
q->next=head;
printf("before:");
q=head;
while(q->next!=head)
{
printf("%d ",q->data);
q=q->next;
}
printf("%d ",q->data);
q=head;
printf(" ");
do {
count++;
if(count= =n-1)
{
t=q->next;
q->next=t->next;
count=0;
printf("%d ", t->data);
free(t);
}
q=q->next;
}
while(q->next!=q);
printf(" the king is: %d ",q->data);
}
4.测试数据：
1）input the number m:20
input the number n:5
before:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5 10 15 20 6 12 18 4 13 1 9 19 11 3 17 16 2 8 14
the king is: 7
2）input the number m:9
input the number n:11
before:1 2 3 4 5 6 7 8 9
2 5 9 7 8 4 1 3
the king is: 6
3）input the number m:10
input the number n:5
before:1 2 3 4 5 6 7 8 9 10
5 10 6 2 9 8 1 4 7
the king is: 3