题目：猴子选王 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。
#include <stdio.h>
struct monkey
{
int num;
monkey *next;
};
monkey *head,*tail;
void creat(int n)
{
int i;
monkey *p,*q;
p=new monkey; //为p分配内存空间
p->num=1; //初始化p结点num域为1
p->next=NULL; //初始化p结点next域为空
head=p; //链表头指针head赋值为p
q=p;
for(i=2;i<=n;i=i+1) //循环存入猴子
{
p=new monkey; //为p配内存空间
p->num=i; //初始化p结点num域为i，表示猴子号 q->next=p; //将p点加到链表尾部
q=p; //让指向链表尾部结点
p->next=NULL; //链表尾部指向空
}
tail=q; //链表尾
tail->next=head; //链表尾部指向链表头，形成循环链表 }
void select(int n)
{
int x=0;
monkey *p,*q;
q=tail; //q赋值给tail，指向循环链表尾部
do //直到型循环，用于循环删除指定间隔的结点 {
p=q->next; //p赋值给相邻的下一个结点
x=x+1; //x加1
if(x%n==0) //x是否整除m
{
printf("%d号猴子淘汰\n",p->num);
q->next=p->next; //删除此结点 delete p; //释放空间
p=NULL;
}
else q=p; //q指向相邻的下一个结点p }while(q!=q->next); //剩余结点数不为1，则继续循环 head=q; //head指向结点q,q为链表中剩余的一个结点
}
void main()
{
int n,m;
head=NULL; //初始化head为空
printf("请输入猴子的个数\n");
scanf("%d",&m);
printf("请输入n\n");
scanf("%d",&n);
creat(m); //调用函数creat建立循环链表
select(n); //调用函数select，找出剩下的猴子 printf("猴王是%d号\n",head->num); //输出猴王
delete head; //删除循环中最后一个结点
}
#include<stdio.h>
int main()
{
int a[1000];//定义一个较大的数组存储数据
int m,n,x,count,i;//定义猴子数m、输入n、所需变量x、cout、i printf("请输入猴子个数:\n");//提示输入m
scanf("%d",&m);
printf("请输入n:\n");//提示输入n
scanf("%d",&n);
for(i=1;i<=m;i++) //令数组与猴子编号对应
a[i]=i;
count=m;//令cout等于猴子个数
x=0;//令x初始值为零
for(i=0;count>1;i++)// 执行循环，淘汰的猴子值为-1，直到只剩一只猴子，即为猴王
{
if(a[i%m+1]!=-1) {x++;}
if(x==n&&a[i%m+1]!=-1)
{a[i%m+1]=-1;count--;x=0;printf("%d号猴子淘汰\n",i%m+1);} }
for(i=1;i<=m;i++) //输出值不为-1的猴子，即猴王
if(a[i]!=-1) printf("猴王是%d号\n",i);
}
第二篇：猴子选大王C语言课程设计
猴子选大王
一、设计目的
1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
2、提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。
4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
5、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。
二、设计内容
1、系统名称：猴子选大王
按照规定的要求，选出最后的一只猴子，为大王。
2、要求：
一堆有编号的猴子，编号为1，2，3……m，这群猴子（m个）按照1-m的顺序围坐一圈，从第一开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中剩下最后一只猴子，则该猴子为大王。
三、程序设计步骤
1）采用主要的数据结构类型。
采用了链表的存储方式，属于链接存储结构。
1
for(i=1;i<n;i++) //建立链表的存储结构
{
p=(LINK)malloc(sizeof(Monkey));
p2->next=p;
p2=p;
}
以下是用于存储结点的结构体的定义:
typedef struct monkey
{
int num;
struct monkey *next;
} Monkey,*LINK;
基本算法：
这个算法的主要流程为：
从控制台读取猴子的数量和报数的最大数——>对猴子进行编号，并用链表来存储——>让链表中的猴子进行报数，对于报数为m的猴子则从链表中删除——>当链表中只剩下一个报数后则停止这个过程，这最后一个猴子即选出来的大王。
以下为为猴子建立链表：
for(i=1;i<n;i++) //建立链表的存储结构
{
p=(LINK)malloc(sizeof(Monkey));
p2->next=p;
p2=p;
}
以下为猴子进行编号： for(i=1;i<=n;i++) //对猴子进行编号 { p->num=i; //printf("%d号猴子：%d\n",p->num,p->num); p=p->next;
}
以下为最主要的算法过程，是通过一个While循环来控制的，是让猴子报数的过程，并删除报数为m的猴子：
while(1)
{
i++;
//当链表只剩最后一个元素了则跳出循环，此时报数已完成 printf("%d号猴子报：%d\n",p->num,i);if(p->next==p) break; if(i==m) { i=0; printf("%d号猴被淘汰\n",p->num); printf("\n"); 2
p2->next=p->next;
p=p2->next;
continue;
}
else
{
if(i==m-1) p2=p;
p=p->next;
}
}
2）详细设计：
#include <stdio.h>
#include <stdlib.h>
int n=2;
int m=1;
typedef struct monkey
{
int num;
struct monkey *next;
} Monkey,*LINK;
void main()
{
printf("请输入一个整数（猴子数量）：");
scanf("%d",&n);
printf("请输入一个小于猴子数量的整数（报数的最大数）："); scanf("%d",&m);
LINK p,head,p2;
int i;
head=p=p2=(LINK)malloc(sizeof(Monkey));
for(i=1;i<n;i++) //建立链表的存储结构
{
p=(LINK)malloc(sizeof(Monkey));
p2->next=p;
p2=p;
}
p2->next=head;
p=head;
//printf("对猴子进行编号！\n");
for(i=1;i<=n;i++) //对猴子进行编号
{
p->num=i;
//printf("%d号猴子：%d\n",p->num,p->num); p=p->next;
3
}
} i=0; p=head; while(1) { i++; //当链表只剩最后一个元素了则跳出循环，此时报数已完成 printf("%d号猴子报：%d\n",p->num,i);if(p->next==p) break; if(i==m) { i=0; printf("%d号猴被淘汰\n",p->num); printf("\n"); p2->next=p->next; p=p2->next; continue; } else { if(i==m-1) p2=p; p=p->next; } } printf("胜出:%d",p->num);
四、调试分析
调试的过程中，对程序做了几点改进，增加了程序的容错能力，不论用户输入什么内容，程序都能安全检查。
这个算法主要考察了对数据存储方式的处理和循环判断的处理。我在这里用了链表的存储方式。
4
五、测试结果
调试得到输出结果如图： 当输入n为8，m为5时的运行结果：
5
六、课程设计小结：
猴子选大王是一个能让人产生较大兴趣的问题，因此编写程序实现之是一件很有意思的事。为编写这个程序的代码及写课程设计报告，我们花了两周的时间，下面说说我们在这期间的感悟。
在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程构思中选算法是一个很重要的概念，只有确定用这么算法后才能接下来的工作，将流程图画在纸上，再依次编写代码，在程序设计中，编写代码只是一个方面，调试才是关键。它是一个相当繁琐的过程，有许多新的问题需要被解决，但同时它
6
也是一个比较重要的过程，因为在程序调试过程中，你会学到很多新的东西，从而增加你编程的经验。
做任何一件事情都需要一个过程，在这个过程中，面对许多问题，我们尽最大的努力寻找解决方法，现学现用新的知识，不断积累经验，为未来的发展打下基础。我们是在学习，但是我们真正要学的是学习的能力，我们享受这个过程，因为它引领我们进步！
7