Xử lý số lớn trong C++

Đỗ Thị Hồng Ngát 13/09/2023
13
Th9

Xử lý số lớn trong C++

1. Khi nào cần xử lý số lớn?

Bài toán 1

Cho hai số nguyên dương \(A\) và \(B\) (A và B có không quá \(1000\) chữ số)

Yêu cầu: Tính \(A + B, A \; – \; B, A * B\)

Các bạn có thể làm thử bài tập này và chấm điểm lời giải của bạn tại đây

Bài toán 2

Cho số nguyên dương \(N (N \le 1000)\). Hãy tính \(N!\)

Đặt vấn đề

Nếu không quan tâm tới phạm vi giá trị của các biến trong 2 bài tập trên. Thì đây là những bài tập cực kỳ đơn giản. Tuy nhiên, nếu bạn code Pascal/C++ sẽ gặp phải hiện tượng lỗi tràn số do kiểu dữ liệu có size lớn nhất là long long cũng chỉ lưu được một số nguyên có \(18-19\) chữ số

Xử lý số lớn sẽ giúp các bạn làm những bài tập đơn giản này

Ý tưởng

Tính toán phép cộng, trừ, nhân, chia theo phong cách của học sinh tiểu học

Xử lý số lớn

Tổ chức dữ liệu

Coi mỗi một số nguyên là 1 vector. Mỗi chữ số của số nguyên đó là một phần tử.
Ví dụ: ta có số nguyên A = 123456789

  • Số nguyên \(A\) khi biểu diễn dưới dạng vector: \(A = [9, 8, 7, 6, 5, 4, 3, 2, 1]\).
  • Ở đây, ta biểu diễn số A theo trình tự đảo ngược là do các phép cộng, trừ, nhân ta đều cộng các số tương ứng với hàng đơn vị trước rồi mới dần dần tính đến hàng chục, hàng nghìn. Hơn nữa, khi cộng, trừ, nhân hai số với nhau có thể độ dài của kết quả sẽ dài hơn độ dài của hai số ban đầu, việc chèn thêm các số vào phần đầu của kết quả sẽ mất thời gian hơn (phép insert trong vector có độ phức tạp \(O(N)\)), nếu lưu theo thứ tự đảo ngược thì có nghĩa là ta chỉ cần thêm các số vào cuối (độ phức tạp \(O(1)\)).

Trong C++ ta có thể định nghĩa một kiểu dữ liệu dùng cho số lớn như sau

typedef vector<long long> bignum;

2. Phép cộng

\(A = [9, 8, 7, 6, 5, 4, 3, 2, 1]\)

\(B = [1, 7, 4, 3, 1, 8, 9]\)

Ý tưởng

Gọi \(C\) là kết quả, số lượng chữ số ở vector kết quả sẽ có ít nhất là \(k = max(A.size(), B.size())\)
Cộng lần lượt từ vị trí \(0\) đến vị trí \(k-1\), khi cộng đến vị trí \(i\) ta có:
Gọi \(mem\) là giá trị của phần nhớ tại bước cộng thứ \(i-1\), khởi tạo \(= 0\)
Tổng tại vị trí \(i\): \(sum = A[i] + B[i] + mem\). Giá trị của \(C[i] = sum \; \% \; 10\)
Giá trị của mem: \(mem = sum \; / \; 10\)

Test thử với hai số A,B bên trên:

Phép cộng

Code phép cộng hai số lớn C++

#include<bits/stdc++.h>
using namespace std;

#define ll long long

typedef vector<ll> bignum;

bignum add(bignum a, bignum b) {
    bignum c;
    c.resize(max(a.size(), b.size()));
    //Resize để thêm 0 vào cuối cho những số có độ dài khác nhau
    a.resize(c.size());
    b.resize(c.size());
    ll mem = 0;
    for (int i = 0; i < c.size(); ++i){
        ll sum = mem + a[i] + b[i];
        c[i] = sum%10;
        mem = sum/10;
    }
    if(mem > 0) c.push_back(mem);
    return c;
}

bignum toBignum(string a){
    bignum c;
    c.clear();
    for(int i = a.size()-1; i >=0; i--)
        c.push_back(a[i] - 48);
    return c;
}

string toString(bignum a){
    string s = "";
    for(int i = a.size()-1; i >=0; i--)
        s += char(a[i]+48);
    return s;
}

int main() {
    string a,b;
    cin>>a>>b;
    bignum A = toBignum(a);
    bignum B = toBignum(b);
    bignum C = add(A,B);
    cout<<toString(C);
}

3. Phép trừ

Giả thiết: \(A \geq B\).

