转载

【java练习】汉诺塔递归实现

1. 问题描述

相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、 由大到小按顺序放置64个金盘。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在 移动过程中三根杆上都始 终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。

2. 问题分析

因为无法直接从题目中获得思路,所以采用数学归纳法进行推导

让n为当前层数上的圆盘编号,当 n=1 的时候:

   圆盘1 直接从 AC

n=2 的时候:

   圆盘1 需要从 AB
   圆盘2 需要从 AC

圆盘1 需要从 BC

 其中 B 作为中间柱被使用过一次

n=n 的时候(将 n-1 看为一个整体):

   A. A 上的 n-1 个圆盘需要从 A 移动到 B (借助于 C )

   B. 圆盘n 需要从 AC

   C. B 上的 n-1 个圆盘需要从 BC (借助于 A

  当步骤为A的时候:

    1. 将 A 上的 n-2 个圆盘移到 C 上。

    2. 将 A 上的第 n-1 个圆盘移到 B

    3. 将 C 上的 n-2 个圆盘移到 B

  当步骤为C的时候:

    1. 将 B 上的 n-2 个圆盘移到 A

    2. 将 B 上的第 n-1 个盘子移到 C

    3. 将 A 上的 n-2 个圆盘移到 C

所以从上面可以分析出来,当n>=2的时候可以分为三个步骤:

(A为初始位置,C为中间位置,B为目的位置)
(B为初始位置,A为中间位置,C为目的位置)

3. 编码

可以创建方法:

/**
     * @param layer  层数
     * @param init   初始位置
     * @param middle 中间位置
     * @param target 目标位置
     * @return void
     */
    private static void solve(int layer, String init, String middle, String target) {
        if (1 == layer) {
            System.out.printf("%d从%s移动到%s;/n", layer, init, target);
        } else {
            solve(layer - 1, init, target, middle);      //1.
            System.out.printf("%d从%s移动到%s;/n", layer, init, target);     //2.
            solve(layer - 1, middle, init, target);      //3.
        }
    }

方法说明

System.out.printf("%d从%s移动到%s;/n", layer, init, target); 
原文  https://segmentfault.com/a/1190000021209372
正文到此结束
Loading...