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

输入格式：

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

输出格式：

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

输入样例：

11

输出样例：

7

思路

约瑟夫环经典问题。有两个解法：

1. 模拟淘汰过程，穷举遍历；
2. 数学方法归纳（递归）；

代码在下面分别列出，这里讲一讲方法二的思路：

假设有 num 个猴子，它们的编号是0 ~ (num-1)，顺时针从0开始报数，报到 out-1 号就出列，剩下的猴子继续从0开始报数。第一个出列的猴子：(out - 1) % num。当第一个猴子出列后，剩下 num-1 个猴子，继续报数到 out-1 出列，本题要求出最后一个出列的猴子。

每处理一次，问题规模就缩小一次。想求 num 个猴子谁是大王，可以先求 num-1 个猴子谁是大王；而对于 num-1 个猴子，又可以分解成 (num-1) - 1 个猴子谁是大王……

问题规模的边界是 num = 1 ，报数到 out-1 的猴子出列，因为只有一个猴子，那大王只能是这个编号为0的猴子：

%20%3D%200%0A#card=math&code=F%281%29%20%3D%200%0A)

当 num = 2 时，报数到 out-1 出列，那最后出列的猴子是谁？只能是只有一个猴子报数得到的序号加上 out：

%20%3D%20%5BF(1)%20%2B%20out%5D%20%5Cmod%20num%0A#card=math&code=F%282%29%20%3D%20%5BF%281%29%20%2B%20out%5D%20%5Cmod%20num%0A)

当 num = 3 时，报数到 out-1 出列，那最后出列的猴子是：

%20%3D%20%5BF(2)%20%2B%20out%5D%20%5Cmod%20num%0A#card=math&code=F%283%29%20%3D%20%5BF%282%29%20%2B%20out%5D%20%5Cmod%20num%0A)

所以整个递推公式为：

%20%3D%20%0A%5Cbegin%7Bcases%7D%0A0%26%2C%20num%20%3D%201%5C%5C%0A%5BF(num-1)%20%2B%20out%20%5D%5Cmod%20num%26%20%2Cnum%20%3E%201%0A%5Cend%7Bcases%7D%0A#card=math&code=F%28num%29%20%3D%20%0A%5Cbegin%7Bcases%7D%0A0%26%2C%20num%20%3D%201%5C%5C%0A%5BF%28num-1%29%20%2B%20out%20%5D%5Cmod%20num%26%20%2Cnum%20%3E%201%0A%5Cend%7Bcases%7D%0A)

有了递推公式就可以编程了。

代码

方法一的代码：

#include <iostream>
#include <cstring>
using namespace std;
#define OUT 3    // 报数到3出列
int main() {
    int num(0);
    cin >> num;
    int* monkey = new int[num];
    memset(monkey, 0x0, sizeof(int) * num);  // 0x0 means stay, 0x1 means out
    int out_count(1), pos(-1);
    int say_count(0);
    while(out_count <= num) {  // 在num个猴子中模拟循环报数
        do {
            pos = (pos + 1) % num;
            if(monkey[pos] == 0)      // 报数
                say_count++;
            if(say_count == OUT) {  // 出列
                say_count = 0;
                monkey[pos] = 0x1;
                break;
            }
        } while(1);
        out_count++;
    }
    cout << pos+1;
    return 0;
}

方法二的代码：

#include <iostream>
using namespace std;
int josephus(int num, int out) {
    if(num == 1)   return 0;
    return (josephus(num-1, out) + out) % num;
}
int main() {
    int num(0);
    cin >> num;
    printf("%d\n", josephus(num, 3) + 1);
    return 0;
}

如果怕递归太深，可以改写成递推形式：

#include <iostream>
using namespace std;
int main() {
    int num(0);
    cin >> num;
    int out(3), last_standing(0);
    for(int i = (out-1); i <= num; i++) 
        last_standing = (last_standing + out) % i;
    printf("%d\n", last_standing + 1);
    return 0;
}