\(A = [9, 8, 7, 6, 5, 4, 3, 2, 1]\)

\(B = [1, 7, 4, 3, 1, 8, 9]\)

Ý tưởng

  • Gọi \(C\) là kết quả, số lượng chữ số ở vector kết quả sẽ có nhiều nhất là \(k = max(A.size(), B.size())\)
  • Trừ lần lượt từ vị trí \(0\) đến vị trí \(k-1\), khi trừ đến vị trí \(i\) ta có:
    • Gọi mem là giá trị của phần nhớ tại bước trừ thứ \(i-1\), khởi tạo \(= 0\)
    • Hiệu tại vị trí \(i\): \(subtract = A[i] – B[i] – mem\)
    • Nếu \(subtract < 0\) thì ta sẽ phải vay thêm \(10\): \(substract += 10\), \(mem = 1\); ngược lại thì \(mem = 0\).
    • Giá trị của \(C[i] = subtract\)

Test thử với hai số A,B bên trên

Phép trừ

Code phép trừ hai số lớn C++

bignum subtract(bignum a, bignum b) {
    bignum c;
    c.resize(max(a.size(), b.size()));
    //Resize để thêm 0 vào cuối cho những số có độ dài khác nhau
    a.resize(c.size());
    b.resize(c.size());
    ll mem = 0;
    for (int i = 0; i < c.size(); ++i){
        ll sub = a[i] - b[i] - mem;
        if(sub < 0){
            mem = 1;
            sub += 10;
        }else
            mem = 0;
        c[i] = sub;
    }
    //loại bỏ các số 0 ở đầu
    while(c.size()>1 && c[c.size()-1] == 0) c.pop_back();
    return c;
}

4. Phép nhân

\(A = [9, 8, 7, 6]\)

\(B = 19\)

Ý tưởng

  • Gọi \(C\) là kết quả, số lượng chữ số ở vector kết quả sẽ có nhiều nhất là \(k = max(A.size(), B.size())\)
  • Nhân lần lượt từ vị trí \(0\) đến vị trí \(k-1\), khi nhân đến vị trí \(i\) ta tiến hành cộng luôn các số để lấy kết quả:
    • Gọi mem là giá trị của phần nhớ tại bước trừ thứ \(i-1\), khởi tạo \(= 0\)
    • Tích tại vị trí \(i\): \(mul = A[i] * B[i] + mem\). Giá trị của \(C[i] = mul \; \% \; 10\)
    • Giá trị của mem: \(mem = mul \; / \; 10\).
    • Lưu ý: Vì giá trị của \(C[i] < 10\) nên giá trị của \(mul\) và \(mem\) luôn luôn nằm trong khoảng giá trị của kiểu dữ liệu long long

Test thử với hai số A,B bên trên

Ta thấy giá trị của nhớ lúc nhân xong tất cả các chữ số là 12, vậy chỉ cần thêm 12 vào cuối của vector kết quả là ta sẽ được tích của A và B

Giả thiết Nhân số lớn với một số nhỏ(kiểu long long)

Phép nhân
Để nhân số lớn với số lớn, ta làm tương tự. Nhân số A với từng chữ số của B và cộng lại

Code phép nhân hai số lớn C++

bignum multiple(bignum a, ll b) {
    bignum c;
    c.resize(a.size());
    ll mem = 0;
    for (int i = 0; i < c.size(); ++i){
        ll mul = mem + a[i]*b;
        c[i] = mul%10;
        mem = mul/10;
    }
    while(mem>0){
        c.push_back(mem%10);
        mem/=10;
    }
    return c;
}
bignum multipleBig(bignum a, bignum b) {
    bignum c,cnt;
    c.clear();
    c.push_back(0);
    cnt.clear();
    ll mem = 0;
    for (int i = 0; i < b.size(); ++i){
        //nhân từng chữ số của b với a
        bignum tmp = multiple(a,b[i]);
        //Thêm 0 vào đầu
        tmp.insert(tmp.begin(),cnt.begin(), cnt.end());
        //cộng dồn vào kết quả
        c = add(c, tmp);
        cnt.push_back(0);
    }
    return c;
}

5. Phép chia

Giả thiết: Chia số lớn với một số nhỏ (kiểu long long)

\(A = [9, 8, 7, 6]\)

\(B = 19\)

