总时间限制: 1000ms 内存限制: 65536kB

描述

约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。

输入

每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是：

0 0

输出

对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号

样例输入

6 2
12 4
8 3
0 0

样例输出

5
1
7

思路

一开始我是用一位数组直接模拟整个过程，样例输入输出是对的，但是超时了。

查阅资料后，得知本题可以由递推公式来得到猴王的编号，思路如下：

设由 monkeyNumber 个猴子，我们从0开始报数，报数3下就离开，即报到 3-1 = 2 的猴子离开。

• 假设只有1只猴子，他就是猴王，他的编号是0
• 假设有2只猴子，猴王编号是 (0 + 3) % 2 = 1
• 假设有3只猴子，猴王编号是 (1 + 3) % 3 = 1
• 假设有4只猴子，猴王编号是 (1 + 3) % 4 = 0
• 假设有5只猴子，猴王编号是 (0 + 3) % 5 = 3
• 假设有6只猴子，猴王编号是 (3 + 3) % 6 = 3
• ……
• 假设有monkeyNumber只猴子，猴王编号是(上一轮的猴王编号 + exitNum) % monkeyNumber.

所以递推公式如下：

%20%26%3D%20(f(monkeyNum%20-%201)%20%2B%20exitNum)%20%5C%25%5C%20monkeyNum%20%5C%5C%0Af(1%2C%20exitNum)%26%3D0%20%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7D%0Af%28monkeyNum%2C%20exitNum%29%20%26%3D%20%28f%28monkeyNum%20-%201%29%20%2B%20exitNum%29%20%5C%25%5C%20monkeyNum%20%5C%5C%0Af%281%2C%20exitNum%29%26%3D0%20%0A%5Cend%7Balign%7D%0A)

代码

样例测试是对的，但超时的代码(数组直接硬刚果然效率不高)

#include<iostream> 
#include<cstring>
using namespace std;
int array[301] = {0};
int monkeyNumber, exitNum;
int main() {
    while(true) {
        scanf("%d%d", &monkeyNumber, &exitNum);
        if(monkeyNumber == 0)  return 0;
        int callNumber = 1, monkeyLeft = monkeyNumber;
        while(monkeyLeft != 1) {
            for(int i = 0; i < monkeyNumber; i++ ) {
                if(array[i] == 666) continue;
                if(callNumber == exitNum) {
                    array[i] = 666;     // This monkey exit
                    callNumber = 1;     // Reset the callNumber
                    monkeyLeft--;
                    continue;
                }
                callNumber++;
            }
        }
        for(int i = 0; i < monkeyNumber; i++) {
            if(array[i] != 666) {
                printf("%d\n", i + 1);
                memset(array, 0, sizeof(array));    // Reset the value of array
                break;
            }
        }
    }
    return 0;
}

由数学递推公式得到的AC代码

#include<iostream> 
using namespace std;
int jonseOptimal(int monkeyNumber, int exitNum) {
    int final = 0;
    for(int total = 2; total <= monkeyNumber; total++) {
        final = (final + exitNum) % total; // total个猴子中winner为final.
    }
    return final + 1;
}
int main() {
    int monkeyNumber, exitNum;
    while(true) {
        scanf("%d%d", &monkeyNumber, &exitNum);
        if(monkeyNumber == 0)  return 0;
        printf("%d\n", jonseOptimal(monkeyNumber, exitNum));
    }
    return 0;
}