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

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

2、lude *include using namespace std; /string類型轉(zhuǎn)換成int類型int string_to_num(string k)/string字符串變整數(shù)型例如str=1234，轉(zhuǎn)換為整數(shù)的1234. int back; stringstream instr(k); instrback; return back; /整形數(shù)轉(zhuǎn)換為string類型string num_to_string(int intValue)string result;stringstream stream;stream result;/從stream中抽取前面放入的int值return res

3、ult;/在字符串str前添加s個(gè)零string stringBeforeZero(string str,int s)for(int i=0;i str2.size() str2 = stringBeforeZero(str2,str1.size() - str2.size();else if (str1.size() =0;i-)int c = (str1i - 0) + (str2i - 0) + flag;/利用ASCII碼對(duì)字符進(jìn)展運(yùn)算,這里加上flag代表的是:當(dāng)前一位有進(jìn)位時(shí)加1，無進(jìn)位時(shí)加0flag = c/10;/c大于10時(shí)，flag置為1，否則為0c %= 10;/c大于1

4、0時(shí)取模，否則為其本身result.insert(0,num_to_string(c);/在result字符串最前端插入新生成的單個(gè)字符if (0 != flag) /最后一為(最高位)判斷，如果有進(jìn)位則再添一位result.insert(0,num_to_string(flag); return result;/*兩個(gè)大整數(shù)字符串相減，超出計(jì)算機(jī)表示圍的數(shù)也能實(shí)現(xiàn)相減(在這里比擬特殊，第一個(gè)參數(shù)一定大于第二個(gè)參數(shù),因?yàn)椋篴1*b0+a0*b1=(a1+a0)*(b1+b0)-(a1*b1+a0*b0) 0 ,所以(a1+a0)*(b1+b0) (a1*b1+a0*b0)這個(gè)函數(shù)的兩個(gè)參數(shù)，第

5、一個(gè)代表的其實(shí)就是(a1+a0)*(b1+b0)，第二個(gè)代表的其實(shí)就是(a1*b1+a0*b0)所以本函數(shù)里不用考慮最終得到結(jié)果為負(fù)數(shù)的情況，至于計(jì)算有關(guān)大整數(shù)負(fù)數(shù)相乘的問題可以通過其他途徑判斷*/string stringSubtractstring(string str1,string str2)/對(duì)傳進(jìn)來的兩個(gè)數(shù)進(jìn)展修剪，如果前面幾位有0則先去掉，便于統(tǒng)一處理while (0 = str10&str1.size()1)str1=str1.substr(1,str1.size()-1);while (0 = str20&str2.size()1)str2=str2.substr(1,str

6、2.size()-1);/使兩個(gè)字符串長(zhǎng)度相等if (str1.size() str2.size() str2 = stringBeforeZero(str2,str1.size() - str2.size(); string result;for(int i=str1.size()-1;i=0;i-)int c = (str1i - 0) - (str2i - 0);/利用ASCII碼進(jìn)展各位減法運(yùn)算if (c 0) /當(dāng)不夠減時(shí)向前一位借位，前一位也不夠位時(shí)再向前一位借位，依次如下c +=10;int prePos = i-1; char preChar = str1prePos;whil

7、e (0 = preChar) str1prePos=9;prePos -= 1;preChar = str1prePos;str1prePos-=1;result.insert(0,num_to_string(c);/在result字符串最前端插入新生成的單個(gè)字符return result;/在字符串str后跟隨s個(gè)零string stringFollowZero(string str,int s)for(int i=0;i1)*=*.substr(1,*.size()-1);/對(duì)傳進(jìn)來的第二個(gè)數(shù)進(jìn)展修剪，如果前面幾位有0則先去掉，便于統(tǒng)一處理while (0 = y0&y.size()1)

8、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次方 的情況下便于利用分治法處理*/int f=4;/*當(dāng)兩字符串中有任意一個(gè)字符串長(zhǎng)度大于2時(shí)都要通過與上面定義的f值進(jìn)展比擬，使其到達(dá)數(shù)據(jù)長(zhǎng)度為2的n次方，實(shí)現(xiàn)方式是在前面 補(bǔ)0，這樣可以保證數(shù)據(jù)值大小不變*/if (*.size()2 | y.size()2) if (*.size() = y.size() /第一個(gè)數(shù)長(zhǎng)度大于等于第二個(gè)數(shù)長(zhǎng)度的情況while (*.size()f) /判斷f值f*=2;if (*.siz

9、e() != f) * = stringBeforeZero(*,f-*.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) * = stringBeforeZero(*,f-*.size();y = stringBeforeZero(y,f-y.size();if (1 = *.size() /數(shù)據(jù)長(zhǎng)度為1時(shí),在前面補(bǔ)一個(gè)0(這里之所以會(huì)出現(xiàn)長(zhǎng)度為1的數(shù)據(jù)是因?yàn)榍懊鎸?duì)數(shù)據(jù)修剪過)*=stringBeforeZero(*,1);

10、if (1 = y.size() /數(shù)據(jù)長(zhǎng)度為1時(shí),在前面補(bǔ)一個(gè)0(這里之所以會(huì)出現(xiàn)長(zhǎng)度為1的數(shù)據(jù)是因?yàn)榍懊鎸?duì)數(shù)據(jù)修剪過)y=stringBeforeZero(y,1);if (*.size() y.size() /最后一次對(duì)數(shù)據(jù)校正，確保兩個(gè)數(shù)據(jù)長(zhǎng)度統(tǒng)一y = stringBeforeZero(y,*.size()-y.size();if (*.size() 1) a1 = *.substr(0,s/2); a0 = *.substr(s/2,s-1); b1 = y.substr(0,s/2); b0 = y.substr(s/2,s-1); string result; if( s =

11、2) /長(zhǎng)度為2時(shí)代表著遞歸的完畢條件 int na = string_to_num(a1); int nb = string_to_num(a0); int nc = string_to_num(b1); int nd = string_to_num(b0); result = num_to_string(na*10+nb) * (nc*10+nd); else /長(zhǎng)度不為2時(shí)利用分治法進(jìn)展遞歸運(yùn)算/*小提示:c = a*b = c2*(10n) + c1*(10(n/2) + c0;a = a1a0 = a1*(10(n/2) + a0;b = b1b0 = b1*(10(n/2) + b

12、0;c2 = a1*b1; c0 = a0*b0;c1 = (a1 + a0)*(b1 + b0)-(c2 + c0);*/string c2 = IntMult(a1,b1);/ (a1 * b1)string c0 = IntMult(a0,b0);/ (a0 * b0) string c1_1 = stringAddstring(a1,a0);/ (a1 + a0) string c1_2 = stringAddstring(b1,b0);/ (b1 + b0) string c1_3 = IntMult(c1_1,c1_2);/ (a1 + a0)*(b1 + b0) string c

13、1_4 = stringAddstring(c2,c0);/ (c2 + c0) string c1=stringSubtractstring(c1_3,c1_4);/ (a1 + a0)*(b1 + b0)-(c2 + c0)string s1=stringFollowZero(c1,s/2);/ c1*(10(n/2) string s2=stringFollowZero(c2,s);/ c2*(10n) result = stringAddstring(stringAddstring(s2,s1),c0);/ c2*(10n) + c1*(10(n/2) + c0 return resu

14、lt; int main() int f=1;while (1 = f)string A,B,C,D; string num1,num2; string r;system(title 3109005933 09計(jì)科02班 黃進(jìn)杰 分治法大整數(shù)乘法);system(color 0a);cout大整數(shù)乘法運(yùn)算(分治法實(shí)現(xiàn))endl;coutnum1;int i=0;/判斷第一個(gè)輸入的數(shù)據(jù)是否合法,當(dāng)字符串中包含非數(shù)字字符時(shí)提示用戶重新輸入for(i=0 ;i num1.size();i+)if (num1i9) cout您輸入的數(shù)據(jù)不合法,請(qǐng)輸入有效的整數(shù)!num1;i=-1;coutnum2;/判斷第二個(gè)輸入的數(shù)據(jù)是否合法,當(dāng)字符串中包含非數(shù)字字符時(shí)提示用戶重新輸入for(i=0 ;i num2.size();i+)if (num2i9) cout您輸入的數(shù)據(jù)不合法,請(qǐng)輸入有效的整數(shù)!num2;i=-1;r=IntMu