算法Basic--高精度

Posted on Edited on In Views:

高精度—-基础算法篇2

791. 高精度加法

题:https://www.acwing.com/problem/content/793/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> add(vector<int> &a, vector<int> &b)
{
    int t = 0;
    vector<int> res;
    for(int i = 0; i < a.size() || i < b.size(); i++)
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        res.push_back(t % 10);
        t /= 10;
    }
    if (t) res.push_back(t);
    reverse(res.begin(), res.end());
    return res;
}
int main()
{
    string a, b; cin >> a >> b;
    vector<int> avec, bvec;
    for (int i = a.size() -1; i >= 0; i--) avec.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) bvec.push_back(b[i] - '0');
    vector<int> res = add(avec, bvec);
    for(auto num : res) cout << num;
    
}

AcWing 792. 高精度减法

题：https://www.acwing.com/problem/content/description/794/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 判断是否 A>=B
bool comp(vector<int> &A, vector<int> &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;
}


vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> res;
    int t = 0;
    for(int i=0; i < A.size(); i++)
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        res.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while(res.size() > 1 && res.back() == 0) res.pop_back(); // 去掉前导0
    reverse(res.begin(), res.end());
    return res;
}

int main()
{
    string a, b; cin >> a >> b;
    vector<int> avec,  bvec;
    for(int i=a.size() -1; i >=0; i--)  avec.push_back(a[i] - '0');
    for(int i=b.size() -1; i >=0; i--)  bvec.push_back(b[i] - '0');

    if(comp(avec, bvec)) //判断是否a - b >= 0；
    {
        auto res = sub(avec, bvec);
        for(auto i=0; i < res.size(); i++) printf("%d", res[i]);
    }
    else
    {
        printf("-");
        auto res = sub(bvec, avec);
        for(auto i=0; i < res.size(); i++) printf("%d", res[i]);
    }
}

793. 高精度乘法

https://www.acwing.com/problem/content/795/

  • 解析：高精乘低精的版本：演算方式是每一个数全乘上低精整数，然后进位记录。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> mul(vector<int> &a, int b)
{
    int t = 0;
    vector<int> res;
    for(int i = 0; i < a.size() || t; i++)
    {
        if (i < a.size()) t += a[i] * b;
        res.push_back(t % 10);
        t /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main()
{
    string a; cin >> a;
    int b; cin >> b;
    
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    auto res = mul(A, b);
    for(auto c : res) cout << c;
}

高精度*高精度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> A, vector<int> B)
{
    vector<int> C(A.size() + B.size());
    
    //每一位对另一个数的每一个做乘积之后，错位相加
    for (int i = 0; i < A.size(); i ++ )
        for (int j = 0; j < B.size(); j ++ )
            C[i + j] += A[i] * B[j];

    for (int i = 0, t = 0; i < C.size() || t; i ++ )
    {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && !C.back()) C.pop_back();

    return C;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    auto C = mul(A, B);

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;

    return 0;
}

高精度除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> div(vector<int> &a, int b, int &r)
{
    vector<int> c;
    for(int i = 0; i < a.size(); i++)
    {
        r = r * 10 + a[i];
        c.push_back(r / b);
        r = r % b;
    }
    while(c.size() > 1 && (*c.begin()) == 0) c.erase(c.begin());
    return c;
}

int main ()
{
    string a; cin >> a;
    int b; cin >> b;
    vector<int> A;
    for(int i = 0; i < a.size(); i++)  A.push_back(a[i] - '0');

    int r = 0;
    vector<int> res = div(A, b, r);
    for(auto i : res) cout << i;
    cout << endl;
    cout << r;
    return 0;
}
'gitalk-container'); }, window.Gitalk);