算法设计技能训练网络1121胡伟

算法设计技能训练实习报告题目：汉诺威塔系（院）:计算机工程学院专业：班级：网络1121学号：姓名：指导教师：学年学期:2013~2014学年第1学期2013年12月6日2算法设计技能训练任务书课题名称设计目的1、通过算法设计技能训练，深入理解算法设计的意义和重要性，更好地掌握算法设计的知识。2、能够针对某一具体问题，设计算法进行解决。3、锻炼实践动手能力，提高解决问题的能力。实验环境硬件：1、PC机，奔腾Ⅳ以上CPU，512MB以上内存，80G以上硬盘；软件：VisualC++编程工具任务要求1）界面友好，函数功能要划分好2）总体设计应画——流程图3）程序要加必要的注释4）要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。工作进度计划序号起止日期工作内容12013.12.2任务下达，查阅文献资料22013.12.2～2013.12.4总体设计、素材搜集、课题详细设计、调试32013.12.5～2013.12.6完善设计、撰写报告42013.12.6答辩指导教师（签章）：年月日3摘要汉诺威塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。所以，设计的目的是运用方法来移动盘子，使原有上小底大的一个柱子上的盘子，每次移动一个，且小盘子要放在大盘子的上面，移动到另一个柱子上，其中只能借助低三根柱子。通过C++语言来编写程序来实现至少5层的调整过程。功能：显示汉诺威塔的调整过程。实施：搭好框架，确定人机对话界面，确定函数个数，实行调整。（1）课题概述（课题的来源，预期目标，面对要解决的问题和需要去解决的问题所用的方法）（2）需求分析（设计的思路，方案，以及功能）（3）设计思路与算法（4）运行结果（5）附录关键词汉诺威塔调整C++益智递归选择数据结构4目录引言..........................................................................................................................................................51汉诺威塔的概述...................................................................................................................................52需求分析...............................................................................................................................................72.1分支结构——IF语句...................................................................................................................72.2分支结构——SWITCH语句............................................................................................................82.4问题概述.....................................................................................................................................102.5三层的汉诺威塔演示.................................................................................................................103算法与代码.........................................................................................................................................123.1分析.............................................................................................................................................123.2代码与注释.................................................................................................................................143.2.1Hanoi函数关于递归调整的代码：...................................................................................143.2.2自动移动的汉诺威塔函数可以根据输入的层数进行处理.............................................154运行结果.............................................................................................................................................20总结........................................................................................................................................................22附录：....................................................................................................................................................23参考文献................................................................................................................................................33指导教师评语........................................................................................................................................345引言汉诺威塔是一款集娱乐与运算的智力游戏，他不仅可以在闲时帮助我们度过美好的时光，还可以在玩的过程中锻炼我们的思维，开发你的思维。本课题的设计是为了解决n层汉诺威塔调整的解决方案，通过循环，选择，递归等算法来来构造不同的函数，主要的是调整，因此最主要的函数hanoi通过递归的方法来实现每层的调整，同时每层的移动也涉及了数组和if的选择，swith的选择。通过使用者输入汉诺威塔的层数，根据不同层数进行处理。来源：法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。[1]不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1）=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，假如每秒钟一次，共需多长时间呢？一个平年365天有31536000秒，闰年366天有31622400秒，平均每年31556952秒，计算一下，1.844674407584554049253.855年这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。1汉诺威塔的概述1．1汉诺威塔及其调整的示意图如图1-1所示为初步设想的效果图6图1-11.2问题内容汉诺塔问题：这是一个古典的数学问题，是一个用递归方法解题的典型例子。问题是这样的：古代有一个梵塔，塔内有三个座Ａ、Ｂ、Ｃ，开始时Ａ座上有６４个盘子，盘子的大小不等，大的在下，小的在上。有一个老和尚想把这６４个盘子从Ａ座移动到Ｃ座。但每次一允许移动一个盘子，且在移动的过程中在３个座上都始终保持大盘在下，小盘在上。1.3预期目标通过编写汉诺威塔的程序代码，来了解汉诺威塔的本质和历史，来加深对程序种方法的理解，并且熟悉所学过的书本知识。7可以运行出友好的界面，并且可以根据界面的提示输入任意的层数，当输入的层数不同时，所运行的步骤也不同，显示出移动的顺序，还可以自动演示移动的过程。1.4遇到的问题汉诺威塔是一个古老的问题，它不仅是一个有趣味的数学问题，而且是关于计算机编程的一个课题。在编程中面对的主要问题有以下几个：①采用递归对移动的显示②采用if和switch语句来对汉诺威塔的每一层进行处理③汉诺威塔的显示1.5学要解决的技术我们需要去解决以上的主要问题，通过c++的递归算法，和一些基本的语句，尽管有些重复，但也是必要的。2需求分析2.1分支结构——if语句If语句的表达方法：if（表达式1）语句1elseif（表达式2）语句2elseif（表达式3）语句3elseif（表达式m）语句melse语句n在每个语句中，可以有多个语句，但需要加上大括号对于可能发生的事情，我们平时经常会说“如果……，那么……”。语文里，我们叫它条件复句。“如果”之后的内容我们称为条件，当条件满足时，就会发生“那么”之后的事件。我们来看这样一句英语：Ifmark90,cout”GOOD!”endl.把它翻译成中文就是：如果分数大于90，则输出GOOD。其实在程序设计中，也是用“如果”来描述可能发生的情况的。它和刚才的那句英语很相似，具体的语法格式是：8我们把若干句语句放在一个大括号中，称为语句块。运行到该if语句，当条件满足时，就会执行语句块内的内容。我们也可以用流程图（图4.1.1）来表示if语句。请注意，if语句的结束是没有分号的，分号只是属于语句块中的语句。2.2分支结构——Switch语句在C++中，也有这样的开关，那就是switch语句。它能够很简捷地描述出多岔路