算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

算法設(shè)計(jì)與分析

實(shí)驗(yàn)報(bào)告

學(xué)院信息科學(xué)與技術(shù)學(xué)院

專業(yè)班級(jí)軟件工程3班

學(xué)號(hào)_______20122668__________

姓名_______王建君____________

指導(dǎo)教師尹治本___________

2014年10月

實(shí)驗(yàn)一同時(shí)求最大元與次大元

一、問(wèn)題提出

在N個(gè)元素中同時(shí)求出最大元與次大元。

二、求解思路

利用分治法解決問(wèn)題。將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)

題互相獨(dú)立且與原問(wèn)題相同。遞歸地解這些子問(wèn)題，然后將各個(gè)子問(wèn)題解合并得到原問(wèn)題的

解。

三、算法復(fù)雜度

當(dāng)n=l時(shí)，不需要比較就可知最大元和次大元均為該數(shù)本身。當(dāng)n=2時(shí)，一次比較就

可以找出兩個(gè)元素的最大元和次大元。當(dāng)n>2時(shí)，可以把n個(gè)數(shù)據(jù)元素分為大致相等的兩

半，一半有n/2個(gè)數(shù)據(jù)元素，而另一半有n/2個(gè)數(shù)據(jù)元素。先分別找出各自組中的最大元和

最小元，然后將兩個(gè)最大元進(jìn)行比較，就可得n個(gè)元素的最大元；將兩個(gè)最小元中的大元

與兩個(gè)最大元中的小元進(jìn)行比較，就可得n個(gè)元素的次大元。在規(guī)模為n的數(shù)據(jù)元素集合中

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

算法復(fù)雜度T(%)=5〃/2-4=O(n)o

四、源代碼

#include<stdio.h>

#include<stdlib.h>

#defineN10〃宏定義元素的個(gè)數(shù)

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("請(qǐng)輸入％d個(gè)數(shù)字:\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;

)

五、結(jié)果分析

運(yùn)算結(jié)果截圖如下

S3軟件3班王建君20122668

請(qǐng)輸入10個(gè)數(shù)字：

12349687432342

尾木元力87

次大兀為43

Pressanykeytocontinue

依次輸入10個(gè)數(shù)字12、3、4、9、6、87、34、23、4、2后求得最大元為87,次大元為34。

實(shí)驗(yàn)二實(shí)現(xiàn)兩個(gè)大整數(shù)的乘法

一、問(wèn)題提出

實(shí)現(xiàn)兩個(gè)大整數(shù)的乘法。

二、求解思路

利用分治法解決問(wèn)題。將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)

題互相獨(dú)立且與原問(wèn)題相同。遞歸地解這些子問(wèn)題，然后將各個(gè)子問(wèn)題解合并得到原問(wèn)題的

解。

三、算法復(fù)雜度

設(shè)X和Y都是n位的二進(jìn)制整數(shù)，現(xiàn)在要計(jì)算它們的乘積XY,我們將n位的二進(jìn)制整

數(shù)X和Y各分為2段，每段的長(zhǎng)為n/2位(為簡(jiǎn)單起見(jiàn)，假設(shè)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位整數(shù)的乘法(AC,BD和

(A-B)(D-C)),6次加、減法和2次移位，由此可得算法復(fù)雜度為：

,、。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類型轉(zhuǎn)換成int類型

intstring_to_num(stringk)

(

intback;

stringstreaminstr(k);

instr?back;

returnback;

)

//整形數(shù)轉(zhuǎn)換為string類型

stringnum_to_string(intintValue)

(

stringresult;

stringstreamstream;

stream?intValue;

stream?result;

returnresult;

)

〃在字符串str前添加s個(gè)零

stringstringBeforeZero(stringstr,ints)

(

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

(

str.insert(O,"On);

)

returnstr;

}

//兩個(gè)大整數(shù)字符串相加，超出計(jì)算機(jī)表示范圍的數(shù)也能實(shí)現(xiàn)相加(本函數(shù)可以實(shí)現(xiàn)大整數(shù)

加法運(yùn)算)

stringstringAddstring(stringstri,stringstr2)

(

〃假定strl和str2是相等的長(zhǎng)度，不相等時(shí)在前面自動(dòng)補(bǔ)零，使兩個(gè)字符串長(zhǎng)度相等

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;〃前一進(jìn)位是否有標(biāo)志,0代表無(wú)進(jìn)位，1代表有進(jìn)位

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

(

intc=(strl[i]-'0')+(str2[i]-'0')+flag;//利用ASCII碼對(duì)字符進(jìn)行運(yùn)算，這里加上flag

代表的是:當(dāng)前一位有進(jìn)位時(shí)加1,無(wú)進(jìn)位時(shí)加0

flag=c/10;〃c大于10時(shí)，flag置為1,否則為0

c%=10;//c大于10時(shí)取模，否則為其本身

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

)

if(0!=flag)〃最后一為(最高位)判斷，如果有進(jìn)位則再添一位

(

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

)

returnresult;

)

/*兩個(gè)大整數(shù)字符串相減，超出計(jì)算機(jī)表示范圍的數(shù)也能實(shí)現(xiàn)相減(在這里比較特殊，第一

個(gè)參數(shù)一定大于第二個(gè)參數(shù)，

因?yàn)椋篴l*b0+a0*bl=(al+a0)*(bl+b0)-(al*bl+a0*b0)>0,所以(al+a0)*(bl+b0)>

(al*bl+a0*b0)

這個(gè)函數(shù)的兩個(gè)參數(shù)，第一個(gè)代表的其實(shí)就是(al+a0)*(bl+b0),第二個(gè)代表的其實(shí)就是

(al*bl+a0*b0)

所以本函數(shù)里不用考慮最終得到結(jié)果為負(fù)數(shù)的情況，至于計(jì)算有關(guān)大整數(shù)負(fù)數(shù)相乘的問(wèn)題可

以通過(guò)其他途徑判斷

*/

stringstringSubtractstring(stringstri,stringstr2)

(

〃對(duì)傳進(jìn)來(lái)的兩個(gè)數(shù)進(jìn)行修剪，如果前面幾位有0則先去掉，便于統(tǒng)一處理

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);

)

