Golang实现算法-约瑟夫环

什么是约瑟夫环

约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。

例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。

• 首先A开始报数，他报1。侥幸逃过一劫。
• 然后轮到B报数，他报2。非常惨，他被杀了
• C接着从1开始报数
• 接着轮到A报数，他报2。也被杀死了。
• 最终胜利者是C

普通算法

使用Golang中的切片，来模拟约瑟夫环。通过cur游标来确定本轮次被踢出的元素，类似于丢手绢，丢到谁后，谁出局。当curl超过切片长度时，从头开始计算cur的值。
此方法，相对于链表省去了由M带来的时间复杂度。

时间复杂度：O(N)
空间复杂度：O(N)

// 普通
func f1(n, m int) int {
	// 将数字通过切片顺序排列
	var arr []int
	for i := 0; i < n; i++ {
		arr = append(arr, i)
	}

	cur := 0

	for len(arr) > 1 {
		if cur+m > len(arr) {
			cur = cur + m - len(arr) - 1
		} else {
			cur += m - 1
		}

		arr = append(arr[:cur], arr[cur+1:]...)

		if cur >= len(arr) {
			cur -= len(arr)
		}

	}

	return arr[0]
}

公式递归

约瑟夫环公式： N>1时， f(N,M)=f((N-1,M)+M)%N ；N=1时，结果为 0

时间复杂度：O(N)
空间复杂度：O(N)

// 递归
func f2(n, m int) int {
	if n == 1 {
		return 0
	}
	return (f2(n-1, m) + m) % n
}

公式循环

时间复杂度：O(N)
空间复杂度：O(1)

// 循环
func f3(n, m int) int {
	pos := 0
	for i := 2; i < n+1; i++ {
		pos = (pos + m) % i
	}
	return pos
}

验证结果

func funcTest() {
	m := 2
	for n := 4; n < 12; n++ {
		res1 := f1(n, m)
		fmt.Println(res1)

		res2 := f2(n, m)
		fmt.Println(res2)

		res3 := f3(n, m)
		fmt.Println(res3)
	}
}

结果：

0
0
0
2
2
2
4
4
4
6
6
6
0
0
0
2
2
2
4
4
4
6
6
6

总结： 利用数学公式写的算法就是牛