汉诺塔–（数据结构）

我的数据结构学习从汉诺塔开始，这个简单的算法我可是整整想了一晚上，现在终于有点明白了，上机单步了几遍，有所了解，，还是写点什么以供以后参考，也希望能对正在学算法的盆友有所裨益······

总得来说汉诺塔就是层叠递归调用的典型例子，一直是利用A—>B A-->C B-->C这样的单个步骤。

具体来说，当盘数大于一时，不违背原则下（过程中总是大在下小的在上），A先借助B再放到C上。总是把盘数看成两个来解决问题。

比如说，当盘数为二时，顾名思义，这个很简单只要三下即可完成。这个时候，可以这样想，如果是三个，就相当于二个完成，还有一个待完成，（注意要有把问题简化为两个盘的思想,这样是递归思想的思想实现），那么把完成的看成一个，剩下待完成的看成一个（带完成的还可以把最近要完成的看成一个，剩下的先别管），这样问题就回到了二个盘数时的第一步完成状态，接下来就是递归的精华了（我是膜拜数学的强大，一个式子可以表达万种情感），然后C上的（二个看成一个那）在借助B放到A上，这样第三个就可以从B放到C上，接下来又是二个了（这个是真正的二个），看基本步骤完成。当盘数是N时，也是利用这种思想，一步一步简化，递归完成。

接下来谈一下N个盘要几次完成问题

书上说是2^n-1次，经过计算验证是正确的。当然我有我的思考计算，哈哈····思考如下：

当完成n个时设用M(n)次，那么，如上我说的算法当完成n个（也就是n+1个时了）还有一个，这时需要把在C上的看成一个，借助B移动到A上（这时最后一个已到B上），当然要做M（n）次搬动了，完成后，B上的最后一个（（n+1）个）搬动到C上。这时，问题又回到了n次开始，当然需要M(n)次了。这么一来就是M（n）2次，加上最后一个的两次，总共是M(n)2+2=M(n+1)次，好了现在是纯数学问题了，可以利用数学知识算出来最后结果，（我还没算，哈哈，我数学不好呀），步骤没错的话，应该结果是M（n）=2^n-1.

以上只是个人体会，写的有些弱智，有什么不正确的还请高人指教。

下面是程序具体实现，（上面为C下面C++）仅供参考······

[cpp] view plain copy print ?
1. #include
2. inta=0;
3. voidhanoi(intn,charA,charB,charC)
4. {
5.
6. a++;
7. if(n==1)
8. {
9. printf("Move sheet %d from %c to %c\n",n,A,C);
10. }
11. else
12. {
13. hanoi(n-1,A,C,B);
14. printf("Move sheet %d from %c to %c\n",n,A,C);
15. hanoi(n-1,B,A,C);
16. }
17. printf("a是：%d\n",a);
18. }
19. intmain()
20. {
21. intn;
22. printf("请输入盘数：");
23. scanf("%d",&n);
24. hanoi(n,"A","B","C");
25. return0;
26. }
27.
28. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
29.
30. #include
31. usingnamespacestd;
32. voidmove(intn,chars,chard)
33. {
34. cout<<n<<","<<s<<"->"<<d<<endl;
35. }
36. voidhanoi(intn,charA='A',charB='B',charC='C')
37. {if(1==n)
38. move(n,A,C);
39. else
40. {
41. hanoi(n-1,A,C,B); move(n,A,C); hanoi(n-1,B,A,C);
42. }
43. }
44. intmain()
45. {
46. inti=0;
47. cout<<"请输入盘数：";
48. cin>>i;
49. hanoi(i);
50. return0;
51. }
52. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[cpp] view plain copy print ?原文链接: https://www.cnblogs.com/snake-hand/p/3142990.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