每日一个算法题

小甲鱼的铁粉

猴子选大王（增强版)

题目来自pta。一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到M，凡报到M的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？
输入格式
输入在一行中给两个正整数N, M（1<= N,M ≤10000000）。（注意M的值的大小，M是比较大的，如果算法效率不高的话，很浪费时间）
输出格式
在一行中输出当选猴王的编号。
输入样例

11 3

输出样例

7

参考答案

#include <stdio.h>
#include<stdlib.h>
int main()
{
    int n,m,result=0;
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; i++)
    {
        result = (result + m) % i;
    }
    printf ("%d", result+1);
    return 0;
}

算法解析

小甲鱼的铁粉

说实话这个算法解析我自己看的也不是很懂，所以发到技术交流区了

fatsky

可能倒着推好理解一点。从0开始计算位置。在最后一轮，剩下的猴子的位置就是pos = 0，在倒数第二轮，因为这个猴子要剩下来，在这一轮它的pos = (0 + m) % 2，倒数第三轮这个猴子的位置必须是pos =  ((0 + m) % 2 + m) % 3，以此类推，就能得到最初的位置。

杨金辉