《算法分析与设计》实验指导书重庆邮电大学应用技术学院二○○八年四月《算法分析与设计》实验目的与要求一、实验目的算法分析与设计是信息与计算科学专业中一门重要的专业课程当用计算机来解决实际问题时，就要涉及到对实际问题进行抽象模拟，也就是数学建模的过程，然后再设计相应的解决算法来解决实际问题，还要验证所设计的算法能够在可忍受或可达到的时间和空间内完成任务，因此算法的分析与设计就成了非常重要的环节通过理论课的学习，我们知道要想设计一个算法必须从算法设计->算法确认->算法分析->编码->检查->调试->计时，七大步骤严格执行，所以读者可严格按照以上步骤进行，为以后进行算法研究的工作打下坚实的基础二、实验要求1．准备好上机所需要的程序，并经人工检查后才能上机，以提高上机效率对程序中自己有疑问的地方应作记号，以便在上机时给予注意不得抄别人所编的程序 2．上机输入并调试所编的程序 3．上机结束后，提交实验报告，实验报告应包括以下内容：（1）题目；（2）算法的基本思想描述；（3）算法分析；（4）主要数据结构描述；（5）程序流程图； （6）程序清单；（7）运行的结果；（8）对运行情况所作的分析以及本次调试程序所取的经验。
如果程序未通过，应分析其原因三、实验步骤1．问题分析和任务的定义明确问题要求做什么，限制做什么（本步强调做什么，而不是怎么做）对问题的描述应避开算法和所涉及的数据类型，而是所完成的任务做出明确的回答如输入数据的类型、值的范围以及输入的形式；输出数据的类型、值得范围及输出的形式；这异步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据2． 数据类型和系统设计在设计这一步骤中分为逻辑设计和详细设计两步实现逻辑设计指的是，为问题的描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法在这个过程中，要综合考虑系统的功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据的封装，基本操作的规格说明尽可能的明确和具体作为逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图详细设计的结果是对数据结构和基本操作的规格说明做出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出函数形式的算法框架。
3． 编码实现和静态检查4． 上机准备和上机调试5． 总结和整理实习报告四、实验总结对实验中发现的问题，调试中的问题分析、解决方法，对算法的改进意见、建议、收获、体会等实验报告参考规范：实验题目班级 姓名 学号 日期一、 需求分析1． 程序的功能；2． 输入输出的要求；3． 测试数据二、 概要设计1． 本程序所用的抽象数据类型的定义；2． 主程序的流程及各程序模块之间的层次关系三、 详细设计1． 采用c语言定义相关的数据类型；2． 写出各模块的伪码算法；3． 画出函数的调用关系图四、 调试分析1． 调试中遇到的问题及对问题的解决方法；（编译错误与运行错误）2． 算法的时间复杂度和空间复杂度五、 运行结果1、 程序的使用说明2、 运行结果六、 实验完成后的思考1、 通过实验学到了什么、理解了什么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三、 程序有退出键四、 下课前提交word文档，内容包括程序代码、运行结果截图（正确的和错误的n值）实验二 实验目的1、 掌握基础算法分析和编程方法；实验课时总课时：2学时/1次实验内容1．完成下列程序* *.*. *..*..*.. *...*...*...*... *....*....*....*....*.... *.....*.....*.....*.....*.....*..... *......*......*......*......*......*......*...... *.......*.......*.......*.......*.......*.......*.......*.......实验要求一、 下课前提交word文档，内容包括程序代码、运行结果截图实验三 排序实验目的1.、掌握排序算法分析和编程方法；实验课时总课时：2学时/1次实验内容1．完成下列程序，实现对数组的降序排序 #include void sort( ); int main() { int array[]={45，56，76，234，1，34，23，2，3}； //数字任意给出 sort( ); return 0; } void sort( ) { } 实验要求一、方法不限，下课前提交word文档，内容包括程序代码、运行结果截图实验四 螺旋数列实验目的1.、掌握算法分析和编程方法；实验课时总课时：2学时/1次实验内容如图： 7 8 9 10 6 1 2 11 5 4 3 12 16 15 14 13 设“1”的坐标为（0，0） “7”的坐标为（－1，－1） 编写一个小程序，使程序做到输入坐标（X,Y）之后显示出相应的数字。
实验要求一、方法不限，下课前提交word文档，内容包括程序代码、运行结果截图实验五六七八实验目的1.、掌握算法分析和编程方法；实验课时总课时：2学时/1次，共8学时实验内容在下面的题目中任选40分的题作为实验五六七八的实验内容1、（15分）要求：随机产生一个字符串，每次产生的字符串内容，长度都不同2、（15分）将整数转换成字符串：char* itoa(int); 例如itoa(-123)则返回“-123”;3、（15分）设计函数 int atoi(char *s) atoi()会扫描参数s字符串，跳过前面的空格字符，直到遇上数字或正负符号才开始做转换，而再 遇到非数字或字符串结束时('')才结束转换，并将结果返回返回值 返回转换后的整型数4、（15分）并编写一个函数实现一个整数到二进制数的转换，如输入6，输出1105、（15分）写函数将一个字符串反转. 函数原型如下:char *reverse(char *str);6、（15分）写一个函数将一个链表逆序. 比如一个链表是这样的: 1->2->3->4->5 通过反转后成为5->4->3->2->17、（25分）题目描述：一个正整数有可能可以被表示为 n 个连续正整数之和，如： 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。
输入数据：一个正整数，以命令行参数的形式提供给程序 输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列此外，序列不允许重复，序列内的整数用一个空格分隔如果没有符合要求的序列，输出 “NONE” 例如，对于 15 ，其输出结果是： 1 2 3 4 5 4 5 6 7 8 对于 16 ，其输出结果是： NONE 8、（25分）题目描述 为了在紧张的上班时间让员工们轻松些，百度休息室里放置着按摩椅、 CD 、高尔夫套装和 Wii 游戏机等休闲用品其中最受欢迎的当然是游戏机 wii 游戏机每个手柄需要使用两节电池（这两个电池可以是不同的品牌）工程师们在玩游戏时如果手柄没有电，他们都是将其中没电的电池拿走，并换上一个全新的电池，有电的必须继续使用 例如，已知三种电池的使用时间分别为 3 小时、 5 小时和 8 小时一开始，工程师使用 3 小时和 5 小时的电池 3 小时后，换上一个 8 小时的，再过 2 小时后，手柄再次没电时，已经没有电池可用了但如果一开始就使用那个 8 小时电量的电池，可以玩满 8 个小时。
告诉你每个品牌电池的使用时间以及该品牌电池的个数，请计算工程师们玩游戏时间的最小值和最大值输入格式输入第一行为一个正整数 n ，表示电池的种数接下来 n 行，每行两个整数 L 和 F ，表示使用时间为 L 的电池有 F 个输出格式输出仅一行，包含两个整数，分别表示工程师们的最短游戏时间和最长游戏时间（短的时间在前）两个整数之间以空格隔开 输入样例 3 3 2 5 2 8 2 输出样例 5 8 9、（25分）题目描述 “ 叉烧鸡翅膀，我呀最爱吃！ ……” 百度 spider 组的 “ 黑龙潭之行 ” 在烤着鸡翅，唱着星爷的经典时达到高潮大家在篝火旁围成一圈，开始玩 “ 数 7 ” 加强版游戏，规则如下： 规则 1 ： 遇 7 的倍数或含 7 的数时 pass 规则 2 ： 遇有包含相同数字的数时 pass 注意相同数字不必相邻例如 121 数错的惩罚很残酷 —— 吞食烤全羊为避免惩罚，百度工程师们需要你 —— 史上最强程序员的帮助百度工程师想知道： req1 x ：符合规则 1 的第 x 个数是什么？ req2 y ：符合规则 2 的第 y 个数是什么？ req12 z ：同时符合规则 1 、 2 的第 z 个数是什么？ query n ：数 n 是规则 1 中的第几个数，是规则 2 中的第几个数？ 输入格式 输入的每一行为一个查询，由一个查询词和一个无符号整型数组成。
共有四种查询，查询词分别为 req1 、 req2 、 req12 、 query （区分大小写） 输出格式 前三种查询输出一个无符号整型的解对于 “ query n ” 的查询，若 n 是规则中的数则输出相应的解，否则输出 -1 输入样例 req1 10 req2 10 req12 10 query 14 输出样例 11 10 12 -1 13 补充说明 输入数据共分五组，前四组中： 1<=x<=10000000,1<=y<1000000,1<=z<250000, 1<=n<24000000. ；第五组中的 y 可能达到 5000000 10、（40分）饭团的烦恼“午餐饭团“是。