2022年分治法之汉诺塔实验报告 .pdf

《2022年分治法之汉诺塔实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年分治法之汉诺塔实验报告 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、陕西师范大学实验报告课题名称算法分析与设计项目名称分治法汉诺塔问题学院计算机科学学院专业计算机科学与技术指导老师王小明小组人员刘永军 高富雷 武子超报告时间2013/11/282013/11/28 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 分治法之汉诺塔问题目录一、设计目的 . 3二、设计内容 . 31任务描述 . 3i. 汉诺塔问题简介. 3ii. 设计任务简介. 32分治法算法的实现过程. 4三、流程图 . 6四、测试

2、结果 . 7五、总结 . 7附：程序源代码. 7名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 一、设计目的1、掌握分治法的思想；2、掌握分治法的典型问题，如汉诺塔问题以及其他问题；3、进一步多级调度的基本思想和算法设计方法；4、提高分析与解决问题的能力。二、设计内容1任务描述i.汉诺塔问题简介在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神大梵天在创造世界的时候，在其中一根针上从下到上地穿好了

3、由大到小的64 片金片，这就是所谓的汉诺塔。不论白天黑夜， 总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从大梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、 庙宇和众生也都将同归于尽。ii. 设计任务简介其实算法非常简单，当盘子的个数为n 时，移动的次数应等于2n - 1 （有兴趣的可以自己证明试试看） 。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。 首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n 为

4、偶数，按顺时针方向依次摆放 A B C ；若 n 为奇数，按顺时针方向依次摆放 A C B 。（1）按顺时针方向把圆盘1 从现在的柱子移动到下一根柱子，即当n 为偶数时，若圆盘1在柱子 A，则把它移动到B；若圆盘1 在柱子 B ，则把它移动到C；若圆盘 1 在柱子 C，则把它移动到A。（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。 这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。（3）反复进行（1） （2）操作，最后就能按规定完成汉诺塔的移动。所以结果非常简单，就是按

5、照移动规则向一个方向移动金片：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 如 3 阶汉诺塔的移动：A C,AB,CB,AC,BA,BC,AC。2分治法算法的实现过程首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若 n 为偶数，按顺时针方向依次摆放 A B C ；若 n 为奇数，按顺时针方向依次摆放 A C B 。（1）按顺时针方向把圆盘1 从现在的柱子移动到下一根

6、柱子，即当n 为偶数时，若圆盘1在柱子 A，则把它移动到B；若圆盘1 在柱子 B ，则把它移动到C；若圆盘 1 在柱子 C，则把它移动到A。（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。 这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。（3）反复进行（1） （2）操作，最后就能按规定完成汉诺塔的移动。所以结果非常简单，就是按照移动规则向一个方向移动金片：如是解决，我们就可以将n 个盘分治成1 个， 2 个， 3 个盘来讨论，如 1 阶汉诺塔的移动： AC；如 2 阶汉

7、诺塔的移动：AB, A C, B C; 如 3 阶汉诺塔的移动：A C,AB,CB,AC,BA,BC,AC。通过最简单的，最少阶数汉诺塔的移动，我们更具上面的讲解，联想到更多的阶数，不难看出其中的规律！因此，我们通过将多阶汉诺塔分解成少数像3 阶一样的汉诺塔，从繁化简，分而治之。解决汉诺塔问题。算法如下：void move( char a, int n, char c) printf(%c-%cn ,a,c); void hanoi(int n, char a, char b, char c, int &time) if (n=0) return ; if (n=1) move(a,1,c);

8、 time+; else hanoi(n-1,a,c,b, time); move(a,n,c); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - time+; hanoi(n-1,b,a,c, time); int main() int n; printf( 请输入汉诺塔的盘数: ); scanf( %d,&n); int time = 0; printf(%d个盘的汉诺塔移动方法是n ： ,n); hanoi(n,a , b

9、 , c,time); printf( 移动了 %d 次n , time); getchar(); getchar(); return 0; 算法分析 ：我们通过递归调用，主函数main() 调用 hanoi()函数， hanoi （）函数在调用move() 函数，以及hanoi()函数对自身的调用，在hanoi()函数自身调用中参数a,b 的交换，实现了品字形排列，顺序逆序的实现，从而解决问题。通过 time 参数的计算，我可可以知道该函数的时间复杂度是o(2n) 。其实我们通过数学归纳法就可以知道N阶汉诺塔需要移动的次数为2n-1 。名师资料总结 - - -精品资料欢迎下载 - - - -

10、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 三、流程图开始输入汉诺塔的阶数 Nhanoi(n, a , b , c ,time)N1输出N阶汉诺塔的移动方法结束T=a;a=b;b=Tnoyes调用 move()函数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 四、测试结果五、总结这次的设计的主要内容是分治算法，汉

11、诺塔问题不难， 但却是典型的分治算法中递归调用案例之一。 因此通过这次练习， 让我们小组更加深刻的认识到分治法的优越性以及优中求优，对算法加以修正，做到最好。附：程序源代码汉罗塔.cpp/ 汉罗塔 .cpp : 定义控制台应用程序的入口点。/ #include stdafx.h #include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - #include void move( char a, int n, char c)

12、printf(%c-%cn ,a,c); void hanoi(int n, char a, char b, char c, int &time) if (n=0) return ; if (n=1) move(a,1,c); time+; else hanoi(n-1,a,c,b, time); move(a,n,c); time+; hanoi(n-1,b,a,c, time); int main() int n; printf( 请输入汉诺塔的盘数: ); scanf( %d,&n); int time = 0; printf(%d个盘的汉诺塔移动方法是n ： ,n); hanoi(n,a , b , c,time); printf( 移动了 %d 次n , time); getchar(); getchar(); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -