Golang 实现汉诺塔

在本文中，我们将学习如何使用递归方法和迭代方法来实现汉诺塔问题。汉诺塔是一个谜题，我们通过每次移动一个圆盘将一组圆盘从一个柱子移动到另一个柱子。在这个谜题中需要遵守一定的规则。

使用递归方法

在这种方法中，我们将编写一个使用递归方法来实现汉诺塔的Go语言程序。

如果n为1，我们可以直接将圆盘从from柱子移动到to柱子。否则，我们先将n-1个圆盘从from柱子移动到via柱子，然后将第n个圆盘从from柱子移动到to柱子，最后将n-1个圆盘从via柱子移动到to柱子。

步骤

• 步骤1 - 首先，我们需要导入fmt包。

• 步骤2 - 然后，创建一个名为hanoi()的函数。这个函数接受三个参数，第一个是字符串变量的数量，其他的是字符串变量。

• 步骤3 - 然后开始main()函数。在main()中调用hanoi()函数，并传入必要的参数。

• 步骤4 - 如果n等于1，将圆盘从from柱子移动到to柱子，并停止程序。否则，以n-1、from柱子、via柱子和to柱子为参数递归调用hanoi()函数，并使用fmt.Println()函数在屏幕上打印结果。

示例

在下面的示例中，我们将了解如何使用递归方法开发一个使用Go语言的程序来实现汉诺塔问题。

package main

import "fmt"

func hanoi(n int, from string, to string, via string) {
   if n == 1 {
      fmt.Printf("Move disk 1 from %s to %s\n", from, to)
   } else {
      hanoi(n-1, from, via, to)
      fmt.Printf("Move disk %d from %s to %s\n", n, from, to)
      hanoi(n-1, via, to, from)
   }
}

func main() {
   hanoi(3, "A", "C", "B")
}

输出

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

使用迭代的概念

在这种方法中，我们将编写一个Go语言程序，通过使用迭代的概念来实现汉诺塔。

语法

func len(v Type) int

len()函数用于获取任何参数的长度。它接受一个参数作为数据类型的变量，我们希望找到其长度，并返回该变量的整数值，即长度。

func append(slice, element_1, element_2…, element_N) []T

append函数用于向数组切片中添加值。它接受多个参数。第一个参数是我们要添加值的数组，其后是要添加的值。然后函数返回包含所有值的最终切片数组。

步骤

• 第1步 − 首先，我们需要导入fmt包。

• 第2步 − 接下来创建一个名为hanoi()的函数。此函数接受四个参数。第一个参数是表示字符串数量的整数值，其他参数是字符串变量。

• 第3步 − 在这个函数内部创建一个空数组，称为stack，并将作为参数获得的变量存储在其中。

• 第4步 − 然后使用for循环遍历stack数组，并使用for循环通过使用fmt.Println()函数在屏幕上打印各个针位置。

示例

在以下示例中，我们将了解如何编写一个Go语言程序，通过使用迭代的概念来实现汉诺塔

package main

import "fmt"

func hanoi(n int, from string, to string, via string) {
   stack := make([][3]string, 0)
   stack = append(stack, [3]string{from, to, via})

   for len(stack) > 0 {
      task := stack[len(stack)-1]
      stack = stack[:len(stack)-1]

      if n == 1 {
         fmt.Printf("Move disk 1 from %s to %s\n", task[0], task[1])
      } else {
         stack = append(stack, [3]string{task[2], task[1], task[0]})
         stack = append(stack, [3]string{task[0], task[1], task[2]})
         stack = append(stack, [3]string{task[1], task[2], task[0]})
         n--
      }
   }
}

func main() {
   hanoi(3, "A", "C", "B")
}

输出

Move disk 1 from B to A
Move disk 1 from C to B
Move disk 1 from A to B
Move disk 1 from A to C
Move disk 1 from B to C

结论

我们成功地编译和执行了一个Go语言程序，实现了汉诺塔问题，并且给出了示例。我们将使用两种不同的方法来实现。第一种方法是使用递归方法，而第二种方法是使用迭代方法。