Golang实现算法-约瑟夫环
原创
什么是约瑟夫环
约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。
- 首先A开始报数，他报1。侥幸逃过一劫。
- 然后轮到B报数，他报2。非常惨，他被杀了
- C接着从1开始报数
- 接着轮到A报数，他报2。也被杀死了。
- 最终胜利者是C
image
普通算法
使用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总结： 利用数学公式写的算法就是牛
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录