算法设计与分析实验报告

算法设计与分析

实验报告

学院信息科学与技术学院

专业班级软件工程3班

学号_______20122668__________

姓名_______王建君____________

指导教师尹治本___________

2014年10月

实验一同时求最大元与次大元

一、问题提出

在N个元素中同时求出最大元与次大元。

二、求解思路

利用分治法解决问题。将一个规模为n的问题分解为k个规模较小的子问题，这些子问

题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题解合并得到原问题的

解。

三、算法复杂度

当n=l时，不需要比较就可知最大元和次大元均为该数本身。当n=2时，一次比较就

可以找出两个元素的最大元和次大元。当n>2时，可以把n个数据元素分为大致相等的两

半，一半有n/2个数据元素，而另一半有n/2个数据元素。先分别找出各自组中的最大元和

最小元，然后将两个最大元进行比较，就可得n个元素的最大元；将两个最小元中的大元

与两个最大元中的小元进行比较，就可得n个元素的次大元。在规模为n的数据元素集合中

找出最大元和次大元，至少需要5n/2-4次比较，即5n/2-4是找最大次大元算法的下界，得

算法复杂度T(%)=5〃/2-4=O(n)o

四、源代码

#include<stdio.h>

#include<stdlib.h>

#defineN10〃宏定义元素的个数

intmax(inta,intb)

(

if(a>b)

returna;

else

returnb;

}

intmin(inta,intb)

(

if(a<b)

returna;

else

returnb;

)

voidSearch(inta[],int*max0,int*secondO,intn)

intg[30];

inti,m;

intmax1,max2,second1,second2;

if(n==l)

(

*max0=a[0];

*second0=a[0];

)

elseif(n==2)

(

*max0=max(a[0],a[1]);

*second0=min(a[0],a[1]);

)

else

(

m=n/2;

fbr(i=0;i<m;i++)

g[i]=a[i]；

Search(g,&max1,&second1,m);

fbr(i=O;i<n-m;i++)

g[i]=a[i+m];

Search(g,&max2,&second2,n-m);

*maxO=max(max1,max2);

*secondO=max(min(max1,max2),max(second1,second2));

)

)

intmain()

