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

1、精彩文檔算法設(shè)計與分析基礎(chǔ)實驗報告實驗名稱分治法求大整數(shù)乘法學(xué)院專業(yè)班級計算機(jī)科學(xué)與技術(shù)09(2)班學(xué)號3109005933姓名黃進(jìn)杰指導(dǎo)教師顧國生2012年12月03日一、實驗?zāi)康耐ㄟ^上機(jī)實驗，要求掌握分治法算法的問題描述、算法設(shè)計思想、程序設(shè)計和算法復(fù)雜性分析等。二、實驗環(huán)境C-Free三、實驗內(nèi)容問題的描述通過分治法求兩個大整數(shù)的乘法算法設(shè)計思想將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各個子問題解合并得到原問題的解。程序設(shè)計#include#include#include#includeusingnamespacestd

2、;/string類型轉(zhuǎn)換成nt類型intstring_to_num(stringk)/str字符串變整數(shù)型例如tr二1234轉(zhuǎn)換為整數(shù)的234.intback;stringstreaminstr(k);instrback;returnback;/整形數(shù)轉(zhuǎn)換為tring類型stringnum_to_string(intintValue)stringresult;stringstreamstream;streamresult;/從stream中抽取前面放入的nt值returnresult;/在字符串str前添加s個零stringstringBeforeZero(stringstr,ints)for

