基础算法题——猴子选大王（约瑟夫环）

心已赠人 2022-12-20 11:08 179阅读 0赞

### [猴子选大王][Link 1] ###

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

> 如果要追求效率，就要打破常规，实施一点数学策略。

#### 算法分析 ####

##### [约瑟夫问题\_百度百科][Link 2] #####

为了讨论方便，先把问题稍微改变一下，并不影响原意：  
问题描述： n 个猴子(编号0~(n-1))，从 0 开始报数，报到 (m-1) 的退出，剩下的人继续从 0 开始报数。求胜利者的编号。

我们知道第一个人( 编号(m-1) mod n ) 出列之后，剩下的 n-1 只猴子组成了一个新的约瑟夫环（按原来的编号）：  
k k+1 k+2 … n-2,n-1,0,1,2,… k-2

原本的编号转换为新的约瑟夫环的编号：

k --> 0
    k+1 --> 1
    k+2 --> 2
    ...
    ...
    k-2 --> n-2

变换后原来求 n 只猴子的约瑟夫环转换为 n-1 只猴子的约瑟夫环！

--------------------

假设 x 是 n-1 个只猴子的大王，根据上面这个表把这个 x 通过转换公式：x’ = ( x + (m-1) ) mod n，x’ 是 n 只猴子的大王。

按上述的思路，想要得到 n 只猴子的大王，就要从 1 只猴子的大王开始递推到 n 只猴子。

递推公式
    f [1] = 0;	//初始化
    f [ i ] = (f [i-1] + m) mod i;		//i>1

实现代码

#include <iostream>
    using namespace std;
    const int m = 3;
    int main()
    { 
        int n, f = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) 
            f = (f + m) % i;
        cout << f + 1 << endl;
        return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/14/problems/808
[Link 2]: https://baike.baidu.com/item/%E7%BA%A6%E7%91%9F%E5%A4%AB%E9%97%AE%E9%A2%98/3857719?fromtitle=%E7%BA%A6%E7%91%9F%E5%A4%AB%E7%8E%AF&fromid=348830&fr=aladdin#1