refer:
点击打开
题目：N个人(编号0,...,N-1)围坐一圈，给定幸运数字M，从0开始依次报数，报到M-1的人出局，下一个人继续从0开始报数，循环，求最后一名成员。
（注：为了与习惯的编程表达一致，这里统一从0开始编码）
思路：
直接循环判断，时间代价太大。
数学推导：
①第一次，N个人参与，则第M%N-1个人出局，剩下N-1个人；（这里，我们标识结果为f(n)）
②从上次出局的下一个人开始，即原始编码为M%N的人，他报号为0，则下一个淘汰的人应该是原始编码为：(M%N)+(M%(N-1)-1)的人；
得出，f(n) = (f(n-1) + M)%N
代码：
#include<iostream>
using namespace std;
int main()
{
int N;
int M;
cin>>N;
cin>>M;
int result=0; //f(1);
for (int i=2; i<=N; i++)
{
result=(result+M)%i;
}
cout<<"lucky one is "<<result+1<<endl;
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-11132.html
