河内之塔解决方法

河内之塔河内之塔 班级 信管一班班级 信管一班 姓名 王苗兵姓名 王苗兵 学号 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 运行结果如下 在键盘上输入数字 3 还可以继续输入数值 数值越大 所需搬运的次数也越大 4 调试报告调试报告 4 1 测试用例测试用例 首先 测试程序能不能运算出正确的结果 输入数据 3 出现了 7 组符合要 求的解 接着输入数据 0 提示输入错误 重新输入 4 能得到正确运行结果 出现了 7 组符合要求的解 从而可知输入的数据要为整数 4 2 调试运行结果调试运行结果 程序第一次编译时 有 19 个错误 都是语法错误 修改后 能通过编译 第一次运行 并不能输出正确结果 主要原因有两个 一个是输入的数据类型 不对 另一个是 输入的数值不对 其他的错误有除数不能为零 括号的位置不 对 经过修改 调试后 能运算出正确的结果 在键盘上输入数据 3 程序运行成功 运行结果如上图设计程序中的结果所示 并且仍可以继续输入数据 出现运行结果 不同的盘子数 所搬运的次数不同 数值越大 搬运次数越多 5 结束语结束语 通过本次的课程学习与设计 让我对 java 程序的数据结构和程序设计算法 的思路有了更深刻有更全面更进一步的认识 拓宽了我对于算法设计的思维与 解决能力 根据不同的需求 采用不同的数据存储方式 不一定要用栈 二叉 树等高级类型 有时用基本的一维数组 只要运用得当 也能达到相同的效果 甚至更佳 就如这次的课程设计题目 河内之塔 通过用简单的 if 判断 舍 弃多余的循环 提高了程序的运行效率 在编写这个程序的过程中 我温习了之前学的基本语法 更加深刻的认识到 循环是大部分程序的基本要素 结合了这学期学的数据结构 分析算法的时间 复杂度 不断改进算法 更加巩固了之前学的知识 比以前更能灵活运用 本次写的程序还有很大的发展空间 可以通过循环 重复输入数据 多次 计算盘子搬运次数 还可以通过设计 让程序能计算出任意结果 在输出方面 为提高运行效率 可以设计只输出一组解 在输入方面 放宽数据类型 随着 数量增加 循环增加 为提高运行效率 可以考虑更改数据类型 通过本次的 java