《算法分析与设计》实验指导书

《《算法分析与设计》实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法分析与设计》实验指导书重庆邮电大学应用技术学院二○○八年四月《算法分析与设计》实验目的与要求一、实验目的算法分析与设计是信息与计算科学专业中一门重要的专业课程。当用计算机来解决实际问题时，就要涉及到对实际问题进行抽象模拟，也就是数学建模的过程，然后再设计相应的解决算法来解决实际问题，还要验证所设计的算法能够在可忍受或可达到的时间和空间内完成任务，因此算法的分析与设计就成了非常重要的环节。通过理论课的学习，我们知道要想设计一个算法必须从算法设计->算法确认->算法分析->编码->检查->调试->计时，七大步骤严格执行，所以读者可严格按

2、照以上步骤进行，为以后进行算法研究的工作打下坚实的基础。二、实验要求1．准备好上机所需要的程序，并经人工检查后才能上机，以提高上机效率。对程序中自己有疑问的地方应作记号，以便在上机时给予注意。不得抄别人所编的程序。2．上机输入并调试所编的程序。3．上机结束后，提交实验报告，实验报告应包括以下内容：（1）题目；（2）算法的基本思想描述；（3）算法分析；（4）主要数据结构描述；（5）程序流程图；（6）程序清单；（7）运行的结果；（8）对运行情况所作的分析以及本次调试程序所取的经验。如果程序未通过，应分析其原因。三、实验步骤1．问题分析和任务的

3、定义明确问题要求做什么，限制做什么（本步强调做什么，而不是怎么做）。对问题的描述应避开算法和所涉及的数据类型，而是所完成的任务做出明确的回答。如输入数据的类型、值的范围以及输入的形式；输出数据的类型、值得范围及输出的形式；这异步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。2．数据类型和系统设计在设计这一步骤中分为逻辑设计和详细设计两步实现。逻辑设计指的是，为问题的描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的

4、伪码算法。在这个过程中，要综合考虑系统的功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据的封装，基本操作的规格说明尽可能的明确和具体。作为逻辑设计的结果。应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作的规格说明做出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出函数形式的算法框架。3．编码实现和静态检查4．上机准备和上机调试5．总结和整理实习报告四、实验总结对实验中发现的问

5、题，调试中的问题分析、解决方法，对算法的改进意见、建议、收获、体会等。实验报告参考规范：实验题目班级姓名学号日期一、需求分析1．程序的功能；2．输入输出的要求；3．测试数据。二、概要设计1．本程序所用的抽象数据类型的定义；2．主程序的流程及各程序模块之间的层次关系。三、详细设计1．采用c语言定义相关的数据类型；2．写出各模块的伪码算法；3．画出函数的调用关系图。四、调试分析1．调试中遇到的问题及对问题的解决方法；（编译错误与运行错误）2．算法的时间复杂度和空间复杂度。五、运行结果1、程序的使用说明2、运行结果六、实验完成后的思考1、通过实

6、验学到了什么、理解了什么2、程序还有哪些不足或还有哪些需要完善的地方七、源程序（带注释）实验一斐波那契数列实验目的1．掌握递归算法及其编程方法；实验课时总课时：2学时/1次实验内容1．利用递归方法或非递归方法实现求斐波那契数列第n项的值斐波那契数列描述如下：F(n)=f(n-1)+f(n-2)F(1)=1F(2)=12．根据算法编制代码（C/C++语言编写，环境可选TC2或VC6）3．调试代码直至得出正确结果实验要求一、输入一个值n，能够得出第n项的斐波那契数列值，当n值不是一个合法值时，给出提示（越详细越好）二、程序能够循环输入值n三、

7、程序有退出键四、下课前提交word文档，内容包括程序代码、运行结果截图（正确的和错误的n值）16实验二实验目的1、掌握基础算法分析和编程方法；实验课时总课时：2学时/1次实验内容1．完成下列程序*　　*.*.　　*..*..*..　　*...*...*...*...　　*....*....*....*....*....　　*.....*.....*.....*.....*.....*.....　　*......*......*......*......*......*......*......　　*.......*.......*....

8、...*.......*.......*.......*.......*.......实验要求一、下课前提交word文档，内容包括程序代码、运行结果截图16实验三排序实验目的1.、掌握排序算法