有n只猴子，按顺时针方向围城一圈选大王(编号1~n)。从第一号开始报数，一直数到m，数到m的猴子推出圈外，剩下的猴子再接着从1开始报数。就这样，知道圈内只剩下一只猴子时，这个猴子就是猴王。 【输入】 每行是用空格隔开的两个整数 n,m。 0< m,n <300 最后一行是：0 0 【输出】 对于每行输入数据(最后一行除外)，输出的数据也是一行，即最后猴王的编号。 【样例】 【输入】 6 2 12 4 8 3 0 0 【输出】 5 1 7

### 实现约瑟夫环问题的算法 约瑟夫环问题是经典的计算机科学问题，可以通过多种方式实现。以下是基于递推公式的解决方案，该方案利用了数学归纳法的思想。 #### 数学公式解析 对于 \( n \) 只猴子和每轮数到 \( m \) 的情况，假设已知当有 \( n-1 \) 只猴子时的结果为 \( f(n-1) \)，则当前 \( n \) 只猴子的情况可表示为： \[ f(n) = (f(n-1) + m) \% n \] 其中初始条件为：\( f(1) = 0 \)[^2]。 此公式的核心在于通过递归的方式逐步缩小问题规模，直至只剩下一个元素为止。 #### Python代码实现 以下是一个Python程序，用于解决多个输入组合下的约瑟夫环问题： ```python def find_monkey_king(n, m): res = 0 for i in range(2, n + 1): # 从2开始迭代至n res = (res + m) % i # 使用递推公式计算当前位置 return res + 1 # 返回实际编号（数组索引从0转为1） if __name__ == "__main__": test_cases = [(7, 3), (5, 2)] # 示例测试数据 results = [] for n, m in test_cases: king_index = find_monkey_king(n, m) results.append(king_index) print(results) # 输出所有结果 ``` 上述代码定义了一个函数 `find_monkey_king` 来接收参数 \( n \) 和 \( m \)，并通过循环应用递推关系得出最终猴王的位置[^2]。注意返回值加1是因为通常人们习惯于从1开始计数而不是从0开始。 #### C++代码实现 同样地，在C++中也可以轻松实现同样的逻辑： ```cpp #include <iostream> using namespace std; int findMonkeyKing(int n, int m){ int res = 0; for(int i = 2; i <= n; ++i){ res = (res + m) % i; } return res + 1; // 转换回人类友好的编号体系 } int main(){ pair<int,int> tests[] = {{7,3}, {5,2}}; // 测试用例 for(auto &[n,m] : tests){ cout << findMonkeyKing(n, m) << endl; } return 0; } ``` 这段C++代码实现了相同的功能，并展示了如何处理多组输入的数据结构[^4]。 ### 结论 无论是使用Python还是C++，都可以高效地解决问题。关键是理解背后的数学原理——即通过不断更新位置变量来模拟整个过程而不必真正构建链表或者数组进行删除操作，从而极大地提高了效率[^3]。