majianyu
5/9/2018 - 7:44 AM

hanio

汉诺塔.汉诺塔的计算方式步骤,求 N 个圆盘:

  1. 将 N-1个圆盘从 A 柱,通过 B 柱移动到C 柱
  2. 将1个圆盘从 A 柱移动到 B 柱
  3. 将 N-1个圆盘从 C 柱,通过 A 柱,移动到 B 柱
  4. 对每一个 N-1 的步骤重复求以上3个步骤,直至 N == 0

汉诺塔的计算步数为 2**N-1

hanno.py
content_copyfile_download
count = 0

def hanoi(n: int, x: str, y: str, z: str):
    '''
    :param n: 圆盘数
    :param x: 起点
    :param y: 目标点
    :param z: 中转点
    count 值为 2 ** N -1
    '''
    if n == 0:
        return
    global count
    count += 1
    hanoi(n - 1, x, z, y)
    print("{} --> {}".format(x, y))
    hanoi(n - 1, z, y, x)


if __name__ == '__main__':
    hanoi(5, "a", "b", "c")
    print(count)
hanoi.go
content_copyfile_download
package main

import "fmt"
var count int
func main() {
    hanoi(3,"a","b","c")
    fmt.Println(count)
}

/*
    n: 圆盘数
    x: 起点
    y: 目的地
    z: 中转点
    count = 2 ** N -1
 */
func hanoi(n int, a, b, c string) {
	if n == 0 {
		return
	}
	count++
	hanoi(n-1, a, c, b)
	fmt.Printf("%s --> %s\n", a, b)
	hanoi(n-1, c, b, a)
}
Hanoi.java
content_copyfile_download
package com.test;

public class Hanoi {
    private static int count;

    public static void main(String[] args) {
        hanoi(4, 'a', 'b', 'c');
        System.out.println(count);
    }

    /**
     * @param n 圆盘数
     * @param x 起点
     * @param y 目的地
     * @param z 中转点
     * count = 2 ** N -1
     */
    private static void hanoi(int n, char x, char y, char z) {
        if (n == 0) {
            // nothing to do
            return;
        }
        count++;
        // 通过 y 中转,将 x 移动到 z
        hanoi(n - 1, x, z, y);
        // 将1个圆盘由 x 移动到 y
        System.out.printf("%c --> %c \n", x, y);
        // 通过 x 中转,将 z 移动到 y
        hanoi(n - 1, z, y, x);
    }
}