猴子选大王
发布网友
发布时间：2022-04-18 20:47
共4个回答
懂视网
时间：2022-04-19 01:08
m只猴子围坐成一个圈，按顺时针方向从1到m编号。然后从1号猴子开始沿顺时针方向从1开始报数，报到n的猴子出局，再从刚出局猴子的下一个位置重新开始报数，如此重复，直至剩下一个猴子，它就是大王。设计并编写程序，实现如下功能：
（1）要求由用户输入开始时的猴子数m、报数的最后一个数n。
（2）给出当选猴王的初始编号。
这道题是典型的约瑟夫环问题，“猴子选大王”问题。
注意：本实例在python2.7下测试通过，未在python3下测试，有兴趣的同学可以到群里交流
直接上代码：
#!/usr/bin/python
# coding=utf-8
# 约瑟夫环算法 之 猴子选王 问题
def king(m,n):
dd = {}
#生成一个字典
p = 1
while(p<=m):
dd[p] = p
p = p+1
j = 1
while(len(dd) >1):
for k,v in dd.items():
if(j == n):
del dd[k]
j = 1
else:
j = j+1
return dd
print king(6,2)注意：这里用到了字典，而不是list。主要是因为这样可以利用字典的索引的优势
热心网友
时间：2022-04-18 22:16
＃i nclude<iostream.h>
int choose(int num,int del)
{
int i;
int a[100];
for(i=0;i<num;i++)
a[i]=1; //猴子状态初始化，为1表示可能被选上，为0表明没希望了；
int sum=0, //循环记数；
countOne=num; //累积记数初始化，大于1表明还有大王候选人；
while(countOne>1)
{
countOne=0;
for(i=0;i<num;i++)
{
sum+=a[i];
if(sum==del)
sum=a[i]=0; //淘汰倒霉猴子；
countOne+=a[i];
}
}
for(i=0;i<num;i++)
if(a[i]!=0)
return i; //找到幸运猴子编号（从0开始的）；
}
void main()
{
int num,del;
cout<<"请输入猴子总数和淘汰数：";
cin>>num>>del;
cout<<"第"<<choose(num,del)+1<<"个猴子为王！"<<endl;
}
热心网友
时间：2022-04-18 23:34
更方便的方法就是用一个循环bool类型数组，加一个边界条件，模拟选择，每选出一个就输出，同时将该数组元素的真值设置为假。
热心网友
时间：2022-04-19 01:09
#include
<stdio.h>
int
main()
{
int
n;
int
n1=0;
//表示报数记数器
int
p=0;
//指向当前数组元素的下标
int
NumOfKing;
//大王的编号
int
M,K;
//M为已知猴子总数,K为报数的量级
int
a[1000];
FILE
*fp1,*fp2;
if((fp1=fopen("monkey.in","r"))==NULL)
{
printf("cann't
open
file!\n");
return
0;
}
fscanf(fp1,"%d%d",&M,&K);
//从文件中读取已知数据
n=M;
//M为圈的长度，即初始猴子数
for(int
i=0;i<n;i++)
a[i]=1;
//初试话状态数组，所有猴子都是就位的
while(n>1)
//n当前圈内还剩下的猴子数,控制循环在圈内只剩下一只猴子时结束循环
{
while(n1<K)
//n1表示报数记数器，每报一次n1加1，直到报完k个数之后结束此循环
{
if(a[p]==1
)
//如果当前位置有猴子
{
n1++;
//报数记数器加1
if(n1==K)
a[p]=0;
//将第K次报数的猴子置0，表示退出圈子
}
p++;
//移动到下一个位置
p=p%M;
//这一步是为了解决循环数组成环遍历的目的
}
n1=0;
//当报完K个数后将报数记数变量清0，以备下次重新报数
n--;
//当报完一轮后总猴子数减1
}
for(int
i=0;i<M;i++)
//最后遍历一遍状态数组
找到状态为1的下标i+1即为猴子大王的编号
{
if(a[i]==1)
{
NumOfKing=i+1;
break;
}
}
fp2=fopen("monkey.out","w");
fprintf(fp2,"%d",NumOfKing);
fclose(fp1);
fclose(fp2);
return
0;
