一群猴子要选新猴王。新猴王的选择方法是:让N只候选猴子围成一圈,从某位置起顺序编号为1~N号。从第1号开始报数,每轮从1报到3,凡报到3的猴子即退出圈子,接着又从紧邻的下一只猴子开始同样的报数。如此不断循环,最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王?
这个是最基础的约瑟夫环
用数组 或者链表实现均可。
数组实现如下:
#include<stdio.h>#define MAX 1005
int main(void){
int monkey[MAX]={0}
int n,temp=0
int monkeyOut=0
int count = 0
scanf("%d",&n)
do{
temp++//逐个枚举圈中的所有位置
if(temp>n)
temp=1//数组模拟环状,最后一个与第一个相连
if(!monkey[temp])
count++//第t个位置上有人则报数
else
continue
if(count==3){//当前报的数是count
count=0//计数器清零
monkey[temp]=1//此猴已经退出,状态设为1,表示已经退出
monkeyOut++//退出猴的数目加一
}
}while((monkeyOut+1)!=n)
int i
for(i=1i<=n++i){
if(!monkey[i]){
printf("%d\n",i)
break}
}
return 0
}
一群猴子要选新猴王。新猴王的选择方法是:让M只候选猴子围成一圈,从某位置起顺序编号为1~M号。从第1号开始报数,每轮从1报到N,凡报到N的猴子即退出圈子,接着又从紧邻的下一只猴子开始重新报数。如此不断循环,最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王?思路1:
利用数组int n[M],都初始化为1,淘汰的标记为0,往复循环操作,剩下最后一个数组元素1的下标+1即是答案。
参考代码:
#include <iostream>
using namespace std
int whoIsMonkeyKing(int,int )
int main()
{
cout<<whoIsMonkeyKing(21,3)<<endl
return 0
}
int whoIsMonkeyKing(int m,int n) //m为猴子个数,n为最大报数
{
if(m<1 || n<1)
{
cout<<"输入参数错误"<<endl
return -1
}
int *p = new int[m]
int *q = p,M = m
int res
for(int i=0i<mi++)
{
p[i]=1
}
while(M!=1)
{
int i=0
while(i!=n)
{
if(q==p+m)
{
q = p
}
if(*q++==1)
{
++i
}
}
*(q-1) = 0
--M
}
for(int i=0i<mi++)
{
if(*(p+i)==1)
{
res = i+1
break
}
else
continue
}
delete[] p
return res
}
#include<stdio.h>#include<stdlib.h>
main()
{ int a[50]
int i,j,M,N,t=0
printf("input two number.\n")
scanf("%d %d",&N,&M)
for(i=0i<Ni++)
a[i]=i+1
for(j=1,i=0j++,i++)
{
if(i==N)i=0
if(a[i]==0){j--continue}
if(j%M==0){a[i]=0t++}
if(N-t==1)break
}
for(i=0i<Ni++)
if(a[i]!=0) printf("猴王是第%d个.\n",a[i])
system("pause")
}
试试...