(

inta[N];

inti,max,second;

system(ntitle软件3班王建君20122668分治法求最大元与次大元)

printf("请输入％d个数字:\n”,N);

for(i=0;i<N;i++)

scanf(H%dH,&a[i]);

Search(a,&max,&second,N);

printf("最大元为％d\n次大元为％小!1”,max,second);

return0;

)

五、结果分析

运算结果截图如下

S3软件3班王建君20122668

请输入10个数字：

12349687432342

尾木元力87

次大兀为43

Pressanykeytocontinue

依次输入10个数字12、3、4、9、6、87、34、23、4、2后求得最大元为87,次大元为34。

实验二实现两个大整数的乘法

一、问题提出

实现两个大整数的乘法。

二、求解思路

利用分治法解决问题。将一个规模为n的问题分解为k个规模较小的子问题，这些子问

题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题解合并得到原问题的

解。

三、算法复杂度

设X和Y都是n位的二进制整数，现在要计算它们的乘积XY,我们将n位的二进制整

数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的塞)，如下图所示：

X=AB,Y=CD

n/2位勿/2位n/2位n/2位

由此，X=A2n/2+B,Y=C2n/2+D,这样，X和Y的乘积可表示为：

XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD。它仅需做3次n/2位整数的乘法(AC,BD和

(A-B)(D-C)),6次加、减法和2次移位，由此可得算法复杂度为：

,、。n=1

T(n)=

3T(n/2)+cnn>1

用解递归方程的套用法可得其解为：T(n)=。(〃l°g23)=O(“'9)。

四、源代码

#include<iostream>

#include<sstream>

#include<string>

#include<stdlib.h>

usingnamespacestd;

//string类型转换成int类型

intstring_to_num(stringk)

(

intback;

stringstreaminstr(k);

instr»back;

returnback;

)

//整形数转换为string类型

stringnum_to_string(intintValue)

(

stringresult;

stringstreamstream;

stream«intValue;

stream»result;

returnresult;

)

〃在字符串str前添加s个零

stringstringBeforeZero(stringstr,ints)

(

for(inti=O;i<s;i++)

(

str.insert(O,"On);

)

returnstr;

}

//两个大整数字符串相加，超出计算机表示范围的数也能实现相加(本函数可以实现大整数

加法运算)

stringstringAddstring(stringstri,stringstr2)

(

〃假定strl和str2是相等的长度，不相等时在前面自动补零，使两个字符串长度相等

if(strl.size()>str2.size())

(

str2=stringBeforeZero(str2,str1.size()-str2.size());

)

elseif(strl.size()<str2.size())

(

strl=stringBeforeZero(str1,str2.size()-strl.size());

)

stringresult;

intflag=O;〃前一进位是否有标志,0代表无进位，1代表有进位

for(inti=strl,size()-l;i>=0;i—)

(

intc=(strl[i]-'0')+(str2[i]-'0')+flag;//利用ASCII码对字符进行运算，这里加上flag

代表的是:当前一位有进位时加1,无进位时加0

flag=c/10;〃c大于10时，flag置为1,否则为0

c%=10;//c大于10时取模，否则为其本身

result.insert(0,num_to_string(c));〃在result字符串最前端插入新生成的单个字符

)

if(0!=flag)〃最后一为(最高位)判断，如果有进位则再添一位

(

result.insert(0,num_to_string(flag));

)

returnresult;

)

/*两个大整数字符串相减，超出计算机表示范围的数也能实现相减(在这里比较特殊，第一

个参数一定大于第二个参数，

因为：al*b0+a0*bl=(al+a0)*(bl+b0)-(al*bl+a0*b0)>0,所以(al+a0)*(bl+b0)>

(al*bl+a0*b0)

这个函数的两个参数，第一个代表的其实就是(al+a0)*(bl+b0),第二个代表的其实就是

(al*bl+a0*b0)

所以本函数里不用考虑最终得到结果为负数的情况，至于计算有关大整数负数相乘的问题可

以通过其他途径判断

*/

stringstringSubtractstring(stringstri,stringstr2)

(

〃对传进来的两个数进行修剪，如果前面几位有0则先去掉，便于统一处理

while('O'==strl[O]&&strl.size()>l)

(

strl=strl.substr(l,strl.size()-l);

)

while(O==str2[0]&&str2.size()>l)

(

str2=str2.substr(l,str2.size()-l);

)

〃使两个字符串长度相等

if(strl.size()>str2.size())

(

str2=stringBeforeZero(str2,str1.size()-str2.size());

)

stringresult;

for(inti=strl.size()-l;i>=O;i—)

(

intc=(strl[i]-'0')-(str2[i]-O);〃利用ASCII码进行各位减法运算

if(c<0)〃当不够减时向前一位借位，前一位也不够位时再向前一位借位，依次如下

c+=10;

intprePos=i-1;

charpreChar=str1[prePos];

while('O'==preChar)

(

strl[prePos]=,9,;

prePos-=1;

preChar=strl[prePos];

)

strl[prePos]-=1;

)

result.insert(0,num_to_string(c));〃在result字符串最前端插入新生成的单个字符

)

returnresult;

)

〃在字符串str后跟随s个零

stringstringFollowZero(strings)

(

for(inti=0;i<s;i++)

{

str.insert(str.size(),"O");

)

returnstr;

)

〃分治法大整数乘法实现函数

stringIntMult(stringx,stringy)〃递归函数

(

//对传进来的第一个数进行修剪，如果前面几位有0则先去掉，便于统一处理

while('O'==x[0]&&x.size()>1)

{

x=x.substr(1,x.size()-1);

)

//对传进来的第二个数进行修剪，如果前面几位有0则先去掉，便于统一处理

while(O==y[0]&&y.size()>l)

{

y=y.substr(1,y.size()-1);

)

/*这里的f变量代表在两个数据字符串长度不想等或者不是2的指数倍的情况下，所要统一

的长度，这样做是为了让数据长度为2的n次方

的情况下便于利用分治法处理

*/

intf=4;

/*当两字符串中有任意一个字符串长度大于2时都要通过与上面定义的f值进行比较，使其

达到数据长度为2的n次方，实现方式是在前面

补0,这样可以保证数据值大小不变

*/

if(x.size()>2||y.size()>2)

if(x.sizeQ>=y.size。)//第一个数长度大于等于第二个数长度的情况

while(x.size()>f)〃判断f值

(

f*=2;

)

if(x.size()!=f)

(

x=stringBeforeZero(x,f-x.size());

y=stringBeforeZero(y,f-y.size());

)

)

else//第二个数长度大于第一个数长度的情况

(

while(y.size()>f)〃判断f值

(

f*=2;

)

if(y.size()!=f)

x=stringBeforeZero(x,f-x.size());

y=stringBeforeZero(y,f-y.size());

if(l==x.size。)//数据长度为1时,在前面补一个0(这里之所以会出现长度为1的数据

是因为前面对数据修剪过)

x=stringBeforeZero(x,1);

)

