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)步；
冒泡排序java代码详解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 + "  ");
}
}
感谢阅读，希望能帮助到⼤家，谢谢⼤家对本站的⽀持！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。