《算法设计与分析》实验报告.doc

华东理工大学（计12） 算法设计与分析 实 验 报 告 （ 1 ）学号： x2014002 姓名： 何意 班级： 计131 成绩：实验名称：算法概述实验地点：所使用的工具软件及环境：win7, visual c+/java 一、实验目的：熟悉数据结构和基本的排序和搜索算法，熟悉编程语言的集成开发环境，掌握程序设计与实现的能力，分析算法的复杂度。 2、 实验内容描述：（在该章题目库中选择5个题目，填写题目内容及输入输出要求。）1、数列有序!description有n(n=100)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请将该数插入到序列中，并使新的序列仍然有序。input输入数据包含多个测试实例，每组数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0标示输入数据的结束，本行不做处理。output对于每个测试实例，输出插入新的元素后的数列。sampleinput3 31 2 40 0sampleoutput1 2 3 42、绝对值排序description输入n(n=100)个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。input输入数据有多组，每组占一行，每行的第一个数字为n,接着是n个整数，n=0表示输入数据的结束，不做处理。 output对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。每个测试实例占一行。sampleinput3 3 -4 24 0 1 2 -30sampleoutput-4 3 2-3 2 1 03、查找最大元素description对于输入的每个字符串，查找其中的最大字母，在该字母后面插入字符串“(max)”。input输入数据包括多个测试实例，每个实例由一行长度不超过100的字符串组成，字符串仅由大小写字母构成。output对于每个测试实例输出一行字符串，输出的结果是插入字符串“(max)”后的结果，如果存在多个最大的字母，就在每一个最大字母后面都插入(max)。sampleinputabcdefgfedcbaxxxxxsampleoutputabcdefg(max)fedcbax(max)x(max)x(max)x(max)x(max)4、数值统计description统计给定的n个数中，负数、零和正数的个数。input输入数据有多组，每组占一行，每行的第一个数是整数n（n100），表示需要统计的数值的个数，然后是n个实数；如果n=0，则表示输入结束，该行不做处理。output对于每组输入数据，输出一行a,b和c，分别表示给定的数据中负数、零和正数的个数。sampleinput6 0 1 2 3 -1 05 1 2 3 4 0.50 sampleoutput1 2 30 0 55、手机短号description大家都知道，手机号是一个11位长的数字串，同时，作为学生，还可以申请加入校园网，如果加入成功，你将另外拥有一个短号。假设所有的短号都是是 6+手机号的后5位，比如号码手机，对应的短号就是645678。现在，如果给你一个11位长的手机号码，你能找出对应的短号吗？input输入数据的第一行是一个n(n = 200)，表示有n个数据，接下来的n行每一行为一个11位的手机号码。output输出应包括n行，每行包括一个对应的短号，输出应与输入的顺序一致。sampleinput21351234567813787654321sampleoutput645678654321三、程序运行结果（说明设计思路，解释使用的数据结构，显示代码，计算时间复杂度） 1、 数列有序!l 设计思路：使用一个一维数组存放数列元素，依次比较数列元素与插入数字的大小，直到找到第一个比插入数字大的元素，记录其所在的位置标号k，将要插入的数字插入第k个位置即可。l 数据结构：用一维数组保存给定的有序数列。l 本程序主要耗费的时间是用在寻找插入位置k的单层循环中，因此时间复杂度为o(n)。l 代码如下：#include using namespace std;int main()int data101;/data数组用来存放输入的数列int n,m;int i,k;cinnm;while(n!=0 & m!=0)for(i=0;idatai;for(i=0;i=m)k=i;break;for(i=n;i=k;i-)datai=datai-1;/插入位置之后的数列顺序后移一位datak=m;/将m插入for(i=0;in;i+)/保存结果 coutdatai” ”; coutdatannm;/输入下一组n和mreturn 0;2、绝对值排序3、查找最大元素4、数值统计5、手机短号 任课教师签名： 2014年 月 日实 验 报 告 （ 2 ）学号： 姓名： 班级： 成绩：实验名称：递归与分治算法实验地点：所使用的工具软件及环境：win7, visual c+/java 一、实验目的：通过上机实验，要求掌握递归与分治法算法的问题描述、算法设计思想、程序设计和算法复杂性分析等。 二、实验内容描述：（在该章题目库中选择题目，填写题目内容及输入输出要求）三、程序运行结果（说明设计思路，解释使用的数据结构，显示代码，计算时间复杂度） 任课教师签名： 2014年 月 日实 验 报 告 （ 3 ）学号： 姓名： 班级： 成绩：实验名称：动态规划实验地点：所使用的工具软件及环境：win7, visual c+/java 一、实验目的：理解动态规划法的设计思想，分析是否满足最优子结构性质，刻画其结构特征，递归地定义最优值（动态规划方程），以自底向上的方式计算出最优值，构造最优解。掌握动态规划的算法框架和设计策略。 二、实验内容描述：（在该章题目库中选择题目，填写题目内容及输入输出要求）三、程序运行结果（说明设计思路，解释使用的数据结构，显示代码，计算时间复杂度） 任课教师签名： 2014年 月 日实 验 报 告 （ 4 ）学号： 姓名： 班级： 成绩：实验名称：贪心算法实验地点：所使用的工具软件及环境：win7, visual c+/java 一、实验目的：理解贪心算法的设计思想，掌握贪心算法的算法框架和设计策略，选取度量标准，逐步构造最优解。 二、实验内容描述：（在该章题目库中选择题目，填写题目内容及输入输出要求）三、程序运行结果（说明设计思路，解释使用的数据结构，显示代码，计算时间复杂度） 任课教师签名： 2014年 月 日实 验 报 告 （ 5 ）学号： 姓名： 班级： 成绩：实验名称：回溯法实验地点：所使用的工具软件及环境：win7, visual c+/java 一、实验目的：理解回溯法的设计思想，回溯法是一个既带有系统性又带有跳跃性的搜索算法。掌握从包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树的过程。掌握回溯法的算法框架和设计策略。 二、实验内容描述：（在该章题目库中选择题目，填写题目内容及输入输出要求）三、程序运行结果（说明设计思路，解释使用的数据结构，显示代码，计算时间复杂度） 任课教师签名： 2014年 月 日实 验 报 告 （ 6 ）学号： 姓名： 班级： 成绩：实验名称：分支限界法实验地点：所使用的工具软件