【2005】N只猴子选大王

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

Sample Output

【题解】

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;

}

巴特西

【2005】N只猴子选大王

Input

Output

Sample Input

Sample Output

最新文章

热门文章