[C++知识库]猴子选大王2 c++

题目描述

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

输入格式

输入在一行中给一个正整数N（N<1000）

输出格式

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

输入输出样列

输入样例1：复制

5

输出样例1：复制

3

【耗时限制】1000ms 【内存限制】128MB

答案

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
int f[999999];
int main(){
?? ?int n;
?? ?cin>>n;
?? ?int s=0;
?? ?for(int i=1;i<=n-1;i++){
?? ??? ?for(int j=1;j<=2;){
?? ??? ??? ?s=(s+1)%n;
?? ??? ??? ?if(s==0){
?? ??? ??? ??? ?s=n;
?? ??? ??? ?}
?? ??? ??? ?if(f[s]==0){
?? ??? ??? ??? ?j++;
?? ??? ??? ?}?? ?
?? ??? ?}
?? ??? ?f[s]=1;
?? ?}
?? ?for(int i=1;i<=n;i++){
?? ??? ?if(f[i]==0){
?? ??? ??? ?cout<<i;
?? ??? ??? ?return 0;?
?? ??? ?}
?? ?}
?? ?return 0;
}