河内之塔解决方法.doc

河内之塔

班级：信管一班
姓名：王苗兵
学号：201119331029

1设计题目
河内之塔
2 问题描述
说明河内之塔(Towers of Hanoi)是法国人(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家曾提及这个故事，据说创世有一座教塔，是由三支钻石棒所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。
3设计
解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：264- 1 = 18446744073709551615为5.05390248594782e+16年，也就是约五千个世纪，如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。
程序代码如下：
程序采用穷举法，对输入的数值进行分析，需要 2^n – 1次搬运。if来判断，算法如下。

void Hanoi(int n,char A,char B,char C) 
  {      if(n == 1)  
  {    printf("Move sheet %d from %c to %c \n",n,A,C);  
}  
else 
    {  
       Hanoi(n-1,A,C,B);    
       printf("Move sheet %d from %c to %c \n",n,A,B); 
  Hanoi(n-1,B,A,C);    
  }  
}
</span>  
运行结果如下：在键盘上输入数字 3

还可以继续输入数值，数值越大，所需搬运的次数也越大。
4调试报告
4.1 测试用例
首先，测试程序能不能运算出正确的结果，输入数据3出现了7组符合要求的解。
接着输入数据0提示输入错误，重新输入4能得到正确运行结果。出现了7组符合要求的解。
从而可知输入的数据要为整数，
4．2调试运行结果
程序第一次编译时，有19个错误，都是语法错误，修改后，能通过编译。第一次运行，并不能输出正确结果，主要原因有两个：一个是输入的数据类型不对；另一个是 输入的数值不对。其他的错误有除数不能为零，括号的位置不对。经过修改，调试后，能运算出正确的结果。
在键盘上输入数据3，程序运行成功，运行结果如上图设计程序中的结果所示
并且仍可以继续输入数据，出现运行结果，不同的盘子数，所搬运的次数不同，数值越大，搬运次数越多。

5 结束语
通过本次的课程学习与设计，让我对java程序的数据结构和程序设计算法的思路有了更深刻有更全面更进一步的认识，拓宽了我对于算法设计的思维与解决能力。根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计题目----河内之塔，通过用简单的if判断，舍弃多余的循环，提高了程序的运行效率。
在编写这个程序的过程中，我温习了之前学的基本语法，更加深刻的认识到循环是大部分程序的基本要素。结合了这学期学的数据结构，分析算法的时间复杂度，不断改进算法，更加巩固了之前学的知识，比以前更能灵活运用。
本次写的程序还有很大的发展空间，可以通过循环，重复输入数据，多次计算盘子搬运次数。还可以通过设计，让程序能计算出任意结果，。在输出方面，为提高运行效率，可以设计只输出一组解。在输入方面，放宽数据类型。随着数量增加，循环增加，为提高运行效率，可以考虑更改数据类型。
通过本次的java课程算法设计，我收获了很多，巩固旧知识的同时，学习了新的知识。更重要的是，它使我对java程序设计算法产生了浓厚的兴趣，面对一道编程题时有了新的思维，对编写程序更有信心。