高精度算法

• 前言
• 大數(shù)加法
• • 不可以處理負數(shù)的模板
  • 可以處理負數(shù)
• 大數(shù)減法
• • 兩個數(shù)都是整數(shù)，且相減結(jié)果大于0
  • 兩個數(shù)都是正整數(shù)，相減結(jié)果可以是負數(shù)
  • 兩個數(shù)均可以是負數(shù)
• 高精度乘法
• • 兩個數(shù)均可以是負數(shù)
• 大數(shù)除法
• • 兩個數(shù)均可以是負數(shù)
• 大數(shù)取模

前言

不得不說csdn上面的文章是越來越亂了，搞的想罵人的那種。本文在這里聲明，這是一篇模板的博客，如果向更深入的了解（會提及一些）可以去參考別的文章。沒一個模板都經(jīng)過博主簡化和模塊化已達到易寫的目的。

大數(shù)加法

不可以處理負數(shù)的模板

// C = A + B, A >= 0, B >= 0 vector<int> add(vector<int> &A, vector<int> &B) {if (A.size() < B.size()) return add(B, A);vector<int> C;int t = 0;for (int i = 0; i < A.size(); i ++ ){t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C; }

可以處理負數(shù)

因為減法就是帶負數(shù)的加法，因此我們在處理負數(shù)的時候一般是對負數(shù)的情況進行討論

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; char a[1000005]; char b[1000005]; int fa, fb; int la, lb;void show(int ed) {if (fa)printf("-");for (int i = ed; i >= fa; --i)printf("%d", a[i]); }// 兩個都為負數(shù)或者兩個都不是負數(shù)的情況 void add() {int i, j, t = 0, s, l;for (i = fa; i < la || i < lb; ++i) {s = a[i] + b[i] + t;t = s / 10;a[i] = s % 10;}a[i] = t ;l = t ? i : i - 1;//t是進位 ，如果最后進位了，這l為i，否則只到i-1show(l); }//比較大小 int cmp() {int la = strlen(a), lb = strlen(b);if (la - fa > lb - fb) // 比較長度return 1;else if (la - fa < lb - fb)return 0;else {// 長度相等則看每一位int i ;for ( i = 0; i < la && a[i + fa] == b[i + fb]; ++i);return a[i + fa] > b[i + fb];} }void minu() {//兩個符號不一樣的話是利用減法int i, j, c = 0, l = -1, s;for (i = 0; i + fa < la; ++i) {s = a[i + fa] - b[i + fb] - c >= 0 ? 0 : 1; //是否需要借位a[i + fa] = (10 + a[i + fa] - b[i + fb] - c) % 10;l = a[i + fa] ? i + fa : l; //判斷末尾位置c = s;}if (l < 0)printf("0");elseshow(l); }int main() {scanf("%s%s", a, b);fa = ('-' == a[0]), fb = ('-' == b[0]);// 我們早兩者如果只有一個負數(shù)的時候，我們讓前一個數(shù)大的原因是這樣我們就可以通過前一個確實整個的符號if ( !cmp())swap(a, b), swap(fa, fb);la = strlen(a), lb = strlen(b);reverse(a + fa, a + la), reverse(b + fb, b + lb); // 易忘int i = fa, j = fb;while (i < la)a[i] -= '0', i ++;while (j < lb)b[j] -= '0', j ++;//j容易寫成iif (fa ^ fb)minu(); // 兩個只有有一個有負號 ，減法elseadd(); // 加法return 0; }

大數(shù)減法

兩個數(shù)都是整數(shù)，且相減結(jié)果大于0

// C = A - B, 滿足A >= B, A >= 0, B >= 0 vector<int> sub(vector<int> &A, vector<int> &B) {vector<int> C;for (int i = 0, t = 0; i < A.size(); i ++ ){t = A[i] - t;if (i < B.size()) t -= B[i];C.push_back((t + 10) % 10);if (t < 0) t = 1;else t = 0;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C; }

兩個數(shù)都是正整數(shù)，相減結(jié)果可以是負數(shù)

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; char a[1000005]; char b[1000005]; int la, lb;//比較大小 int cmp() {int la = strlen(a), lb = strlen(b);if (la > lb ) // 比較長度return 1;else if (la < lb )return 0;else {// 長度相等則看每一位int i = 0;while (i < la && a[i] == b[i])i ++;return a[i] > b[i];} }void minu() {int i, j, t = 0, ed = -1;for (i = 0; i < la || i < lb; ++i) {int s = a[i] - b[i] - t >= 0 ? 0 : 1; //是否需要借位a[i] = (10 + a[i] - b[i] - t) % 10;ed = a[i] ? i : ed; //判斷末尾位置t = s;}if (ed < 0)printf("0");elsefor (int i = ed ; i >= 0 ; --i)printf("%d", a[i]); }int main() {scanf("%s%s", a, b);// 我們早兩者如果只有一個負數(shù)的時候，我們讓前一個數(shù)大的原因是這樣我們就可以通過前一個確實整個的符號if ( !cmp()) {cout << '-';swap(a, b);}la = strlen(a), lb = strlen(b);reverse(a, a + la), reverse(b, b + lb); // 易忘int i = 0, j = 0;while (i < la)a[i] -= '0', i ++;while (j < lb)b[j] -= '0', j ++;//j容易寫成iminu();return 0; }

