Go语言中实现汉诺塔算法demo

Go  /  管理员 发布于 3年前   862

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

算法分析（递归算法）

我们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法还是同过递归来求，至于是什么是递归，递归实现的机制是什么，我们说的简单点就是自己是一个方法或者说是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？，这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。

实现这个算法可以简单分为三个步骤：

（1） 把n-1个盘子由A 移到 B；

（2） 把第n个盘子由 A移到 C；

（3） 把n-1个盘子由B 移到 C；

demo:

package main

import (
    "fmt"
)

func print(n int,x rune,y rune)(){
    fmt.Printf("moving disk %d from pole %c to pole %c\n",n,x,y)
}

func move(n int,a rune,b rune,c rune)(){
    if n==1{
        print(n,a,c)
    }else {
        move(n-1,a,c,b);
        print(n,a,c);
        move(n-1,b,a,c)
    }
}

func main() {
    var n int;
    fmt.Println("Please input the disk number n: ");
    fmt.Scanf("%d",&n);
    move(n,'x','y','z')
}

完