题解 | #孩子们的游戏(圆圈中最后剩下的数)#
孩子们的游戏(圆圈中最后剩下的数)
http://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6
/**
- 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
- @param n int整型
- @param m int整型
- @return int整型
- C语言声明定义全局变量请加上static，防止重复定义 */
int LastRemaining_Solution(int n, int m ) {
// write code here
int i = 1;
int y = 0;
for (i = 2; i <= n; i++)
{
y = (y + m) % i;
}
return y;
}
解题思路：
举例n = 8, m = 3;计算过程如下：
-
设F(8,3) = y, F(7,3) = x。需找出x与y的对应关系。（注：x，y代表最终留下的元素在本轮的坐标索引号,本例子中为元素G的坐标）
-
已知，x表示从D字母开始数(x+1)个数后即可得到，最终留下的元素在本轮的坐标索引号。
-
而从N=8到N=7删除的元素C刚好在D的前一个。我们可知，C在N=8时的坐标为(m-1)，因此，(m-1+x+1) 即为G在N = 8时的坐标y。
-
由于会溢出，所以应对N的值取余。即y = (m-1+x+1)%n;
-
即F(n,m) = (F(n-1,m) + m) % n;
由上可得：
