Golang递归实现汉诺塔问题时遇到slice越界错误该如何解决

Golang递归实现汉诺塔问题时遇到slice越界错误该如何解决

package main

import (
	"fmt"
)

func move(n int, source, target, auxiliary []int) {
	if n > 0 {
		move(n-1, source, auxiliary, target)
		curr := source[len(source)-1]
		target = append(target, curr)
		source = source[:len(source)-1]

		fmt.Printf("%v\n%v\n%v\n", source, auxiliary, target)

		move(n-1, auxiliary, target, source)
	}
}

func main() {
	var (
		a = []int{3, 2, 1}
		b = []int{}
		c = []int{}
	)
	move(3, a, c, b)
}

更多关于Golang递归实现汉诺塔问题时遇到slice越界错误该如何解决的实战教程也可以访问 https://www.itying.com/category-94-b0.html

6 回复

你尝试过使用像 delve 这样的调试器吗？

更多关于Golang递归实现汉诺塔问题时遇到slice越界错误该如何解决的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


我使用了VS Code自带的调试器。我遇到的问题是在递归调用过程中，名为source的切片长度不知为何变成了小于0的值。

这个使用切片的例子有帮助吗？

https://play.golang.org/p/rbnOVS9W700

编辑： 我认为这个例子更好。

你使用调试器时找到原因了吗？

如果没有，也许可以尝试在纸上逐步推演你的算法：写下每一步后每个变量的状态，并仔细思考为什么变量会以这种方式被改变。

请记住：算法的正确性与实现它的编程语言无关。

不，我找不到原因。

我已经用Python和Kotlin实现了相同的算法。在这些语言中，它运行得很好。

我是Go编程的新手。我推测，在我从源切片中移除最后一个元素后，其长度的变化并没有在递归调用之间传递。这个问题是否可能是因为切片是引用类型而导致的？

这是一个典型的Go语言slice引用问题。你的代码中slice作为参数传递时，对slice的修改不会反映到原始slice上，导致递归过程中slice状态不一致。

问题在于：

  1. append返回的是新slice，需要赋值回原变量
  2. slice作为参数传递时，函数内部修改不会影响调用方的slice

以下是修正后的代码：

package main

import (
	"fmt"
)

func move(n int, source, target, auxiliary *[]int) {
	if n > 0 {
		move(n-1, source, auxiliary, target)
		
		// 从源柱子取出最上面的盘子
		curr := (*source)[len(*source)-1]
		*source = (*source)[:len(*source)-1]
		
		// 将盘子放到目标柱子
		*target = append(*target, curr)
		
		fmt.Printf("A: %v\nB: %v\nC: %v\n\n", *source, *auxiliary, *target)
		
		move(n-1, auxiliary, target, source)
	}
}

func main() {
	var (
		a = []int{3, 2, 1}
		b = []int{}
		c = []int{}
	)
	move(3, &a, &c, &b)
}

或者使用返回值的方式：

package main

import (
	"fmt"
)

func move(n int, source, target, auxiliary []int) ([]int, []int, []int) {
	if n > 0 {
		source, auxiliary, target = move(n-1, source, auxiliary, target)
		
		// 移动盘子
		curr := source[len(source)-1]
		source = source[:len(source)-1]
		target = append(target, curr)
		
		fmt.Printf("A: %v\nB: %v\nC: %v\n\n", source, auxiliary, target)
		
		auxiliary, target, source = move(n-1, auxiliary, target, source)
	}
	return source, target, auxiliary
}

func main() {
	var (
		a = []int{3, 2, 1}
		b = []int{}
		c = []int{}
	)
	move(3, a, c, b)
}

关键修改：

  1. 使用指针传递slice，确保递归调用中能修改原始slice
  2. 或者通过返回值传递修改后的slice状态
  3. 确保每次移动后slice的长度变化能正确传递到递归的下一层
回到顶部