java 实现汉诺塔详解及实现代码汉诺塔问题:有三根柱子A,B,C,其中A上面有n个圆盘,从上至下圆盘逐渐增大,每次只能移动一个圆盘,并且规定大的圆盘不能叠放在小的圆盘上面,现在想要把A上面的n个圆盘全部都移动到C上面,输出移动的总步数以及
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-->c2.初始化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);
--结束END--
本文标题: java 实现汉诺塔详解及实现代码
本文链接: https://www.lsjlt.com/news/226740.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-05-16
2024-05-16
2024-05-16
2024-05-16
2024-05-16
2024-05-16
2024-05-16
2024-05-16
2024-05-16
2024-05-16
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0