递归之汉诺塔问题

悠悠 2023-06-04 02:59 23阅读 0赞

**汉诺塔问题：**

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

![1504737-20190907152946394-1859396079.png][]

有一个和尚想把这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;
            }
        }
    }

转载于:https://www.cnblogs.com/tcxpz/p/11481311.html

[1504737-20190907152946394-1859396079.png]: /images/20230601/8cb0c63c4a8147b2828befe304b4648f.png