if(l==y.size())//数据长度为1时,在前面补一个0(这里之所以会出现长度为1的数据

是因为前面对数据修剪过)

y=stringBeforeZero(y,l);

}

if(x.sizeQ>y.size。)//最后一次对数据校正，确保两个数据长度统一

y=stringBeforeZero(y,x.size()-y.size());

)

if(x.size()<y.size。)//最后一次对数据校正，确保两个数据长度统一

x=stringBeforeZero(x,y.size()-x.size());

)

ints=x.size();

stringal,aO,bl,bO;

if(s>1)

al=x.substr(0,s/2);

aO=x.substr(s/2,s-l);

bl=y.substr(0,s/2);

bO=y.substr(s/2,s-l);

)

stringresult;

if(s==2)//长度为2时代表着递归的结束条件

intna=string_to_num(a1);

intnb=string_to_num(aO);

intnc=string_to_num(b1);

intnd=string_to_num(bO);

result=num_to_string((na*10+nb)*(nc*10+nd));

}

else{〃长度不为2时利用分治法进行递归运算

小提示：

c=a*b=c2*(10An)+cl*(10A(n/2))+cO;

a=alaO=al*(10A(n/2))+aO;

b=blbO=bl*(10A(n/2))+bO;

c2=al*bl;cO=aO*bO;

cl=(al+aO)*(bl+b0)-(c2+cO);

stringc2=IntMult(al,bl);//(al*bl)

stringcO=IntMult(aO,bO);//(aO*bO)

stringcl_l=stringAddstring(al,aO);//(al+aO)

stringcl_2=stringAddstring(bl,bO);//(bl+bO)

stringcl_3=IntMult(c1_1,c1_2);//(al+aO)*(bl+bO)

stringcl_4=stringAddstring(c2,c0);//(c2+cO)

stringc1=stringSubtractstring(c1_3,c1_4);//(al+aO)*(bl+b0)-(c2+cO)

strings1=stringFollowZero(c1,s/2);//cl*(10A(n/2))

strings2=stringFollowZero(c2,s);//c2*(10An)

result=stringAddstring(stringAddstring(s2,s1),cO);//c2*(10An)+cl*(10A(n/2))+cO

)

returnresult;

)

intmain()

(

intf=l;

stringA,B,C,D;

stringnuml,num2;

stringr;

system(ntitle软件3班王建君20122668分治法实现大整数乘法)

cout<<”请输入第一个大整数(任意长度):"；

cin»numl;

inti=0;

〃判断第一个输入的数据是否合法，当字符串中包含非数字字符时提示用户重

新输入

for(i=0;i<numl.size();i++)

(

if(numl[i]<'0'||numl[i]>'9')

(

cout<<"您输入的数据不合法，请输入有效的整数!”<<endl;

cin»numl;

i=-l；

)

)

cout<<"请输入第二个大整数(任意长度):“；

cin»num2;

〃判断第二个输入的数据是否合法，当字符串中包含非数字字符时提示用户重

新输入

for(i=0;i<num2.size();i++)

(

if(num2[i]<'0'||num2[i]>,9,)

(

cout<〈"