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

《《算法设计与分析》实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、华东理工大学（计12）算法设计与分析实验报告（1）学号：X姓名：何意班级：计131成绩：实验名称：算法概述实验地点：所使用的工具软件及环境：Win7,VisualC++/Java一、实验目的：熟悉数据结构和基本的排序和搜索算法，熟悉编程语言的集成开发环境，掌握程序设计与实现的能力，分析算法的复杂度。二、实验内容描述：（在该章题目库中选择5个题目，填写题目内容及输入输出要求。）1、数列有序!Description有n(n<=100)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请将该数插入到序列中，并使新的序列仍然有序。Input输入数据包含多个测试实例，每组

2、数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0标示输入数据的结束，本行不做处理。Output对于每个测试实例，输出插入新的元素后的数列。SampleInput33 124 00SampleOutput12342、绝对值排序Description输入n(n<=100)个整数，按照绝对值从大到小排序后输出。题目保证对于每一个测试实例，所有的数的绝对值都不相等。Input输入数据有多组，每组占一行，每行的第一个数字为n,接着是n个整数，n=0表示输入数据的结束，不做处理。Output对于每个测试实例，输出排序后的结果，两个数之间用一个空格隔开。

3、每个测试实例占一行。SampleInput33-42 4012-3 0SampleOutput15华东理工大学（计12）算法设计与分析-432 -32103、查找最大元素Description对于输入的每个字符串，查找其中的最大字母，在该字母后面插入字符串“(max)”。Input输入数据包括多个测试实例，每个实例由一行长度不超过100的字符串组成，字符串仅由大小写字母构成。Output对于每个测试实例输出一行字符串，输出的结果是插入字符串“(max)”后的结果，如果存在多个最大的字母，就在每一个最大字母后面都插入"(max)"。SampleInputabcdefgfe

4、dcba xxxxxSampleOutputabcdefg(max)fedcba x(max)x(max)x(max)x(max)x(max)4、数值统计Description统计给定的n个数中，负数、零和正数的个数。Input输入数据有多组，每组占一行，每行的第一个数是整数n（n<100），表示需要统计的数值的个数，然后是n个实数；如果n=0，则表示输入结束，该行不做处理。Output对于每组输入数据，输出一行a,b和c，分别表示给定的数据中负数、零和正数的个数。SampleInput60123-10 512340.5 0SampleOutput123 0055、手机

5、短号Description大家都知道，手机号是一个11位长的数字串，同时，作为学生，还可以申请加入校园网，如果加入成功，你将另外拥有一个短号。假设所有的短号都是是6+手机号的后5位，比如号码为的手机，对应的短号就是。现在，如果给你一个11位长的手机号码，你能找出对应的短号吗？Input输入数据的第一行是一个N(N<=200)，表示有N个数据，接下来的N行每一行为一个11位的手机号码。15华东理工大学（计12）算法设计与分析Output输出应包括N行，每行包括一个对应的短号，输出应与输入的顺序一致。SampleInput2 SampleOutput 三、程序运行结果（说

6、明设计思路，解释使用的数据结构，显示代码，计算时间复杂度）1、数列有序!l设计思路：使用一个一维数组存放数列元素，依次比较数列元素与插入数字的大小，直到找到第一个比插入数字大的元素，记录其所在的位置标号K，将要插入的数字插入第K个位置即可。l数据结构：用一维数组保存给定的有序数列。l本程序主要耗费的时间是用在寻找插入位置K的单层循环中，因此时间复杂度为O(n)。l代码如下：#includeusingnamespacestd;intmain(){intdata[101];//data数组用来存放输入的数列intn,m;inti,k;cin>>n>>m;

7、while(n!=0&&m!=0){for(i=0;i>data[i];for(i=0;i=m){k=i;break;}for(i=n;i>=k;i--)data[i]=data[i-1];//插入位置之后的数列顺序后移一位data[k]=m;//将m插入for(i=0;i>n>>m;//输入下一组n和m}