分治法思想递归解决汉诺塔问题

妖狐艹你老母 2023-02-16 06:03 15阅读 0赞

### 分治思想 ###

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解  
法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到  
求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还  
较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是  
分治策略的基本思想。

### 汉诺塔问题 ###

汉诺塔问题是由很多放置在三个塔座上的盘子组成的一个古老的难题。如下图所示，所有盘子的直 径是不同的，并且盘子中央都有一个洞使得它们刚好可以放在塔座上。所有的盘子刚开始都放置在A 塔 座上。这个难题的目标是将所有的盘子都从塔座A移动到塔座C上，每次只可以移动一个盘子，并且任何 一个盘子都不可以放置在比自己小的盘子之上。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]  
试想一下，如果只有两个盘子，盘子从小到大我们以数字命名(也可以想象为直径)，两个盘子上 面就是盘子1，下面是盘子2，那么我们只需要将盘子1先移动到B塔座上，然后将盘子2移动到C塔座，最 后将盘子1移动到C塔座上。即完成2个盘子从A到C的移动。  
如果有三个盘子，那么我们将盘子1放到C塔座，盘子2放到B塔座，在将C塔座的盘子1放到B塔座 上，然后将A塔座的盘子3放到C塔座上，然后将B塔座的盘子1放到A塔座，将B塔座的盘子2放到C塔座， 最后将A塔座的盘子1放到C塔座上。  
以下是手画的一个草图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 1]  
如果有四个，五个，N个盘子，那么我们应该怎么去做?这时候递归的思想就很好解决这样的问题 了，当只有两个盘子的时候，我们只需要将B塔座作为中介，将盘子1先放到中介塔座B上，然后将盘子2 放到目标塔座C上，最后将中介塔座B上的盘子放到目标塔座C上即可。  
所以无论有多少个盘子，我们都将其看做只有两个盘子。假设有 N 个盘子在塔座A上，我们将其看 为两个盘子，其中(N-1)~1个盘子看成是一个盘子，最下面第N个盘子看成是一个盘子，那么解决办法 为:  
1、先将A塔座的第(N-1)~1个盘子看成是一个盘子，放到中介塔座B上，然后将第N个盘子放到目标 塔座C上。  
2、然后A塔座为空，看成是中介塔座，B塔座这时候有N-1个盘子，将第(N-2)~1个盘子看成是一个 盘子，放到中介塔座A上，然后将B塔座的第(N-1)号盘子放到目标塔座C上。  
3、这时候A塔座上有(N-2)个盘子，B塔座为空，又将B塔座视为中介塔座，重复1，2步骤，直到 所有盘子都放到目标塔座C上结束。  
简单来说，跟把大象放进冰箱的步骤一样，递归算法为: 1、从初始塔座A上移动包含n-1个盘子到中介塔座B上。 2、将初始塔座A上剩余的一个盘子(最大的一个盘子)放到目标塔座C上。 3、将中介塔座B上n-1个盘子移动到目标塔座C上。

/**
    * 汉诺塔问题
    * @param dish 盘子个数(也表示名称) * @param from 初始塔座
    * @param temp 中介塔座
    * @param to 目标塔座
    */
    public static void move(int dish,String from,String temp,String to){
        
        if(dish == 1){
        
    System.out.println("将盘子"+dish+"从塔座"+from+"移动到目标塔座"+to); }else{
        
    move(dish-1,from,to,temp);//A为初始塔座，B为目标塔座，C为中介塔座 System.out.println("将盘子"+dish+"从塔座"+from+"移动到目标塔座"+to);
    }

测试：

> move(3,“A”,“B”,“C”);  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200608183844527.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200608183946908.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200608184216716.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70