关于递归:递归实现汉诺塔问题

42次阅读

共计 2678 个字符,预计需要花费 7 分钟才能阅读完成。

一.起源:

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。有人造了三根柱子,在一根柱子上从下往上依照大小程序摞着 64 片黄金圆盘。让上司把圆盘从上面开始按大小程序从新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能挪动一个圆盘。

二.形象为数学问题:

如下图所示,从左到右有 A、B、C 三根柱子,其中 A 柱子下面有从小叠到大的 n 个圆盘,现要求将 A 柱子上的圆盘移到 C 柱子下来,期间只有一个准则:一次只能移到一个盘子且大盘子不能在小盘子下面,求挪动的步骤和挪动的次数

解:(1)n == 1

      第 1 次  1 号盘  A—->C       sum = 1 次

       (2)  n == 2

       第 1 次  1 号盘  A—->B

       第 2 次  2 号盘  A—->C

       第 3 次  1 号盘  B—->C        sum = 3 次

(3)n == 3

第 1 次  1 号盘  A—->C

第 2 次  2 号盘  A—->B

第 3 次  1 号盘  C—->B

第 4 次  3 号盘  A—->C

第 5 次  1 号盘  B—->A

第 6 次  2 号盘  B—->C

第 7 次  1 号盘  A—->C        sum = 7 次

不难发现法则:1 个圆盘的次数 2 的 1 次方减 1

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

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

。。。。。

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

 故:挪动次数为:2^n – 1

三.调用办法的栈机制:(特点:先进后出)

       从主线程开始调用办法(函数)进行不停的压栈和出栈操作,函数的调用就是将函数压如栈中,函数的完结就是函数出栈的过程,这样就保障了办法调用的程序流,即当函数呈现多层嵌套时,须要从外到内一层层把函数压入栈中,最初栈顶的函数先执行完结(最内层的函数先执行完结)后出栈,再倒数第二层的函数执行完结出栈,到最初,第一个进栈的函数调用完结后从栈中弹出回到主线程,并且完结。

四.算法剖析(递归算法):

       咱们在利用计算机求汉诺塔问题时,必不可少的一步是对整个实现求解进行算法剖析。到目前为止,求解汉诺塔问题最简略的算法还是同过递归来求,至于是什么是递归,递归实现的机制是什么,咱们说的简略点就是本人是一个办法或者说是函数,然而在本人这个函数里有调用本人这个函数的语句,而这个调用怎么能力调用完结呢?,这里还必须有一个完结点,或者具体的说是在调用到某一次后函数能返回一个确定的值,接着倒数第二个就能返回一个确定的值,始终到第一次调用的这个函数能返回一个确定的值。

       实现这个算法能够简略分为三个步骤:

(1)把 n - 1 个盘子由 A 移到 B;

(2)把第 n 个盘子由 A 移到 C;

(3)把 n - 1 个盘子由 B 移到 C;

从这里动手,在加上下面数学问题解法的剖析,咱们不难发现,移到的步数必然为奇数步:

(1)两头的一步是把最大的一个盘子由 A 移到 C 下来;

(2)两头一步之上能够看成把 A 上 n - 1 个盘子通过借助辅助塔(C 塔)移到了 B 上,

(3)两头一步之下能够看成把 B 上 n - 1 个盘子通过借助辅助塔(A 塔)移到了 C 上;

五,java 源代码:

package com.self;
import java.util.Scanner;
public class TowersOfHanoi {
    /**
 * 标记挪动次数 */ static int m = 0;
    /**
 * 实现挪动的函数 * * @param disks 盘子编号
 * @param from 挪移地位
 * @param to 指标地位
 */ public static void move(int disks, char from, char to) {System.out.println("第" + (++m) + "次挪动 :" + "把" + disks + "号圆盘从" + from + "-> 移到 ->" + to);
    }
    /**
 * 递归实现汉诺塔的函数 * * @param n
 * @param A
 * @param B
 * @param C
 */
 public static void hanoi(int n, char A, char B, char C) {
        // 圆盘只有一个时,只需将其从 A 塔移到 C 塔
 if (n == 1) {
            // 将编 b 号为 1 的圆盘从 A 移到 C
 TowersOfHanoi.move(1, A, C);
        }
        // 否则
 else {
            // 递归,把 A 塔上编号 1~n- 1 的圆盘移到 B 上,以 C 为辅助塔
 hanoi(n - 1, A, C, B);
            // 把 A 塔上编号为 n 的圆盘移到 C 上
 TowersOfHanoi.move(n, A, C);
            // 递归,把 B 塔上编号 1~n- 1 的圆盘移到 C 上,以 A 为辅助塔
 hanoi(n - 1, B, A, C);
        }
    }
    public static void main(String[] args) {Scanner input = new Scanner(System.in);
        char A = 'A';
        char B = 'B';
        char C = 'C';
        System.out.println("******************************************************************************************");
        System.out.println("这是汉诺塔问题(把 A 塔上编号从小号到大号的圆盘从 A 塔通过 B 辅助塔挪动到 C 塔下来");
        System.out.println("******************************************************************************************");
        System.out.print("请输出圆盘的个数:");
        int disks = input.nextInt();
        TowersOfHanoi.hanoi(disks, A, B, C);
        System.out.println(">> 挪动了" + m + "次,把 A 上的圆盘都挪动到了 C 上");
        input.close();}
}

; “ 复制代码 ”)

六.图解程序运行流程:

(1)函数 hanoi(int n,char A,char B,char C) 的性能是把编号为 n 的圆盘借助 B 从 A 挪动到 C 上。

(2)函数 move(int n ,char N ,char M) 的性能是把 1 编号为 n 的圆盘从 N 移到 M 上

七.程序运行截图:

正文完
 0