每日一个算法题

小甲鱼的铁粉

猴子选大王（增强版)

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

1. 11 3
   

复制代码

输出样例

1. 7

复制代码

参考答案

1. #include <stdio.h>
   
2. #include<stdlib.h>
   
3. int main()
   
4. {
   
5.     int n,m,result=0;
   
6.     scanf("%d%d", &n, &m);
   
7.     for (int i = 2; i <= n; i++)
   
8.     {
   
9.         result = (result + m) % i;
   
10.     }
    
11.     printf ("%d", result+1);
    
12.     return 0;
    
13. }

复制代码

算法解析

小甲鱼的铁粉

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

fatsky

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

杨金辉