猴子选大王,一般是用循环队列或者链表来做
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
你现在初始共有几个人,怎么开始有31,count<=28,保证最后会留下一个数?
最后,程序的要求是只要最后一个数,还是要出列的全部过程?
这个我觉得只能逐个模拟,满足相应条件回归,比如满3归0,到30号归1,只剩下1个,结束,单纯用J%3,J++,应该实现不了