算法设计实验报告一(简单算法设计)

实验报告一课程C++实验名称简单算法设计第1页专业_数学与应用数学___班级__双师一班学号105012011056姓名陈萌实验日期：2013年3月9日报告退发(订正、重做)一、实验目的1.理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程；2.掌握简单问题的算法设计与分析，能设计比较高效的算法；3.熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力。二、实验内容(一)相等元素问题1.问题描述元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？2.具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1767题输入：输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n(n=500)，表示整数序列的长度，第二行给出整数序列，整数之间用一个空格隔开。输出：对于每个测试例输出一行，若该组测试例中存在两个相等的元素则输出”Yes”，否则，输出”No”。每个测试例的输出数据用一行表示。3.测试数据输入：31097125643852531194516263517925324657211234217867533201587327843526457896522237659432133391输出：NoYesNo(二)整数集合分解1.问题描述设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。2.具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1768题输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n(n为偶数，且n=500)，表示原整数集合的长度，第二行给出这n个整数序列，整数之间用一个空格隔开。输出：对于每个测试例输出两行，分别表示新生成的整数集合。其中，第一行是元素和比较小的整数集合，第二行是元素和比较大的整数集合，整数之间用一个空格隔开。两个测试例的输出数据之间用一个空行隔开，最后一个测试例后无空行3.测试数据输入：22268253416237395765721134782961739512043122628348591432475142619245278652377851732972695372输出：234612131617202125293437394351576876789522379142426282932373742474851515259616265737895三、实验步骤1.程序如下：#includestdio.h#defineN500intmain(){inti,j,m,n,t,k=0;inta[N];printf(请输入测试的数的个数:\n);scanf(%d,&m);for(t=0;tm;t++){printf(请输入序列的长度:\n);scanf(%d,&n);printf(请输入序列的数字:\n);for(i=0;in;i++)scanf(%d,&a[i]);for(i=0;in;i++)for(j=i+1;jn;j++)if(a[i]==a[j])k=1;if(k==1)printf(yes\n);elseprintf(NO\n);}return0;}2.程序如下：#includestdio.h#defineN500intmain(){inta[N];intn,k,t,j,i,b,m;printf(请输入示例的个数:\n);scanf(%d,&m);for(b=0;bm;b++){printf(请输入数的个数:\n);scanf(%d,&n);printf(请输入该组数:\n);for(i=0;in;i++)scanf(%d,&a[i]);for(i=0;in;i++){k=i;for(j=i+1;jn;j++)if(a[k]a[j])k=j;if(i!=k){t=a[i];a[i]=a[k];a[k]=t;}}for(i=0;in/2;i++)printf(%3d,a[i]);printf(\n);for(;in;i++)printf(%3d,a[i]);printf(\n);}return0;}四、实验结果与讨论（一）程序运行结果如下：（二）程序运行结果如下：五、总结本次试验不是很难，感觉程序应多上机练习才会有较大提高，在编程过程中较为马虎，因此希望以后自己注意细节，争取做到高效编程。