算法——分治算法（汉诺塔的实现 Java代码）

怼烎@ 2023-02-13 05:47 5阅读 0赞

分治法是一种很重要的算法。字面上的解释是“分而治之”.就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直按求解，原问题的解即子问题的解的合井。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并撞序)，傅立叶变换(快速傅立叶变换)。

使用分治算法可以解决排序当中的归并排序：[归并排序 单击前往！][Link 1]

➢ 汉诺塔游戏的演示和思路分析: .

1.  如果是有一个盘，A->C
2.  如果我们有n>=2情况，我们总是可以看做是两个盘1.最下边的盘2.上面的盘
    
    1.  先把最上面的盘A->B
    2.  把最下边的盘A->C
    3.  把B塔的所有盘从B~>C

代码实现：

package DivideConquer;
    
    public class Hanoitower { 
    	public static void main(String[] args) { 
    		move(5, 'A', 'B', 'C');
    	}
    
    	// 移动方法
    	public static  void move(int num, char a, char b, char c) { 
    		// 如果只有一个
    		if (num == 1) { 
    			System.out.println("第 1个盘，从 "+ a + " -> " + c); 
    		} else { 
    			//把最上面的所有盘移动到b
    			move(num - 1, a, c, b);
    			//把最下面的盘移到c
    			System.out.println("第 " + num + "个盘，从 " + a + " -> " + c);
    			//把b上剩余的移到c
    			move(num - 1, b, a, c);
    		}
    	}
    }

进行测试：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]

[Link 1]: https://blog.csdn.net/qq_44973159/article/details/106071569
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200527175248380.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70