java 实现汉诺塔详解及实现代码

java 实现汉诺塔详解及实现代码

java 实现汉诺塔详解及实现代码

汉诺塔问题：有三根柱子A,B,C，其中A上面有n个圆盘，从上至下圆盘逐渐增大，每次只能移动一个圆盘，并且规定大的圆盘不能叠放在小的圆盘上面，现在想要把A上面的n个圆盘全部都移动到C上面，输出移动的总步数以及移动的过程

分析：

//先求出移动的总步数

1，假设g（n）表示n个圆盘时的移动总的步数，当n=1时，g(1)=1;

2.现在可以把g(n)进行细分为三步：

1>先将n-1个圆盘从A通过C移动到B上面，相当于将n-1个圆盘从A移动到C，因此需要g(n-1)步；

2>然后将剩下的最大的圆盘从A移动到C，需要1步；

3>最后再将n-1个圆盘从B通过A移动到C上面，相当于将n-1个圆盘从A移动到C，因此也需要g(n-1)步；

因此可以得出递归关系式：g(n) = 2*g(n-1)+1;

//现在我们在来求出移动的过程

1.假设hm(m,a,b,c)表示将m个圆盘从a通过b移动到c的过程，假设mv(a,c)输出一次a到c的过程，即print a-->c

2.初始化hm，当m=1时，hm(1,a,b,c)=mv(a,c);

2.可以把hm(m,a,b,c)进行细分为三步：

1>先将n-1个圆盘从A通过C移动到B，此时b和c进行互换，也就是 hm(m-1,a,c,b);

2>然后将剩下的最大的圆盘从A移动到C，也就是hm(1,a,b,c);

3>最后将n-1个圆盘从B通过A移动到C，此时b和a进行交换，也就是 hm(m-1,b,a,c);

最终得到过程的递归关系式：hm(m,a,b,c) = hm(m-1,a,c,b)+1+hm(m-1,b,a,c);

实现代码：

public class test{

public static void main(String[] args){

Scanner in = new Scanner(System.in);

int n = in.nextInt();

test t = new test();

//获取总的步数

System.out.println("需要移动的总步数为:" +t.getSum(n));

//获取移动的过程

t.hm(n,'a','b','c');

}

//获取总步数

public int getSum(int n){

if(n == 1)

return 1;

return 2 * getSum(n-1) +1 ;

}

//获取移动的过程

public void hm(int m,char a,char b,char c){

if(m == 1)

move(a,c);

hm(m-1,a,c,b);

move(a,c);

hm(m-1,b,a,c);

}

//输出一次移动的过程

public void move(char a,char c){

System.out.print(a + "-->" + c + " ");

}

}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。