您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“如何實(shí)現(xiàn)大整數(shù)乘法運(yùn)算與分治算法”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“如何實(shí)現(xiàn)大整數(shù)乘法運(yùn)算與分治算法”吧!
普通乘數(shù)運(yùn)算
對于乘數(shù)運(yùn)算有一種比較簡單較為容易理解的方法,我們可以利用小學(xué)時(shí)期學(xué)的列豎式的計(jì)算方法進(jìn)行乘法運(yùn)算。
列豎式乘法運(yùn)算
參考上圖中的列豎式計(jì)算方法,我們進(jìn)行代碼實(shí)現(xiàn)。
#include <iostream> #include <string> #include <stdlib.h> #include <vector> #include <cstring> #include <algorithm> std::string multiply(std::string a, std::string b) { std::string result = ""; int row = b.size(); int col = a.size() + 1; int tmp[row][col]; memset(tmp,0, sizeof(int)*row*col); reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); for(int i = 0; i < b.size(); i++) { for(int j = 0; j < a.size(); j++) { std::string bit_a = std::string(1, a.at(j)); std::string bit_b = std::string(1, b.at(i)); tmp[i][j] += std::stoi(bit_a) * std::stoi(bit_b); tmp[i][j+1] = tmp[i][j] / 10; tmp[i][j] %= 10; } } int N = a.size() + b.size(); int sum[N]; memset(sum, 0, sizeof(int)*N); for(int n = 0; n < N; n++) { int i = 0; int j = n; while (i <= n && j >= 0 ) { if(i < row && j < col) { sum[n] += tmp[i][j]; } i++; j--; } if( n+1 < N ) { sum[n+1] = sum[n] / 10; sum[n] %= 10; } } bool zeroStartFlag = true; for (int i = N-1; i >= 0; i--) { if(sum[i]==0 && zeroStartFlag) { continue; } zeroStartFlag = false; result.append(std::to_string(sum[i])); } return result; } int main() { std::string a = "3456"; std::string b = "1234"; std::string result = multiply(a, b); std::cout << a << " * " << b << " = " << result <<std::endl; return 0; }
為了方便我們先將各個(gè)乘數(shù)做了翻轉(zhuǎn)處理,最后需要再將結(jié)果翻轉(zhuǎn)回來。在運(yùn)算過程中用來存放乘法運(yùn)算結(jié)果的數(shù)組,我們沒有進(jìn)行移位處理同列相加,而是對角線相加,這樣可以減少空間和運(yùn)算步驟。上面的代碼運(yùn)行結(jié)果如下所示。
運(yùn)行結(jié)果
因?yàn)樽址拈L度沒有特別的限制,所以上面的算法可以適用大整數(shù)運(yùn)算。
分治算法
雖然上面的列豎式的方法可以很好的解決大整數(shù)乘法的問題,但是我們還用一種更加高效的方法可以選擇,這就是分治(Divide and Conquer)算法。它是一種非常重要的算法,可以應(yīng)用到很多領(lǐng)域,比如快速排序,二分搜索等。從算法的名字我們可以看出它是將大的問題拆分進(jìn)行細(xì)化,由大變小,先將小的問題解決,最終將這個(gè)問題解決,所以叫Divide and Conquer。在這里我們可以通過這種方法將大整數(shù)進(jìn)行拆分,拆分成一個(gè)個(gè)可以通過程序語言直接進(jìn)行運(yùn)算的小整進(jìn)行計(jì)算,最后求得到大整數(shù)的值。
假設(shè)有兩個(gè)大整數(shù),我們設(shè)為a(大小為n位)和b(大小為m位),這里我們將使用二分法對數(shù)據(jù)進(jìn)行拆分,這兩個(gè)整數(shù)我們可以分解為:
則,
令,
根據(jù)上面公式里,我們可以將a*b分解為四個(gè)小的整數(shù)的乘法,即z3,z2,z1,z0四個(gè)表達(dá)式。如果分解出來的乘法數(shù)值還是很大,還可以按照同樣的方法進(jìn)行拆解直到拆解成較小的數(shù)值乘法,直到計(jì)算機(jī)程序語言可以直接運(yùn)算。
比如,上面的3456和1234相乘,參考下圖通過二分法逐級對整數(shù)進(jìn)行拆分,我們將兩個(gè)整數(shù)拆分到一位整數(shù)進(jìn)行運(yùn)算。
3456和1234拆分步驟圖
下面我們看一下分治算法的代碼實(shí)現(xiàn),這里我們使用遞歸的方法。
#include <iostream> #include <string> #include <stdlib.h> #include <vector> #include <cstring> #include <algorithm> #include <cmath> std::string add(std::string a, std::string b) { int N = std::max(a.size(), b.size()); int sum[N]; memset(sum, 0, sizeof(int)*N); reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); for(int i = 0; i< N; i++) { int bit_a = 0; int bit_b = 0; if(i < a.size()) bit_a = std::stoi(std::string(1, a.at(i))); if(i < b.size()) bit_b = std::stoi(std::string(1, b.at(i))); sum[i] += (bit_a + bit_b); if(i < N-1 && sum[i]>9) { sum[i+1] = sum[i] / 10; sum[i] %=10; } } std::string result=""; bool zeroStartFlag = true; for (int i = N-1; i >= 0; i--) { if(sum[i]==0 && zeroStartFlag) { continue; } zeroStartFlag = false; result.append(std::to_string(sum[i])); } return result; } std::string divideAndConquer(std::string a, std::string b) { if( a.size() < 2 && b.size() < 2) { return std::to_string(std::stoi(a) * std::stoi(b)); } int n = a.size(); int m = b.size(); int halfN = n/2; int halfM = m/2; std::string a0 = "0"; std::string a1 = "0"; if(a.size() > halfN && halfN > 0) { a1 = a.substr(0, halfN); a0 = a.substr(halfN, a.size() - halfN); } else { a1 = "0"; a0 = a; } std::string b0 = "0"; std::string b1 = "0"; if(b.size() > halfM && halfM > 0) { b1 = b.substr(0, halfM); b0 = b.substr(halfM, b.size() - halfM); } else { b1 = "0"; b0 = b; } std::string a1b1 = divideAndConquer(a1, b1); std::string a0b0 = divideAndConquer(a0, b0); std::string a1b0 = divideAndConquer(a1, b0); std::string a0b1 = divideAndConquer(a0, b1); a1b1.append((n - halfN) + (m - halfM), '0'); a1b0.append(n - halfN, '0'); a0b1.append(m - halfM, '0'); std::string result = ""; result = add(a1b1, a1b0); result = add(result, a0b1); result = add(result, a0b0); return result; } int main() { std::string a = "3456"; std::string b = "1234"; std::cout << a << " * " << b << " = " << divideAndConquer(a, b) << std::endl; return 0; }
程序的運(yùn)行結(jié)果如下:
分治算法運(yùn)行結(jié)果
到此,相信大家對“如何實(shí)現(xiàn)大整數(shù)乘法運(yùn)算與分治算法”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。