Ý tưởng

  • Gọi \(C\) là kết quả, số lượng chữ số ở vector kết quả sẽ có nhiều nhất là \(k = max(A.size(), B.size())\)
  • Chia lần lượt từ vị trí \(k-1\) đến vị trí \(0\), ta có
    • Gọi mem là giá trị của phần dư tại bước nhân trước, khởi tạo \(= 0\)
    • Giá trị số chia tại vị trí \(i\): \(div = mem*10+A[i]\)
    • Giá trị của \(C[i] = div/b\)
    • Giá trị của \(mem\): \(mem = div % b\)
    • Lưu ý: Vì giá trị của \(C[i] < 10\) nên giá trị của \(div\) và \(mem\) luôn luôn nằm trong khoảng giá trị của kiểu dữ liệu long long

Code mẫu phép chia số lớn với số nhỏ C++

// chia lấy phần nguyên
bignum division(bignum a, ll b) {
    bignum c;
    c.resize(a.size());
    ll mem = 0;
    for (int i = c.size()-1; i >=0; i--){
        ll div = mem*10 + a[i];
        c[i] = div/b;
        mem = div%b;
    }
    //loại bỏ các số 0 ở đầu
    while(c.size()>1 && c[c.size()-1] == 0) c.pop_back();
    return c;
}
//chia lấy phần dư
ll mod(bignum a, ll b) {
    ll mem = 0;
    for (int i = a.size()-1; i >=0; i--){
        ll div = mem*10 + a[i];
        mem = div%b;
    }
    return mem;
}

6. Đánh giá độ phức tạp

Với \(M,N\) là độ dài của các số lớn

Kỹ thuật Độ phức tạp
Cộng hai số lớn \(O(M+N)\)
Trừ hai số lớn \(O(M+N)\)
Nhân số lớn với số nhỏ \(O(M)\)
Nhân hai số lớn \(O(M * N)\)
Chia lấy phần nguyên/dư số lớn với số nhỏ \(O(M)\)

Code mẫu toàn bộ các hàm trên tham khảo ở đây

Bạn có thể tham khảo để làm bài tập xử lý số lớn cơ bản ở đây

7. Cải tiến kỹ thuật xử lý số lớn

Ý tưởng

Thay vì mỗi phần tử của vector lưu một chữ số của số cần tính, thì mình lưu X số cho mỗi phần tử (với \(1 \le X \le 18\))

Giả thiết

Với \(X = 4\)

\(A = 123456789\) được biểu diễn thành: \(A = [6789, 2345, 1]\)

\(B = 9813471\) được biểu diễn thành: \(B = [3471, 981]\)

Cách giải

  • Gọi \(C\) là kết quả, số lượng chữ số ở vector kết quả sẽ có nhiều nhất là \(k = max(A.size(), B.size())\)
  • Cộng lần lượt từ vị trí \(0\) đến vị trí \(k-1\), khi cộng đến vị trí \(i\) ta có:
    • Gọi \(mem\) là giá trị của phần nhớ tại bước cộng thứ \(i-1\), khởi tạo \(= 0\)
    • Tổng tại vị trí \(i\): \(sum = A[i] + B[i] + mem\) Giá trị của \(C[i] = sum \; \% \; 10^4 \; (là \; 10^X)\)
    • Giá trị của \(mem\): \(mem = sum / 10^4\)
    • Lưu ý lúc chuyển từ bignum sang string: Nếu số lượng chữ số ở phần tử đó không đủ \(X\), phải thêm \(0\) vào đầu cho đủ (xem ví dụ dưới)

Test thử với hai số A,B bên trên

Xử lý số lớn cải tiến

Code mẫu cộng hai số lớn cải tiến

bignum add(bignum a, bignum b) {
    bignum c;
    c.resize(max(a.size(), b.size()));
    a.resize(c.size());
    b.resize(c.size());
    ll mem = 0;
    for (int i = 0; i < c.size(); ++i){
        ll sum = mem + a[i] + b[i];
        c[i] = sum%base;
        mem = sum/base;
    }
    if(mem > 0) c.push_back(mem);
    return c;
}

Bạn có thể tham khảo toàn bộ code xử lý số lớn cải tiến tại đây

Kết luận

  • Vậy thời gian thực hiện phép xử lý số lớn ở kỹ thuật này sẽ nhanh gấp \(X\) lần so với kỹ thuật trước.
  • Với phép cộng, trừ hai số lớn: có thể đặt \(X = 17\), do mình vẫn có thể cộng trừ hai số có \(17\) chữ số với nhau trong kiểu long long
  • Với phép nhân, chia hai số lớn: có thể đặt \(X = 9\), do mình vẫn có thể nhân hai số có \(9\) chữ số với nhau (nhân lên sẽ ra kết quả khoảng \(10^{18}\)) trong kiểu long long

8. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Unable to display PDF file. Download instead. 

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *