根据问题描述可知，该问题中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=0i<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
我用java写了一个，也是给人帮忙啦，可以给兄台参考参考，有空的话，给你改个指针版出来MonkeyNumber.java源程序如下：
package test
import java.util.Scanner
/**
* @author Administrator
*
* 有M只猴子围成一圈，每只各一个从1到M中的编号，
* 打算从中选出一个大王；经过协商，决定出选大王的规则：从第一个开始循环报数，
* 数到N的猴子出圈，最后剩下来的就是大王。
* 要求：从键盘输入M、N，编程输出猴子出列的次序并计算哪一个编号的猴子成为大王（用数组实现）。
* 要求程序完整，并且验证过，
*
*/
public class MonkeyNumber {
/**
* 出圈
* <b>方法描述</b>：第outNo号出圈 <p>
* <b>方法流程</b>：
* <p>
* @param monkey
* @param n
* @return outNo 出圈的索引号
*/
private static int getOut(int[] monkey,int n){
int outNo = -1
int intValidVoters = getVotersNumber(monkey)
for(int i=0i<monkey.lengthi++){
if(intValidVoters >n){
if(monkey[i]==n%intValidVoters){
outNo = i+1
monkey[i]=-1// 去除该位置的值
System.out.print("--编号为["+outNo+"]的猴子出圈！--")
return outNo
}
}
else if(intValidVoters <n){
if(monkey[i]==(n%intValidVoters==0?intValidVoters:n%intValidVoters)){
outNo = i+1
monkey[i]=-1// 去除该位置的值
System.out.print("--编号为["+outNo+"]的猴子出圈！--")
return outNo
}
}
else if(intValidVoters==n){
if(monkey[i]==n){
outNo = i+1
monkey[i]=-1// 去除该位置的值
System.out.print("--编号为["+outNo+"]的猴子出圈！--")
return outNo
}
}
}
return outNo
}
/**
* 重新初始化数组
* <b>方法描述</b>：对输入的数组重新进行赋初值 <p>
* <b>方法流程</b>：
* <p>
* @param monkey
* @param startPos 从startPos位置开始赋初值，startPos索引的数组，其值置为1
*/
private static void reAssign(int[] monkey, int startPos){
int count = 0
//数组中大于等于位置startPos的有效值的个数
int behindCount = getVotersNumber(monkey, startPos)
//对号码重新初始化
for(int i=0i<monkey.lengthi++){
int differenceValue = i-startPos+1
if(monkey[i] != -1){
if(differenceValue <0){
monkey[i]= ++behindCount
}
else if(differenceValue >= 0){
monkey[i]= ++count
}
}
}
}
/**
* <b>方法描述</b>：取得当前有效选民数 <p>
* <b>方法流程</b>：
* <p>
* @param monkey
* @return
*/
private static int getVotersNumber(int[] monkey){
int count = 0
//计算目前多少个号码有效
for(int i=0i<monkey.lengthi++){
if(monkey[i] != -1){
count++
}
}
System.out.print("当前有["+count+"]只猴子参加选举！")
return count
}
/**
* <b>方法描述</b>：取得大于等于位置startPos的有效选民数 <p>
* <b>方法流程</b>：
* <p>
* @param monkey
* @return
*/
private static int getVotersNumber(int[] monkey,int startPos){
int count = 0
//计算目前多少个号码有效
for(int i=startPosi<monkey.lengthi++){
if(monkey[i] != -1){
count++
}
}
return count
}
/**
* <b>方法描述</b>：主程序 <p>
* <b>方法流程</b>：测试
* <p>
* @param args
*/
public static void main(String[] args){
System.out.println("Input:M N ")
Scanner scanner = new Scanner(System.in)
String strM = scanner.next()
String strN = scanner.next()
while (strM == null || !strM.matches("[0-9]+")){
System.out.println("输入错误，您输入的第一个参数不是数字，请再次输入:")
scanner = new Scanner(System.in)
strM = scanner.next()
}
while (strN == null || !strN.matches("[0-9]+")){
System.out.println("输入错误，您输入的第二个参数不是数字，请再次输入:")
scanner = new Scanner(System.in)
strN = scanner.next()
}
int m = Integer.parseInt(strM)
int n = Integer.parseInt(strN)
System.out.println("当前有::["+m+"]只猴子"+",即将报的数是::["+n+"]")
int monkey[] = new int[m]
//赋初值
for(int i=0i<mi++){
monkey[i]=i+1
}
for(int i=0i<m-1i++){
//出圈
int outNum = getOut(monkey,n)
int startPos = -1
if(outNum==m){
startPos = 0
}
else{
startPos = outNum
}
//再次循环赋初值
reAssign(monkey,startPos)
System.out.println()
}
for(int i=0i<mi++){
if(monkey[i]!=-1){
System.out.println("Voting Success!!!编号为["+(i+1)+"]的猴子成为大王！")
}
}
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）