Time Limit: 3 second
Memory Limit: 2 MB
N只猴子选大王。选举办法如下：从头到尾1、2、3报数，凡报3的退出，余下的从尾到头1、2、3报数，凡报3退出；余下的又从头到尾报数，还是报3的退出；依此类推，当剩下的两只猴子时，取这时报数报1的为王。若想当猴王，请问当初应占据什么位置？
例如：输入猴子最初的只数N:10
输出想当猴王当初应占据的位置：8
Input
输入猴子最初的只数n（n<=200)
第一行输入N的值
Output
输出想当猴王当初应占据的位置
Sample Input
10
Sample Output
8
【题解】
for 3次表示跳3个格子，而每层for中又用一个while以此来跳过那些已经被选过的猴子。在这之前j =1;然后j =n;再试一次。反过来后j没有必要再等于1，因为反过来的时候停在了最前面的猴子位置处。正向的时候要找的也正是这个，就算这个位置已经被占过了，也没有影响。正向找之前先判断一下是不是剩两只，正向找完后再判断是不是只剩两只，只剩两只后可以特判一下，这个特判可以用一个过程来完成，用数字来表示特判的方向（即从前往后扫还是从后忘前扫，扫描到的第一个数字就是答案）
【代码】
#include <cstdio>
const int MAXN = 200;
int n,po[4],rest;
bool bo[MAXN + 10];
void input_data()
{
scanf("%d",&n);
rest = n;
for (int i = 1;i <= MAXN+9;i++) //初始化
bo[i] = true;
}
void output_ans(int l) //这是剩下两个的情况时 特判的方向 也即输出答案。
{
if (l == 1)
{
int j = 1;
while (!bo[j]) j++; //这是跳过已经被选过的猴子的方法
printf("%d",j);
}
else
{
int j = n;
while (!bo[j]) j--; //反向扫描
printf("%d",j);
}
}
void get_ans()
{
if (n == 1) //特判只有一只猴子的情况
{
printf("1");
return;
}
int j = 1; //从第一个开始扫描
bool flag = false;
while (!flag)
{
if (rest == 2) //如果只剩两只就输出答案。把这句放前面可以使得程序适用于n=2的情况
{
output_ans(1);
return;
}
while (j <n) //只要j<n就可以继续数 不用等于n 因为等于n只能数一次了。不可能够3次
{
for (int k = 1;k <= 3;k++) //跳过那些被数过的猴子 再数3次。
{
while (!bo[j]) j++; //跳过数过的猴子。
if (j > n) break; //如果超过了n 就表示已经不够数3次了
if (k == 3) //如果数了3次就将当前数到的猴子置为已数过
{
bo[j] = false;
rest--; //减少了一只猴子
}
j++; //继续数下一只
if (j >n) break; //大于n同样不能数了。
}
}
if (rest == 2) //只剩两只的话输出答案。
{
output_ans(2);
return;
}
j = n; //接下来反过来数
while (j > 1) //只要大于1 就可以继续数
{
for (int k = 1;k <= 3;k++)
{
while ( (j >=2) && (!bo[j])) j--; //这是防止数组下标溢出。所以判断条件是>=2
if ( (j == 1) && (!bo[j])) break; //这是不满足的情况 跳出。因为j到了1 而且第一只还已经被数过了
if (k == 3)
{
bo[j] = false;
rest --;
}
j--;//继续往前找
if ( j < 1) break;
}
}
}
}
int main()
{
input_data();
get_ans();
return 0;
}