100题_14 圆圈中最后剩下的数字
时间：2011-03-08 来源：小橋流水
题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。
View Code
#include <iostream>
using namespace std;
int last_remain(const int &n, const int &m)
{
if (n == 1)
return 0;
else
return (last_remain(n-1, m) + m) % n;
}
int main()
{
cout<<last_remain(10, 3)<<endl;
return 0;
}
这题最简单的办法就是暴力法了。除了暴力法，就是找规律了，找规律的过程有点负责，最终的规律是：
f(n,m) = [f(n-1,m) + m] % n
有了这个规律，递归就行，代码如下：
View Code
#include <iostream>
View Code
using namespace std;
int last_remain(const int &n, const int &m)
{
if (n == 1)
return 0;
else
return (last_remain(n-1, m) + m) % n;
}
int main()
{
cout<<last_remain(10, 3)<<endl;
return 0;
}
相关阅读 更多 +