3、(inti=0;istr2.size()str2=stringBeforeZero(str2,str1.size()-str2.size();elseif(str1.size()=0;i-)intc二(str1i-0)+(str2i-0)+利用gSCII碼對字符進(jìn)行運(yùn)算這里加上flag代表的是當(dāng)前一位有進(jìn)位時加無進(jìn)位時力0flag二c/10;/大于10時，flag置為1,否則為0c%=10；/大于10時取模，否則為其本身result.insert(0,num_to_string(c)在/)sult字符串最前端插入新生成的單個字符if(0!二flag)/最/后一為(最高位)判斷，如果有進(jìn)位則再添

4、一位result.insert(0,num_to_string(flag);returnresult;/*兩個大整數(shù)字符串相減超，出計算機(jī)表示范圍的數(shù)也能實現(xiàn)相(在減這里比較特殊第，一個參數(shù)一定大于第二個參數(shù),因為：a1*b0+a0*b1=(a1+a0)*(b1+b0)-(a1*b1+a0*b0)所以(a1+a0)*(b1+b0)(a1*b1+a0*b0)這個函數(shù)的兩個參數(shù)，一個代表的其實就是1+a0)*(b1+bQ)第二個代表的其實就是1*b1+a0*b0)所以本函數(shù)里不用考慮最終得到結(jié)果為負(fù)數(shù)的情況，至于計算有關(guān)大整數(shù)負(fù)數(shù)相乘的問題可以通過其他途徑判斷*/stringstringSubtr

5、actstring(stringstr1,stringstr2)/對傳進(jìn)來的兩個數(shù)進(jìn)行修剪，如果前面幾位0則有先去掉，便于統(tǒng)一處理while(0二二str10&str1.size()1)str1=str1.substr(1,str1.size()T);while(0=str20&str2.size()1)str2=str2.substr(1,str2.size()-1);/使兩個字符串長度相等if(str1.size()str2.size()str2=stringBeforeZero(str2,str1.size()-str2.size();stringresult;for(inti=str1

6、.size()-1;i=0;i-)intc二(str1i-0)-(str2i-0利用ASCII碼進(jìn)行各位減法運(yùn)算if(c0)/當(dāng)/不夠減時向前一位借位，前一位也不夠位時再向前一位借位，依次如下c+二10;intprePos二i-1;charpreChar二str1prePos;while(0二二preChar)str1prePos二9;prePos-二1;preChar二str1prePos;str1prePos-=1;result.insert(0,num_to_string(c)在/esult字符串最前端插入新生成的單個字符returnresult;/在字符串str后跟隨s個零string

7、stringFollowZero(stringstr,ints)for(inti=0;i1)x=x.substr(1,x.size()-1);/對傳進(jìn)來的第二個數(shù)進(jìn)行修剪，如果前面幾0位則有先去掉，便于統(tǒng)一處理while(0=y0&y.size()1)y=y.substr(1,y.size()-1);/*這里的f變量代表在兩個數(shù)據(jù)字符串長度不想等或者不的指數(shù)倍的情況下，所要統(tǒng)一的長度,這樣做是為了讓數(shù)據(jù)長度2為勺n次方的情況下便于利用分治法處理*/intf=4;/*當(dāng)兩字符串中有任意一個字符串長度大于都要通過與上面定義的直進(jìn)行比較，使其達(dá)到數(shù)據(jù)長度為2的n次方，實現(xiàn)方式是在前面補(bǔ)0，這樣可以保

8、證數(shù)據(jù)直大小不變*/if(x.size()2|y.size()2)if(x.size()=y.size()|/一個數(shù)長度大于等于第二個數(shù)長度的情況while(x.size()f)判/斷f值f*=2;if(x.size()!=f)x=stringBeforeZero(x,f-x.size();y=stringBeforeZero(y,f-y.size();else/第二個數(shù)長度大于第一個數(shù)長度的情況while(y.size()f)判/斷f值f*=2;if(y.size()!=f)x=stringBeforeZero(x,f-x.size();y=stringBeforeZero(y,f-y.si

9、ze();if(1=x.size()數(shù)/據(jù)長度為1時,在前面補(bǔ)一個0(這里之所以會出現(xiàn)長度為1的數(shù)據(jù)是因為前面對數(shù)據(jù)修剪過)x=stringBeforeZero(x,1);if(1=y.size()數(shù)/據(jù)長度為1時,在前面補(bǔ)一個0(這里之所以會出現(xiàn)長度為1的數(shù)據(jù)是因為前面對數(shù)據(jù)修剪過)y=stringBeforeZero(y,1);if(x.size()y.size()最/后一次對數(shù)據(jù)校正，確保兩個數(shù)據(jù)長度統(tǒng)一y=stringBeforeZero(y,x.size()-y.size();if(x.size()1)a1=x.substr(0,s/2);a0=x.substr(s/2,s-1);b

10、1=y.substr(0,s/2);b0=y.substr(s/2,s-1);stringresult;if(s=2)/長/度為2時代表著遞歸的結(jié)束條件intna=string_to_num(a1);intnb=string_to_num(a0);intnc=string_to_num(b1);intnd=string_to_num(b0);result=num_to_string(na*10+nb)*(nc*10+nd);else/長/度不為2時利用分治法進(jìn)行遞歸運(yùn)算小提示:c二a*b二c2*(10l)+c1*(10八(n/2)+cO;a二alaO二a1*(10八(n/2)+aO;b二blb

11、O二b1*(10八(n/2)+bO；c2二a1*b1;c0二a0*b0;c1二(a1+a0)*(b1+b0)-(c2+c0);stringc2=IntMult(a1,b1);/(a1*b1)stringc0=IntMult(a0,b0);/(a0*b0)stringc1_1=stringAddstring(a1,a0);/(a1+a0)stringc1_2=stringAddstring(b1,b0);/(b1+b0)stringc1_3=IntMult(c1_1,c1_2);/(a1+a0)*(b1+b0)stringc1_4=stringAddstring(c2,c0);/(c2+c0)s

12、tringc1=stringSubtractstring(c1_3,c1_4);/(a1+a0)*(b1+b0)-(c2+c0)strings仁stringFollowZero(c1,s/2)；/c1*(10入(n/2)strings2=stringFollowZero(c2,s);/c2*(10八n)result二stringAddstring(stringAddstring(s2,s1),c0);/c2*(10八n)+c1*(10入(n/2)+c0returnresult;intmain()intf=1;while(1=f)stringA,B,C,D;stringnum1,num2;str

13、ingr;system(title3109005933計09科02班黃進(jìn)杰分治法大整數(shù)乘法);system(color0a);cout大整數(shù)乘法運(yùn)算分治法實現(xiàn)endl;coutnum1;inti=0;/判斷第一個輸入的數(shù)據(jù)是否合,當(dāng)法字符串中包含非數(shù)字字符時提示用戶重新輸入for(i=0;inum1.size();i+)if(num1i9)cout您輸入的數(shù)據(jù)不合，請輸入有效的整tnum1;i=-1;coutnum2;/判斷第二個輸入的數(shù)據(jù)是否合,當(dāng)字符串中包含非數(shù)字字符時提示用戶重新輸入for(i=0;inum2.size();i+)if(num2i9)cout您輸入的數(shù)據(jù)不合7請輸入有效的整tnum2;i=-1;r=IntMult(num1,num2)