侧边栏壁纸
  • 累计撰写 71 篇文章
  • 累计创建 87 个标签
  • 累计收到 5 条评论

目 录CONTENT

文章目录

Golang实现算法-约瑟夫环

KunkkaWu
2023-02-02 / 0 评论 / 2 点赞 / 4,210 阅读 / 575 字 / 正在检测是否收录...

什么是约瑟夫环

约瑟夫问题是个著名的问题: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

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

2

评论区