分治算法：汉诺塔问题

本文主要是介绍分治算法：汉诺塔问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1，基本介绍

分治算法是一种重要的算法。基本思想就是“分而治之”，将一个复杂的问题分为多个相似的子问题，然后再把子问题分为更小的子问题，直到最后子问题可以以一种最简单的方式直接求解，原问题的解即为子问题解的合并。分治算法的一些经典算法如：二分搜索，棋盘模型，合并排序，快速排序，汉诺塔等，以下将用汉诺塔举例

2，基本步骤

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
解决：如果子问题规模较小，则直接求解；如果规模较大，则递归求解
合并：将各个子问题的解合并为主问题的解

3，汉诺塔代码实现

如果问题规模足够小，只有一个塔片，则直接从A塔移动到C塔
如果A塔上有多个塔盘，则对问题进行分解，将最后一个塔盘上面的所有塔盘移动到B塔，将最后一个塔盘移动到C塔，最后将B塔的所有塔盘移动到C塔
如果最后一个塔盘上面的塔盘规模不够小，则继续递归处理，直至问题解决

package com.self.datastructure.algorithm.dac;/*** 分治算法实现之_汉诺塔* @author pj_zhang* @create 2020-06-26 17:55**/
public class HanoiTower {public static void main(String[] args) {hanoiTower(3, 'A', 'B', 'C');}/*** 汉诺塔实现* @param num 汉诺塔数量* @param a 处理中的第一个塔柱* @param b 处理中的第二个塔柱* @param c 处理中的第三个塔柱*/private static void hanoiTower(int num, char a, char b, char c) {if (num == 1) {// 如果数量为1, 则直接从A移动到CSystem.out.println("将第 " + num + " 个塔片从 " + a + " 移动到 " + c);} else {// 如果有多个塔片, 则分开处理// 首先最下层塔片上面的所有塔片从A移动到BhanoiTower(num - 1, a, c, b);// 然后将最下面的盘从A移动到CSystem.out.println("将第 " + num + " 个塔片从 " + a + " 移动到 " + c);// 最后将移动到B的盘统一移动到ChanoiTower(num - 1, b, a, c);}}}