Java解决汉诺塔问题

1 package com.java; 2  3 /** 4  * 分治算法 5  * 基本思路： 6  * 对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题， 7  * 这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 8  * 具体步骤如下： 9  * 1、分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；10  * 2、解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；11  * 3、合并：将各个子问题的解合并为原问题的解。12  */13 14 /**15  * hanoi问题的基本思路：16  * 设n为圆盘数，A、B、C为三根石柱，17  * 1、当n=1时，直接将一个圆盘从A石柱移动到C石柱18  * 2、当n>1时，将前n-1个圆盘从石柱A，借助石柱C移动到石柱B；19  * 然后将第n号圆盘从石柱A移动到石柱C；20  * 最后将前n-1个圆盘从石柱B，借助石柱A移动到石柱C21  */22 23 public class Hanoi {24     public static void main(String[] args) {25 26         solve(3);27 28     }29 30     public static void solve(int n) {31         // 已知条件n个圆盘和A、B、C三根石柱32         hanoi(n, "A", "B", "C");33     }34 35     private static void hanoi(int n, String a, String b, String c) {36         if (n == 1) {37             // 只有一个圆盘时直接从A石柱移动到C石柱38             move(n, a, c);39         } else {40             // 将前n-1个圆盘从石柱A移动到石柱B41             hanoi(n - 1, a, c, b);42             // 将第n号圆盘从石柱A移动到石柱C43             move(n, a, c);44             // 将前n-1个圆盘从石柱B移动到石柱C45             hanoi(n - 1, b, a, c);46         }47     }48 49     private static void move(int n, String i, String j) {50         System.out.println("将第" + n + "个圆盘，" + "从" + i + "移动到" + j);51     }52 53 54 }