兩個數(shù)均可以是負數(shù)

#include <iostream> #include <string> #include <algorithm> using namespace std; string a, b, s, t; int fa, fb;void init() {fa = (a[0] == '-'), fb = (b[0] == '-');s = a.substr( 1, a.size() ), t = b.substr( 1, b.size() ); }bool cmp(string a, string b) {int as = a.size(), bs = b.size();if (as > bs || as == bs && a > b)return true;elsereturn false; }void change(string &s, string &t, string a, string b) {int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;for ( int i = 0; i < d; i++ )as > bs ? t += "0" : s += "0";s += a, t += b; // 前邊補上0 }string calcAddition( string a, string b ) {string s = "0", t = "0";//多放的一個0是加法可能會進一位change(s, t, a, b);int len = s.size();for ( int i = len - 1; i >= 1; i-- )s[i] += t[i] - '0';if ( s[i] > '9' ) {s[i] -= 10;s[i - 1]++;}bool j = true;for ( int i = 0; i < len; i++ )if ( s[i] != '0' )j = false;if ( j )return "0";return s[0] == '0' ? s.substr( 1, len ) : s; }string calcSubtraction( string a, string b ) {string s = "", t = "";change(s, t, a, b);if ( s < t )swap(s, t);int len = s.size();for ( int i = len - 1; i >= 0; i-- ) {if ( s[i] < t[i] ) {s[i] += 10;if ( s[i - 1] >= '1' )s[i - 1]--;else { // 否則向前邊不是0的借位int j = i - 1;while ( s[j] == '0' )s[j--] += 9;//s[j]--;}}s[i] -= ( t[i] - '0' );}if ( len == 1 )return s;return s[0] == '0' ? calcAddition( s.substr( 1, len ), "0" ) : s; }int main() {cin >> a >> b;init();if ( fa && fb ) {if ( cmp(s, t) )cout << "-";cout << calcSubtraction( s, t ) << endl;} else if ( !fa && !fb ) {if (!cmp(a, b) )cout << "-";cout << calcSubtraction( a, b ) << endl;} else if ( fa )cout << "-" << calcAddition( s, b ) << endl;elsecout << calcAddition( a, t ) << endl;return 0; }

高精度乘法

一個結(jié)論是：兩個相乘的數(shù)，第一個數(shù)的第i為與第二個數(shù)的第j位（從1開始），相乘的結(jié)果是累加到第 結(jié)果的第i + j - 1位上的。

兩個數(shù)均可以是負數(shù)

#include <iostream> #include <cstring> #define T 1000000 using namespace std; char a1[T], b1[T]; int a[T], b[T], c[T], lena, lenb, lenc, x, t, f;void mul() {for (int i = 1; i <= lena; i++) {x = 0;//x是進位for (int j = 1; j <= lenb; j++) {c[i + j - 1] += a[i] * b[j] + x ;x = c[i + j - 1] / 10;c[i + j - 1] %= 10;}c[i + lenb] = x;}lenc = lena + lenb;while (c[lenc] == 0 && lenc > 1)lenc--;if (f == -1)cout << "-";for (int i = lenc; i >= 1; i--)cout << c[i];cout << endl; }int main() {cin >> a1 >> b1 ;lena = strlen(a1), lenb = strlen(b1);f = 1, t = 0;if (a1[0] == '-') //判斷第一個字符是不是負數(shù)，如果是，再判斷另一個是不是，再想輸出問題對于B1字符數(shù)組同理f *= -1, t++;for (int i = t; i <= lena - 1; i++)a[lena - i] = a1[i] - '0'; //除去符號位后，將字符變成數(shù)字，放在對應(yīng)的int數(shù)組里面，進行計算t = 0;if (b1[0] == '-')f *= -1, t++;for (int i = t; i <= lenb - 1; i++)b[lenb - i] = b1[i] - '0';mul();return 0; }

大數(shù)除法

兩個數(shù)均可以是負數(shù)

