【藍橋杯C組】備賽基礎篇之高精度演算法

一、高精度加法

思路：

運用vector數組（c選手可用len來記錄數組長度，數組去保存數字）將存入字元串裡面的數字元倒敘保存，按照小學的加法列式，相加保存進位即可。具體參考程式碼。

詳細程式碼解析：

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//數據名稱太長後面又要經常用到它，所以直接給他取個小名，就相當於c中的define
typedef vector<int> vi;
vi add(vi& a, vi& b) {
    vi c;//存結果的數組
    for (int i = 0, t = 0;i < a.size() || i < b.size() || t;i++) {
        //加法就是讓所有的數字加到沒有為止；還有保存進位的要儲存到c中。
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        //每次存儲個位，這也就解釋了為什麼限制條件要加一個t！=0，因為可能兩個數字都加完了，還有進位的數字沒有加進去。
        t /= 10;
    }

    return c;
}

int main() {
    vi a, b, c;
    string str1, str2;
    cin >> str1 >> str2;

    //倒序保存，注意字元與數字之間的轉換。
    for (int i = str1.size() - 1;i >= 0;i--) a.push_back(str1[i] - '0');
    for (int i = str2.size() - 1;i >= 0;i--) b.push_back(str2[i] - '0');

    c = add(a, b);

    //倒序輸出
    for (int i = c.size() - 1;i >= 0;i--) cout << c[i];
    return 0;
}

二、高精度減法

思路：

運用豎式減法，大的減小的，小的減大的需要轉換成大的減小的再天上負號；減不過就向後一個借1。

詳細程式碼解析：

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//數據名稱太長後面又要經常用到它，所以直接給他取個小名，就相當於c中的define
typedef vector<int> vi;

bool cmp(vi& a, vi& b) {
    //比較位數，位數大的數值肯定大。
    if (a.size() != b.size()) return a.size() > b.size();

    //位數相同，從高位往低位比較每個位置的數值。
    for (int i = a.size() - 1;i >= 0;i--)
        if (a[i] != b[i]) return a[i] > b[i];

    return true;
}

void sub(vi& a, vi& b, vi& c) {
    for (int i = 0, t = 0;i < a.size();i++) {
        //a是大的數字，所以以a的位數作為結束
        t += a[i];
        //看看是否需要-1，前方的數值有木有借位。
        if (i < b.size()) t -= b[i];
        //看看是否還有b，有的話就相減
        //沒有的話直接存入位數中。
        c.push_back((t + 10) % 10);
        //加10模10防止a[i]小了，不夠，減成了負號
        if (t < 0) t = -1;
        //t帶了負號，說明借了位，變為-1記錄借了位。
        else t = 0;
        //不是負號，初始化為0，什麼事也沒發生。
    }

    while (c.size() > 1 && !c.back()) c.pop_back();
    //去掉前置零。
}

int main() {
    string str1, str2;
    vi a, b, c;
    cin >> str1 >> str2;

    //倒序保存
    for (int i = str1.size() - 1;i >= 0;i--) a.push_back(str1[i] - '0');
    for (int i = str2.size() - 1;i >= 0;i--) b.push_back(str2[i] - '0');

    if (cmp(a, b)) sub(a, b, c);
    //減不過，就只能添負號，讓b-a。
    else sub(b, a, c), cout << "-";

    //倒序輸出
    for (int i = c.size() - 1;i >= 0;i--) cout << c[i];

    return 0;
}

 

三、高精度乘法

思路：

運用豎式法則的演算法，由於這個演算法是高精度乘以低精度，所以不用一個一個的乘，只需讓高精度中的每一個數乘以整個低精度就行。

詳細程式碼解析：

#include<iostream>
#include<string>
#include<vector>
using namespace std;

typedef vector<int> vi;

vi mul(vi& a, int& b) {
    vi c;
    for (int i = 0, t = 0;i < a.size() || t;i++) {
        if (i < a.size()) t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    //處理前置零
    while (c.size() > 1 && !c.back()) c.pop_back();
    return c;
}

int main() {
    string str;
    int b;
    vi a, c;
    cin >> str >> b;
    //倒序存儲
    for (int i = str.size() - 1;i >= 0;i--) a.push_back(str[i] - '0');

    c = mul(a, b);
    //倒序輸出
    for (int i = c.size() - 1;i >= 0;i--) cout << c[i];
    return 0;
}

 

四、高精度除法

思路：

標準除法運算，適合於     高/低    。

詳細程式碼解析：

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

typedef vector<int> vi;

vi div(vi& a, int& b, int& r) {
    vi c;
    //由於除法是從高位開始計算，所以我們要倒序訪問
    for (int i = a.size() - 1;i >= 0;i--) {
        r = r * 10 + a[i];//餘數乘10+下一位數
        c.push_back(r / b);
        r %= b;//餘數2取模
    }

    //由於倒序訪問，存儲的結果也就是正序的，我們為了將其統一保存格式，所以要將他反過來。
    //統一格式的話便於將四則運算聯合起來用。
    reverse(c.begin(), c.end());
    while (c.size() > 1 && !c.back()) c.pop_back();
    return c;
}

int main() {
    int b, r = 0;
    string str;
    vi a, c;
    cin >> str >> b;
    for (int i = str.size() - 1;i >= 0;i--) a.push_back(str[i] - '0');

    c = div(a, b, r);
    for (int i = c.size() - 1;i >= 0;i--) cout << c[i];
    cout << endl << r << endl;
    return 0;
}

 

 

 

高精度演算法在歷年藍橋杯中出現過，所以要掌握。

Tags:

VirMach 便宜 VPS

QNews

QNews