算法设计与分析报告1

1、学生学号0121510880508实验课成绩学生实验报告书实验课程名称开课学院指导教师姓名学生姓名学生专业班级算法设计与分析限验计算机科学与技术学院丁小兵软件学术15022021-2021学年第2学期实验工程名称分治法的应用报告成绩1实验者丁小兵专业班级软件学术1502组别1同组者完成日期2021年5月10日,1第一局部：实验分析与设计(可加页)一、实验目的和要求1 .目的(1) 根本掌握分治算法的原理.(2) 掌握递归算法及递归程序的设计.(3) 能用程序设计语言求解相关问题.2 .要求(1) 用分治法求解问题；(2) 分析算法的时间性能,设计实验程序验证分析结论.二、分析与设计1 .了解用

2、分治法求解的问题：当要求解一个输入规模为n,且n的取值相当大的问题时,如果问题可以分成k个不同子集合,得到k个不同的可独立求解的子问题,其中1<k<n,而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出.那末,对于这类问题分治法是十分有效的.2 .掌握分治法的一般限制流程.DanC(p,q)globaln,A1:n;integerm,p,q;/1<pq<nifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);/p_m<qreturnCombine(DanC(p,m),DanC(m+1,q);endifendDa

3、nC3 .实验内容仔细阅读备选实验的题目,设计序要的程满足正确性,代码中有关键的注释,书写格式清楚,简洁易懂,效率较高,利用C+的模板,设计的程序通用性好,适合各种合理输入,并能对不合理输入做出正确的提示.中位数问题问题描述设X0:n-1和丫0:n-1为两个数组,每个数组中含有n个已排好序的数.找出期口丫白2n个数的中位数.编程任务利用分治策略试设计一个O(logn)时间的算法求出这2n个数的中位数.数据输入由文件input.txt提供输入数据.文件的第1行中有1个正整数n(n<=200),表示每个数组有n个数.接下来的两行分别是X,丫数组的元素.结果输出程序运行结束时,将计算出的中位数

4、输出到文件output.txt中.输入文件例如input.txt3输出文件例如output.txt145151831421三、主要仪器设备及耗材1 .安装了Windows10操作系统的PC机1台2 .PC机系统上安装了MicrosoftVisualStudio2021开发环境第二局部：实验过程和结果可加页四、代码调试说明调试手段、过程及结果分析调试主要内容为编写程序的语法正确性与否,程序逻辑的正确性与否.F5:启动调试；F11:逐语句调试；F12:逐过程调试；F9:切换断点;ctrl+B:新建断点等.代码：#include<iostream>#include<fstream&

5、gt;usingnamespacestd;intmidNum(inta口,intn)if(n%2=0)return(an/2+an/2-1)/2;)elsereturnan/2;)intmax(inta,intb)if(a>=b)intmin(inta,intb)intgetmidNum(inta口,intb口,intn)intm1,m2;if(n<=0)return-1;if(n=1)return(a0+b0)/2;if(n=2)return(max(a0,b0)+min(a1,b1)/2;m1=midNum(a,n);m2=midNum(b,n);if(m1=m2)|_retu

6、rnm1;)if(m1<m2)if(n%2=0)returngetmidNum(a+n/2-1,b,n/2+1);else(returngetmidNum(a+n/2,b,n/2+1);)else(if(n%2=0)returngetmidNum(b+n/2-1,a,n/2+1);)elsereturngetmidNum(b+n/2,a,n/2+1);intmain()/*ofstreamoo("file1.txt",ios:out);if(!oo)cout<<"Error"system("pause");retur

7、n1;)oo<<11;oo.close();*/ifstreamii("file1.txt",ios:in);if(!ii)cout<<"wrong"system("pause");return1;inti;ii>>i;/cout<<i;inta10;intb10;ints=0;for(s=0;s<i;s+)ii>>as;一|)for(s=0;s<i;s+)ii>>bs;|)ii.close();/cout<<b2;intresult=ge

