每日一个算法题
猴子选大王（增强版)题目来自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;
}
算法解析
说实话这个算法解析我自己看的也不是很懂{:10_266:}，所以发到技术交流区了 可能倒着推好理解一点。从0开始计算位置。在最后一轮，剩下的猴子的位置就是pos = 0，在倒数第二轮，因为这个猴子要剩下来，在这一轮它的pos = (0 + m) % 2，倒数第三轮这个猴子的位置必须是pos =((0 + m) % 2 + m) % 3，以此类推，就能得到最初的位置。 {:10_250:}
页:
[1]