猴子选大王

• 初级
• 进阶版：

初级

一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入格式：
输入在一行中给一个正整数N（≤1000）。

输出格式：
在一行中输出当选猴王的编号。

输入样例：

11

输出样例：

7

示例：

#include
int main(){int n,sum=0;scanf("%d",&n);for(int i=2;i<=n;i++)sum=(sum+3)%i;printf("%d",sum+1);return 0;
}//https://www.jianshu.com/p/6ee5c7b21333   约瑟夫环问题的数学解

正常解：

#include
int main()
{int n,i,t=0,q=0;scanf("%d",&n);int a[n+1];for(i=1;i<=n;i++)a[i]=0;if(n!=1){for(i=1;i<=n;i++){if(a[i]==0)t++;if(a[i]==0&&t%3==0){a[i]=1;q++;if(q==n-1)break;}if(i==n)i=0;}}for(i=1;i<=n;i++){if(a[i]==0){printf("%d\n",i);break;}}return 0;
}

进阶版：

【例题描述】
由M只猴子围成一圈，从1到M进行编号，打算从中选出一个大王，经过协商，决定选出大王的规则：从第一个开始循环报数，
数到N的猴子出圈，下一个猴子从1开始报数。

输入样例：

6 2
12 4 
8 3
0 0

输出样例：

5
1
7

原文章：（点我）

这个解法只能一次次地进行测试，没法等都输入完了再进行测试。
里面代码有错误，我给改一下。
方法1的改好的代码：

#include
using namespace std;
#define MAX 100
long a[MAX+1];
long m,n,i,Count,k;
int main()
{cin>>m>>n;for(i=1;i<=m;i++)a[i]=1;k=m;			//报数前，指向该数的前一只猴子for(i=1;i<=m;i++)//出圈M只猴子{Count=0;		//报数前，个数为0while(Count<n)//当前报数{if(k==m)//从最后一个位置移动到第一个位置k=1;elsek++;if(a[k]==1)//当前猴子在圈内，报数Count++;}a[k]=0;//猴子K出圈}cout<<k<<endl;return 0;
}

方法3改好的代码：

#include
using namespace std;
int main()
{
int i,m,k,ans;
cin>>m>>k;
ans=0;
for(i=2;i<=m;i++)
ans=(ans+k)%i;
cout<<ans+1<<endl;//因为这里的位次是从0开始的k%k=0.
}
//博主这部分打错了，我给你改上。

方法一改良版：可以先大批量输入三次：

#include
using namespace std;
#define MAX 100
long a[MAX+1];
long m,n,i,Count,k[3];
int main()
{int p=0;cin>>m>>n;while((m!=0)&&(n!=0)){for(i=1;i<=m;i++)a[i]=1;k[p]=m;			//报数前，指向该数的前一只猴子for(i=1;i<=m;i++)//出圈M只猴子{Count=0;		//报数前，个数为0while(Count<n)//当前报数{if(k[p]==m)//从最后一个位置移动到第一个位置k[p]=1;elsek[p]++;if(a[k[p]]==1)//当前猴子在圈内，报数Count++;}a[k[p]]=0;}p++;cin>>m>>n;}cout<<k[0]<<endl<<k[1]<<endl<<k[2];return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！