分治算法(汉诺塔问题)
一. 算法介绍：
分治算法，其实就是把一个大问题看成若干个小问题，解决了所有的小问题，那么大问题就解决了，原问题的解就是子问题解的合并，之前说的归并排序、快速排序，都用到了分治思想。
二. 分治算法的基本步骤：
- 分解：将原问题分解成若干个相互独立的、规模较小的、容易求解的、与原问题形式相同的子问题；
- 解决：直接求解子问题或者递归求解子问题；
- 合并：将各个子问题的解合并为原问题的解。
三. 分治算法经典应用：汉诺塔问题
1. 汉诺塔问题介绍：
汉诺塔
汉诺塔问题介绍
2. 怎么玩？
玩法
3. 思路分析：
我们先给3根针标上号，左边的是A，中间的是B，右边的是C。
- 假如只有一个盘，那就直接从A移动到C；
- 假如有两个盘，那就把上面那个从A移动到B，把底下那个从A到C，再把B中的移到C；
- 假如有多个盘，我们也可以按照两个盘的方式处理。即把最下边的看成一个盘，其他所有的看成一个盘；当然这里其他所有的还可以按照这种方式再进行分治。
4. 代码实现：
public class HanoiTower {
/**
* 汉诺塔问题
* @param plateNum 盘子的数量
* @param a 出发地，初始的时候是A
* @param b 中转地，初始的时候是B
* @param c 目的地，初始的时候是C
*/
public static void hanoiTower(int plateNum, String a, String b, String c) {
if (plateNum == 1) {
System.out.println("从 " + a + " 到 " + c);
} else { // 盘子数量大于等于2的情况
// 上面的从A到B
hanoiTower(plateNum - 1, a, c, b);
// 最下面那个从A到C
System.out.println("从 " + a + " 到 " + c);
// B针上的所有搬到C
hanoiTower(plateNum - 1, b, a, c);
}
}
public static void main(String[] args) {
hanoiTower(5, "A", "B", "C");
}
}怎么验证对不对呢？打开4399或者7k7k，搜索汉诺塔，选择盘子的数量，运行代码，按照代码打印的结果去玩这个游戏，就知道对不对了。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
