递归之汉诺塔问题

汉诺塔问题：

古代有一个梵塔，塔内有三个座A,B,C。A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。

有一个和尚想把这64个盘子从A座移动到C座，但是每次只允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。

在上述移动过程中可以利用B座，要求输出一定的步骤：

求解思路：

可以将问题求解简单分为三个步骤：

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

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

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

这样就将原问题分解成了形式形同、规模变小的子问题　

　　1个圆盘的次数 2的1次方减1

　　2个圆盘的次数 2的2次方减1

       3个圆盘的次数 2的3次方减1

       。  。   。    。   。 

       n个圆盘的次数 2的n次方减1

 　　故：移动次数为：2^n - 1

递归代码实现：

package com.tcxpz.demo;

import java.util.Scanner;
public class Hanoi {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        hanoi(n,"A","B","C");
    }
    private static void hanoi(int n,String source,String spare,String target){
        if(n==1){
            System.out.println("From "+source+" To "+target);
            return;
        }else{
            //将n-1各盘子从source搬到spare,以target为周转盘
            hanoi(n-1,source,target,spare);
            //将最后一个盘子从source搬到target
            System.out.println("From "+source+" To "+target);
            //再将spare上的n-个盘子搬到target,以source为周转盘
            hanoi(n-1,spare,source,target);
            return;
        }
    }
}