一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？
输入格式：
输入在一行中给一个正整数 N（≤ 1000）。
输出格式：
在一行中输出当选猴王的编号。
输入样例：
11
输出样例：
7
解题思路：
- 第一种方法（算法一）：
给每个猴子初始设为 0，退出时就置为 1，最后检查数组中的数字，是 0 就输出。难点在于让判断循环进行以及循环出口。- 让判断循环进行：当 i == N 时，将其置 0，这样就能继续循环。
- 循环出口：直到退出的猴子数等于 N-1，就是还剩一只猴子就退出。
- 第二种方法（算法二）：
增加一个数组，每次将数组筛选，将剩下的猴子放进新的数组里。直到数组里就剩 2 只猴子（与筛选算法有关）。在文章的最后会解释算法二中的一点小细节。
另外，要注意数组的初始化
scanf("%d", N);
int a[N]={0};
初始化的时候 N 的值需要已知。初始化是在编译时完成。所以 N 尚未输入。这样就会产生错误。解决方法是用一个 for 循环完成初始化。
解题代码：
算法一
#include<stdio.h>
int main ()
{
int N, i;
scanf("%d", &N);
int a[N+1]; //舍弃 a[0],方便给猴子编号
for (i=1; i<N+1; i++) { //初始化数组
a[i] = 0;
}
int count = 0, quit = 0;
if (N != 1) {
for (i=1; i<N+1; i++) {
if (a[i] == 0) count ++;
if (count % 3 == 0 && a[i] == 0) {
a[i] = 1; // 退出的猴子标记为 1
quit ++;
if ( quit == N-1) break;
}
if (i == N) i = 0; //让其循环
}
}
for (i=1; i<N+1; i++) {
if (a[i] == 0) {
printf("%d\n", i);
break;
}
}
return 0;
}
算法二
#include<stdio.h>
int main ()
{
int N, i;
scanf("%d", &N);
int a[N+1]; // 舍弃 a[0],方便给猴子编号
for (i=1; i<N+1; i++) { //初始化数组
a[i] = i;
}
int count;
int b[N+1]; // 舍弃 b[0],方便给猴子编号
while (N > 2) {
for (i=1; i<=N; i++) {
if (i == 1) {
switch (N % 3) {
case 0: count = 1; break;
case 1: count = 2; break;
case 2: count = 3; break;
} // 算法的下方会给出讲解
}
if (i%3 != 0 && i<=N/3*3) {
b[count++] = a[i];
}
if (i%3 != 0 && i>N/3*3) {
switch (N % 3) {
case 0: break;
case 1: b[1] = a[i]; break;
case 2:
if (i == N) {
b[1] = a[i-1];
b[2] = a[i];
}
break;
}
}
}
N = count - 1;
for (i=1; i<=count-1; i++) {
a[i] = b[i];
} // 将新的数组 b 赋给原数组 a
}
if (N == 1) {
printf("1\n");
} else {
printf("%d\n", a[2]);
}
return 0;
}
算法二中的一点细节：
if (i == 1) {
switch (N % 3) {
case 0: count = 1; break;
case 1: count = 2; break;
case 2: count = 3; break;
} // 算法的下方会给出讲解
}
在形成新的数组之后，要从第一个开始访问，当 N 不同的时候，第一个的情况会有所不同，所以有了上面的处理。
-
比如 N = 3 时，
a[i] 1 2 3 猴子编号 1 2 3↓ｂ[count] 1 2 猴子编号 1 2 当 N 恰为 3 的倍数时，下一次从猴子 1 号开始数。所以 switch 那里将 b 的初始指针设为了 1。
-
而当 N = 4 时，
a[i] 1 2 3 4 猴子编号 1 2 34 ↓ｂ[count] 1 2 3 猴子编号 4 1 2 当 N 为 4 的时候，下一次从猴子 4 号开始数，所以 switch 那里将 b 的初始指针设为了 2。把 b[1] 的位置留给 4 号猴子。
-
而当 N = 5 时，
a[i] 1 2 3 4 5 猴子编号 1 2 34 5 ↓ｂ[count] 1 2 3 4 猴子编号 4 5 1 2 当 N 为 5 的时候，下一次从猴子 4 号开始数，所以 switch 那里将 b 的初始指针设为了 3。把 b[1] 的位置留给 4 号猴子，b[2] 的位置留给 5 号猴子。