#include <iostream> #include <string> using namespace std;string fixedNum( string a ) {if ( a.size() == 1 )return a;for ( int i = 0; i < a.size(); i++ )if ( '1' <= a[i] && a[i] <= '9' )return a.substr( i, a.size() );return "0"; }string calcAddition( string a, string b ) {a = fixedNum(a);b = fixedNum(b);int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;string s = "0", t = "0";for ( int i = 0; i < d; i++ )as > bs ? t += "0" : s += "0";s += a;t += b;for ( int i = s.size() - 1; i >= 1; i-- ) {s[i] += t[i] - '0';if ( s[i] > '9' ) {s[i] -= 10;s[i - 1]++;}}return s[0] == '0' ? s.substr( 1, s.size() ) : s; }string calcSubtraction( string a, string b ) {int as = a.size(), bs = b.size(), d = as - bs;string s = "", t = "";for ( int i = 0; i < d; i++ )t += "0";s += a;t += b;for ( int i = s.size() - 1; i >= 0; i-- ) {if ( s[i] < t[i] ) {s[i] += 10;if ( s[i - 1] >= '1' )s[i - 1]--;else {int j = i - 1;while ( s[j] == '0' )s[j--] += 9;s[j]--;}}s[i] -= ( t[i] - '0' );}if ( s.size() == 1 )return s;for ( int i = 0; i < s.size(); i++ ) {if ( '1' <= s[i] && s[i] <= '9' )return s.substr( i, s.size() );}return "0"; }int main() {string a, b, c, sum = "0", cnt = "1";bool j1 = false;cin >> a >> b;if ( a == "0" ) {cout << 0 << endl;return 0;} else if ( a[0] == '-' && b[0] == '-' ) {a = a.substr( 1, a.size() );b = b.substr( 1, b.size() );} else if ( a[0] == '-' ) {j1 = true;a = a.substr( 1, a.size() );} else if ( b[0] == '-' ) {j1 = true;b = b.substr( 1, b.size() );} else;c = b;int as = a.size(), bs = b.size(), cs, d = as - bs;for ( int i = 0; i < d - 1; i++ ) {c += "0";cnt += "0";}cs = c.size();bool j2 = false;while ( c != b ) {while ( as > cs || as == cs && a >= c ) {j2 = true;a = calcSubtraction( a, c );as = a.size();sum = calcAddition( sum, cnt );}c = c.substr( 0, c.size() - 1 );cnt = cnt.substr( 0, cnt.size() - 1 );cs = c.size();}while ( as > bs || as == bs && a >= b ) {j2 = true;a = calcSubtraction( a, b );sum = calcAddition( sum, cnt );as = a.size();}if ( j1 && j2 )cout << '-';cout << sum << endl;return 0; }

大數(shù)取模

#include <iostream> #include <string> using namespace std;string calcAddition( string a, string b ) {int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;string s = "0", t = "0";for ( int i = 0; i < d; i++ )as > bs ? t += "0" : s += "0";s += a;t += b;for ( int i = s.size() - 1; i >= 1; i-- ) {s[i] += t[i] - '0';if ( s[i] > '9' ) {s[i] -= 10;s[i - 1]++;}}bool j = true;for ( int i = 0; i < s.size(); i++ )if ( s[i] != '0' )j = false;if ( j )return "0";return s[0] == '0' ? s.substr( 1, s.size() ) : s; }string calcSubtraction( string a, string b ) {int as = a.size(), bs = b.size(), d = as - bs;string s = "", t = "";for ( int i = 0; i < d; i++ )t += "0";s += a;t += b;for ( int i = s.size() - 1; i >= 0; i-- ) {if ( s[i] < t[i] ) {s[i] += 10;if ( s[i - 1] >= '1' )s[i - 1]--;else {int j = i - 1;while ( s[j] == '0' )s[j--] += 9;s[j]--;}}s[i] -= ( t[i] - '0' );}if ( s.size() == 1 )return s;for ( int i = 0; i < s.size(); i++ ) {if ( '1' <= s[i] && s[i] <= '9' )return s.substr( i, s.size() );}return "0"; }int main() {string a, b, c;cin >> a >> b;c = b;int as = a.size(), bs = b.size(), cs, d = as - bs;for ( int i = 0; i < d - 1; i++ )c += "0";cs = c.size();while ( c != b ) {while ( as > cs || as == cs && a >= c ) {a = calcSubtraction( a, c );as = a.size();}c = c.substr( 0, c.size() - 1 );cs = c.size();}while ( as > bs || as == bs && a >= b ) {a = calcSubtraction( a, b );as = a.size();}cout << a << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的高精度算法（加减乘除取模（均可以处理负数））的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。