算法设计与分析报告1

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

1、学生学号0121510880508实验课成绩学生实验报告书实验课程名称算法设计与分析B实验开课学院计算机科学与技术学院指导教师姓名学生姓名丁小兵学生专业班级软件学术15022015--2016学年第2学期1实验项目名称分治法的应用报告成绩实验者丁小兵专业班级软件学术1502组别同组者完成日期2017年5月10日第一部分：实验分析与设计（可加页）一、实验目的和要求1.目的（1）基本掌握分治算法的原理。（2）掌握递归算法及递归程序的设计。（3）能用程序设计语言求解相关问题。2.要求（1）用分治法求解问题；（2）分析算法的时间

2、性能，设计实验程序验证分析结论。二、分析与设计1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1

3、;//p£m

4、数。«数据输入由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示每个数组有n个数。接下来的两行分别是X，Y数组的元素。«结果输出程序运行结束时，将计算出的中位数输出到文件output.txt中。输入文件示例输出文件示例input.txtoutput.txt3515183142114三、主要仪器设备及耗材1．安装了Windows10操作系统的PC机1台2．PC机系统上安装了MicrosoftVisualStudio2013开发环境11第二部分：实验过程和结果（可加页）四、代码调试说明（

5、调试手段、过程及结果分析）调试主要内容为编写程序的语法正确性与否，程序逻辑的正确性与否。F5：启动调试；F11：逐语句调试；F12：逐过程调试；F9：切换断点；ctrl+B：新建断点等。代码：#include#includeusingnamespacestd;intmidNum(inta[],intn){if(n%2==0){return(a[n/2]+a[n/2-1])/2;}elsereturna[n/2];}intmax(inta,intb){if(a>=b){returna;

6、}else{returnb;}}intmin(inta,intb){if(a<=b){returna;}else{returnb;}}intgetmidNum(inta[],intb[],intn){intm1,m2;if(n<=0)return-1;if(n==1)return(a[0]+b[0])/2;if(n==2)return(max(a[0],b[0])+min(a[1],b[1]))/2;m1=midNum(a,n);m2=midNum(b,n);if(m1==m2){returnm1;}if(m1

7、if(n%2==0){returngetmidNum(a+n/2-1,b,n/2+1);}11else{returngetmidNum(a+n/2,b,n/2+1);}}else{if(n%2==0){returngetmidNum(b+n/2-1,a,n/2+1);}else{returngetmidNum(b+n/2,a,n/2+1);}}}intmain(){/*ofstreamoo("file1.txt",ios::out);if(!oo){cout<<"Error";system("pause");return

8、1;}oo<<11;oo.close();*/ifstreamii("file1.txt",ios::in);if(!ii){cout<<"wrong";system("pause");return1;}inti;ii>>i;//cout<