2020-04-18 72e775598a854efe5fbac2424d2ca151 99+ 几秒 0.1 k 0次访问

剑指offer-圆圈中最后剩下的数

一、题意

0，1，…，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求这个圆圈里剩下的最后一个数字。
如0、1、2、3、4这5个数字组成的圆圈，从数字0开始每次删除第3个数字，则删除的前四个数字分别是2、0、4、1，因此最后剩下的数字是3。

二、分析

输入的序列在删除一个元素后，序列的长度会改变，如果索引在被删除的元素位置开始计算，那么每删除一个元素，序列的长度减一而索引会完全改变。如果能找到改变前的索引和新索引的对应关系，那么该问题就容易解决了。
定义一个函数f(n，m)，表示每次在n个数字0，1，2，3，…，n-1中每次删除第m个数字后剩下的数字。那么第一个被删除的数字的索引是(m-1)%n。删除该索引元素后，剩下的n-1个数字为0，1，2，…，k-1，k+1，…，n-1。下次删除数字是从k+1位置开始，于是可以把序列看作k+1，…，n-1，0，1，…，k-1。该序列最后剩下的序列也是f的函数。但该函数和第一个函数不同，存在映射关系，使用f’来表示，于是有：
f(n，m) = f’(n-1，m)。

k+1 --> 0
.
.
k+2 --> 1
n-1 --> n-k-2
.
.
0   --> n-k-1
k-1 --> n-2

将映射定义为函数p，则p(x) = (x-k-1)%n，它表示如果映射前的数字是x，那么映射后的数字是(x-k-1)%n。对应的逆映射是p’(x) = (x+k+1)%n。由于映射之后的序列和最初的序列具有同样的形式，即都是从0开始的连续序列，仍然可以用函数f表示，记为f(n-1，m)。映射之前的序列中最后剩下的数字f’(n-1，m) = p’[f(n-1，m)] = [f(n-1, m)+k+1]%n代入得到f(n，m) = f’(n-1，m) = [f(n-1，m)+m]%n。
经过分析，终于得到一个递归公式。要得到n个数字的序列中最后剩下的数字，只需要得到n-1个数字的序列中最后剩下的数字，以此类推…。当n = 1时，也就是序列中开始只有一个数字0，那么最后剩下的数字就是0

$$ f(x) = \left\{ \begin{array}{lr} 0 & : n=0\\ [f(n-1,m)+m] \%n & : n > 1 \end{array} \right. $$

三、代码实现

package main

import "fmt"

// n个数字从0、1、2、...、n-1开始编号，每次从其中删除第m个数字
func CycleNumber(n, m int) int {
	if n < 1 || m < 1 {
		return -1
	} else if n == 1 {
		return 0
	} else {
		return (CycleNumber(n-1, m) + m) % n
	}
}

func main() {
	last := CycleNumber(5, 3)
	fmt.Printf("5个数字编号0、1、2、3、4，每次删除第3个数字，剩下的数字：%d", last)
}

// 输出如下:
5个数字编号0、1、2、3、4，每次删除第3个数字，剩下的数字：3

Process finished with exit code 0