算法导论报告

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

1、算法导论软件4班魏仁斌20122712问题一：同时求n个元中的最大元与次大元思路：分冶法i•算法设计：讦(问题不可分){直接求解；返回问题的解；}else{对原问题进行分治；递归对每一个分治的部分求解；归并整个问题，得出全问题的解；}2.算法描述：分治就是“分而治之”的意思，其实质就是将原问题分成n个规模较小而结构与原问题相似的子问题；然后递归地解这些子问题，最后合并其结果就得到原问题的解。当n=2时的分片法又称二分法。分治步骤：(1)分解(Divide)：将原问题分成一系列子问题。(2)解决(Conquer)：递

2、归地解各子问题。若子问题足够小，则可直接求解。(3)合并(combine)；将子问题的结果合并成原问题的解。复杂度：通常算法，设置一个变量，等于需要比较的数纽的第一个元素，然后依次与后面的n-1a行比较，盂要比较ml次得到最大元。源程序代码：#include"iostream.h"#defineN10intmax(inta,intb){return((a>b)?a:b);}intmin(inta,intb){return((a

3、dO,intn){intg[30];inti,m;intmax1,max2,second1,sccond2;if(n==l){*max0=a[0J;*secondO=a[OJ;}elseif(n==2){*max0=max(a[01,a[1]);*second0=min(a[0],a[1]);}else{m=n/2;for(i=0;i

4、cond2,n-m);*maxO=max(max1,max2);*second()=max(min(max1,max2),max(second1,second2));}}voidmain(){cout«"MJ分治法同时求最人元和次大元”；inta[N];inti,max,second;cout«H输入,,«N«,'个数:“；for(i=0;i

5、econd=n«second«"u;}测试结果：用分治凄夙时求最大元和次大元瞄入丄0个数：5412689522678654177输岀结果：iax=95second=78分析：利用递归速度较慢，但是可以把问题简单化。问题二：大整数的乘法思路：分冶递归思想。设X和Y是两个n位的整数，假定n是2的整数次幕。把每个整数分为两部分，每部分为n/2位，则X和Y可垂写为X=xl*10n/2+x0和Y=yl*10n/2+y0,X和Y的乘积可以计算为：X*Y=(xl*10n/2+x0)*(yl*lOn/2+yO)=X*Y*10n

6、+((xl+xO)*(yl+yO)-xl*yl-xO*yO)*10n/2+xO*yO由此体现了分治递归的思想，将大整数化小，规模也变小。复杂S：T(n)=^(nlog3)=0(nL59)源代码：#include#include#include#defineN1()()//最人10()位/*函数声明*/voidcalc1(char*strhintlenlJnt*tmpjntm);voidaccumulate(intcntjnt*res,intres_len,i

7、nt*tmpjnttmpjen);char*bignum_multi(char*strl.intlenl,char*str2,intlen2,char*result,intlen);intmain(){inti,j；/*获取计算数据(可以从文件屮读取)*/charstr1[N]={NULL};charstr2[N]={NULL};charresult[N*N]={NULL);printf(uInputNuml:");scanf(n%s",strl);fflush(stdin);printf(uInputNum2

8、:u);scanf("%s",str2);/*计算两个字符串的长度，及存储结果所需要的空间*/intlcn1=strlcn(str1)Jcn2=strlcn(str2);intlen=lenl+len2;/*计算并输出计算结果*/printf(nTheresultis:%s,bignum_multi(strlJen1,str2,len2,resul