递归的应用-汉诺塔游戏

递归的应用-汉诺塔游戏

汉诺塔游戏:有A、B、C三个柱子,A柱子上有n个盘片,要求把A柱子上的盘片通过B柱子移动到C柱子,规则是“小盘片只能在大盘片的上边”。

思路:把A柱上所有的盘子分成两部分,把上面的n-1个盘子看成一个整体,这样就简化成了两个盘子(上面的n-1个,和最下面的1个)
1. 先把A柱的n-1个盘(看成一个整体),通过C盘移动到B盘
2. 然后把A柱最后一个盘移动到C盘
2. 最后把B柱的n-1个盘通过A盘移动到C盘

Python版本:

def move(n, a, b, c):
    """
    递归的应用
    汉诺塔游戏:有A、B、C三个柱子,A柱子上有n个盘片,要求把A柱子上的盘片通过B柱子移动到C柱子,规则是“小盘片只能在大盘片的上边”。
    :param n: a柱中的盘片数量
    :param a: a柱的名称
    :param b: b柱的名称
    :param c: c柱的名称
    :return:
    """
    if n == 1:
        # 如果只有一个,则直接把它从a柱移动到$c柱,打印出a柱移动到c的盘片
        print(a, '-->', c)
    else:
        # 否则,先把a柱上面的n-1个通过c柱移动到b
        move(n-1, a, c, b)
        # 打印出a移动到c的盘片
        print(a, '-->', c)
        # 最后把b中的n-1个盘片移动到c
        move(n-1, b, a, c)


# 调用,共3个盘片,第一个盘片叫A,第二个盘片叫B,第三个盘片叫C
move(3, 'A', 'B', 'C')

php版本:

<?php
    /**
     * 递归的应用
     * 汉诺塔游戏:有A、B、C三个柱子,A柱子上有n个盘片,要求把A柱子上的盘片通过B柱子移动到C柱子,规则是“小盘片只能在大盘片的上边”。
     * @param $n $a柱中的盘片数量
     * @param $a $a柱的名称
     * @param $b $b柱的名称
     * @param $c $c柱的名称
     */
    function hanoi ($n, $a, $b, $c)
    {
        if ($n == 1) {
            //如果只有一个,则直接把它从$a柱移动到$c柱,打印出$a柱移动到$c的盘片
            echo $a, '-->', $c , "\n";
        } else {
            //否则,先把$a柱上面的n-1个通过$c柱移动到$b
            hanoi($n - 1, $a, $c, $b);
            //打印出$a移动到$c的盘片
            echo $a, '-->', $c , "\n";
            //最后把$b中的n-1个盘片移动到$c
            hanoi($n - 1, $b, $a, $c);
        }
    }

    //调用,共3个盘片,第一个盘片叫A,第二个盘片叫B,第三个盘片叫C
    hanoi(3, 'A', 'B', 'C');

js版本:

/**
 * 递归的应用
 * 汉诺塔游戏:有A、B、C三个柱子,A柱子上有n个盘片,要求把A柱子上的盘片通过B柱子移动到C柱子,规则是“小盘片只能在大盘片的上边”。
 * @param n a柱中的盘片数量
 * @param a a柱的名称
 * @param b b柱的名称
 * @param c c柱的名称
 */
function hanoi (n, a, b, c){
    if(n==1){
        //如果只有一个,则直接把它从a柱移动到$c柱,打印出a柱移动到c的盘片
        console.log(a, '-->', c);
    }else{
        //否则,先把a柱上面的n-1个通过c柱移动到b
        hanoi(n-1, a, c, b);
        //打印出a移动到c的盘片
        console.log(a, '-->', c);
        //最后把b中的n-1个盘片移动到c
        hanoi(n-1, b, a, c);
    }
}

//调用,共3个盘片,第一个盘片叫A,第二个盘片叫B,第三个盘片叫C
hanoi(3, 'A', 'B', 'C');
打赏

Leave a Reply

avatar

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
Notify of

扫码在手机查看
iPhone请用自带相机扫
安卓用UC/QQ浏览器扫

递归的应用-汉诺塔游戏