8、tmidNum(a,b,i);cout<<result<<endl;ofstreamoo("file2.txt",ios:out);if(!oo)(cout<<"Error"system("pause");return1;oo<<result;oo.close();system("pause");return0;运行截图:输入截图:输出截图：.Ad的.trtumfifrCm第三局部：实验小结、收获与体会这次实验主要是利用分治法来寻求中位数.通过这次的实验,让我充分学习

9、了分治法以及其相关知识点,给我提供了一个动手操作的时机,并且为了能够实现这个目的而努力.当然,不否认这次的实验也是相当有难度的,毕竟感觉工作量挺大的,而且也确实有不少自己不明白的地方.对于这次的实验来说,我通过努力了解了什么是分治法,而且,也懂得了如何利用代码实现分治法.总而言之,这次我收获确实很大.实验工程名称动态规划算法报告成绩11实验者丁小兵专业班级软件学术1502组别1同组者完成日期2021年5月10日,1实验目的和要求1 .实验目的(1) 能用程序设计语言实现求解相关问题的算法；(2) 深刻掌握动态规划法的设计思想并能熟练运用；(3) 理解这样一个观点：同样的问题可以用不同的方法解决

10、,一个好的算法是反复努力和重新修正的结果.2 .实验要求(1) 用动态规划法求解问题；分析算法的时间性能,设计实验程序验证分析结论3 .实验内容(1)仔细阅读备选实验的题目,选择一个(可选多个)作为此次实验题目,设计的程序要满足正确性,代码中有关键的注释,书写格式清楚,简洁易懂,效率较高,利用C+的模板,设计的程序通用性好,适合各种合理输入,并能对不合理输入做出正确的提示.(2) 从以下题目中任选其一完成.1. 最大踩积问题问题描述设I是一个n位十进制整数.如果将I划分为k段,那么可得到k个整数.这k个整数的乘积称为I的一个k乘积.试设计一个算法,对于给定的I和k,求出I的最大k乘积.例如十进

11、制整数1234划分为3段可有如下情形：1 X2X34=682 X23X4=9212 X3X4=144编程任务对于给定的I和k,编程计算I的最大k乘积.数据输入输入的第1行中有2个正整数n和k.正整数n是序列的长度；正整数k是分割的段数.接下来的一行中是一个n位十进制整数.(n<=10)结果输出计算出的最大k乘积.输入文件例如输出文件例如input.txt32output.txt623124.分析设计理解最优子结构的问题.有一类问题的活动过程可以分成假设干个阶段,而且在任一阶段后的行为依赖于该阶段的状态,与该阶段之前的过程如何到达这种状态的方式无关.这类问题的解决是多阶段的决策过程.在50

12、年代,贝尔曼RichardBellman等人提出了解决这类问题的“最优化原理,从而创立了最优化问题的一种新的算法设计方法-动态规划.对于一个多阶段过程问题,是否可以分段实现最优决策,依赖于该问题是否有最优子结构性质,能否采用动态规划的方法,还要看该问题的子问题是否具有重叠性质.最优子结构性质：原问题的最优解包含了其子问题的最优解.子问题重叠性质：每次产生的子问题并不总是新问题,有些子问题被反复计算屡次.问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个根本要素.（1） 理解分段决策Bellman方程.每一点最优都是上一点最优加上这段长度.即当前最优只与上一步有关.Us=0,Uj丁平打

13、WiBUs初始值,Uj第J段的最优值.（2） 一般方法1找出最优解的性质,并刻画其结构特征；2递归地定义最优值写出动态规划方程；3以自底向上的方式计算出最优值；4根据计算最优值时得到的信息,构造一个最优解.步骤1-3是动态规划算法的根本步骤.在只需要求出最优值的情形,步骤4可以省略,步骤3中记录的信息也较少；假设需要求出问题的一个最优解,那么必须执行步骤4,步骤3中记录的信息必须足够多以便构造最优解.三、主要仪器设备及耗材1 .安装了Windows10操作系统的PC机1台2 .PC机系统上安装了MicrosoftVisualStudio2021开发环境第二局部：实验过程和结果可加页四、代码调试

14、说明调试手段、过程及结果分析调试主要内容为编写程序的语法正确性与否,程序逻辑的正确性与否.F5:启动调试；F11:逐语句调试；F12:逐过程调试；F9:切换断点；ctrl+B:新建断点等.代码：#include<iostream>#include<fstream>#include<math.h>usingnamespacestd;inta101;/给定的n个数字intm101101;/目标数组,储存最优解intw101101;intn,k;intmax(inta,intb);voidmaxdp()inttemp,_max;/*动态转移方程的求解过程|if(j

15、=1)m(i,j)=w(1,i);前i位(1:i)数字分j组乘积的最大值等于分为j-1组的结果再乘以一个因子if(j>=1&&j<=i)m(i,j)=maxm(d,j-1)*m(d+1,i)|其中：1<=d<i(即从1开始一直到i-1中找最大值)elseif(i<j)m(i,j)=0;、*/如果分成1段|for(inti=1;i<=n;i+)mi1=w1i;for(inti=1;i<=n;i+)for(intj=2;j<=k;j+)_max=0;for(intd=1;d<i;d+)mij=max(mdj-1*wd+1i,mi

16、j);if(mdj-1*wd+1i)>_max)_max=mdj-1*wd+1i;/cout<<mdj-1<<"*"<<wd+1i<<"="<<_max<<endl;mij=_max;intmax(inta,intb)if(a>b)returna;)elsereturnb;intmain()(system("pause");ifstreami1("input.txt",ios:in);if(!i1)(cout<<&quo

17、t;Error"Isystem("pause");return1;)intnum;i1>>n>>k>>num;inty=n;for(intx=1;x<=n;x+)(y=y-1;ax=num/(pow(10,y);num=num-ax*(pow(10,y);)/wij表示从第i位到第j位所组成的十进制数for(inti=1;i<=n;i+)(wii=ai;for(intj=i+1;j<=n;j+)wij=wij-1*10+aj;/每次乘以10再加上个位数)maxdp();ofstreamo1("output.txt",ios:out);if(!o1)(cout<<"ERRORsystem("pause");return1;)o1<<mnk;o1.close();cout<<mnk<<endl;/fprintf(fp2,"%I64d",mnk);/cout<<mnk<<endl;system("pause");return0;运行截图：*飞崂一网莺磔讣£刖*0*治|)1聃触1g/IEft爷讲庶内.输入截图：