〃使兩個(gè)字符串長(zhǎng)度相等

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碼進(jìn)行各位減法運(yùn)算

if(c<0)〃當(dāng)不夠減時(shí)向前一位借位，前一位也不夠位時(shí)再向前一位借位，依次如下

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字符串最前端插入新生成的單個(gè)字符

)

returnresult;

)

〃在字符串str后跟隨s個(gè)零

stringstringFollowZero(strings)

(

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

{

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

)

returnstr;

)

〃分治法大整數(shù)乘法實(shí)現(xiàn)函數(shù)

stringIntMult(stringx,stringy)〃遞歸函數(shù)

(

//對(duì)傳進(jìn)來(lái)的第一個(gè)數(shù)進(jìn)行修剪，如果前面幾位有0則先去掉，便于統(tǒng)一處理

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

{

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

)

//對(duì)傳進(jìn)來(lái)的第二個(gè)數(shù)進(jìn)行修剪，如果前面幾位有0則先去掉，便于統(tǒng)一處理

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

{

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

)

/*這里的f變量代表在兩個(gè)數(shù)據(jù)字符串長(zhǎng)度不想等或者不是2的指數(shù)倍的情況下，所要統(tǒng)一

的長(zhǎng)度，這樣做是為了讓數(shù)據(jù)長(zhǎng)度為2的n次方

的情況下便于利用分治法處理

*/

intf=4;

/*當(dāng)兩字符串中有任意一個(gè)字符串長(zhǎng)度大于2時(shí)都要通過(guò)與上面定義的f值進(jìn)行比較，使其

達(dá)到數(shù)據(jù)長(zhǎng)度為2的n次方，實(shí)現(xiàn)方式是在前面

補(bǔ)0,這樣可以保證數(shù)據(jù)值大小不變

*/

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

if(x.sizeQ>=y.size。)//第一個(gè)數(shù)長(zhǎng)度大于等于第二個(gè)數(shù)長(zhǎng)度的情況

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

(

f*=2;

)

if(x.size()!=f)

(

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

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

)

)

else//第二個(gè)數(shù)長(zhǎng)度大于第一個(gè)數(shù)長(zhǎng)度的情況

(

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。)//數(shù)據(jù)長(zhǎng)度為1時(shí),在前面補(bǔ)一個(gè)0(這里之所以會(huì)出現(xiàn)長(zhǎng)度為1的數(shù)據(jù)

是因?yàn)榍懊鎸?duì)數(shù)據(jù)修剪過(guò))

x=stringBeforeZero(x,1);

)

if(l==y.size())//數(shù)據(jù)長(zhǎng)度為1時(shí),在前面補(bǔ)一個(gè)0(這里之所以會(huì)出現(xiàn)長(zhǎng)度為1的數(shù)據(jù)

是因?yàn)榍懊鎸?duì)數(shù)據(jù)修剪過(guò))

y=stringBeforeZero(y,l);

}

if(x.sizeQ>y.size。)//最后一次對(duì)數(shù)據(jù)校正，確保兩個(gè)數(shù)據(jù)長(zhǎng)度統(tǒng)一

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

)

if(x.size()<y.size。)//最后一次對(duì)數(shù)據(jù)校正，確保兩個(gè)數(shù)據(jù)長(zhǎng)度統(tǒng)一

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)//長(zhǎng)度為2時(shí)代表著遞歸的結(jié)束條件

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{〃長(zhǎng)度不為2時(shí)利用分治法進(jìn)行遞歸運(yùn)算

小提示：

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分治法實(shí)現(xiàn)大整數(shù)乘法)

cout<<”請(qǐng)輸入第一個(gè)大整數(shù)(任意長(zhǎng)度):"；

cin?numl;

inti=0;

〃判斷第一個(gè)輸入的數(shù)據(jù)是否合法，當(dāng)字符串中包含非數(shù)字字符時(shí)提示用戶重

新輸入

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

(

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

(

cout<<"您輸入的數(shù)據(jù)不合法，請(qǐng)輸入有效的整數(shù)!”<<endl;

cin?numl;

i=-l；

)

)

cout<<"請(qǐng)輸入第二個(gè)大整數(shù)(任意長(zhǎng)度):“；

cin?num2;

〃判斷第二個(gè)輸入的數(shù)據(jù)是否合法，當(dāng)字符串中包含非數(shù)字字符時(shí)提示用戶重

新輸入

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

(

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

(

cout<〈"