著名的汉诺(Hanoi)塔问题通常是用 方法解决?,汉诺塔解析

汉诺塔问题是算法中的经典中的经典，是递归思想的入门问题。一般是这样描述：左中右三根柱子，左边柱子上有n个圆盘 每个圆盘从下至上从大到下排列，移动过程中小的圆盘不能放在大圆盘下面，要求将左边柱子上的圆盘全部移动到右边圆盘上，可以借助中间的圆盘。返回其时间复杂度并且打印每一个步骤。
分析：
首先用特例来初步了解过程即n=2的时候 左边有两个圆盘大圆盘编号为做左1放在下面，小圆盘编号为左2放在上面，移动过程为：
1，左1 从左到中
2，左2 从左到右
3，左1 从中到右
那么当左边有n个圆盘的时候步骤为：
1，左1—（n-1） 从左到中
2，左n 从左到右
3，左1—（n-1）从中到右
n个圆盘需要移动的步骤数推到过程：
1—（n-1）从左到中 和从中到右 所需的步数是一样的即f(n-1)步
所以：总步数就是三个移动过程步数相加
f(n)=f(n-1)+1+f(n-1)
推理：
f(n)+1=2(f(n-1)+1)
且f(1) = 2 这是等比数列 用公式得：
f(n)=2^n - 1;
所以时间复杂度为O(2^n)

public class Hanoi { public static void main(String[] args) { hanoi(3);//实例有三个的情况 } public static void hanoi(int n){ if(n>0){ func(n,"left","mid","right"); } } public static void func(int n ,String from,String mid,String to){ if(n==1){ System.out.println("move from "+from+" to "+to); }else{ func(n-1,from,to,mid); func(1,from,mid,to); func(n-1,mid,from,to); } }}