Đếm số phép gán và so sánh trong fibonacci năm 2024

Question

Fibonacci là dãy số kinh điển trong toán học được tìm thấy cách đây hơn 800 năm. Đến nay các nhà khoa học phát hiện nhiều trùng hợp thú vị về dãy số này trong tự nhiên. Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng 1 và 1, sau đó các số tiếp theo sẽ bằng tổng của 2 số liền trước nó.

Nội dung chính Show

II. Cách biểu diễn số nguyên lớn
1. Biểu diễn bằng chuỗi kí tự
2. Biểu diễn bằng mảng các kí tự
III. Các phép toán Nhập - Xuất, So sánh, Cộng và Trừ
1. Nhập xuất các số nguyên lớn
2. So sánh hai số nguyên lớn
3. Phép cộng hai số nguyên lớn
4. Phép trừ hai số nguyên lớn
5. Chương trình đầy đủ
IV. Bài toán minh họa
1. Số Fibonaci thứ n
Ý tưởng
Cài đặt
2. Số nguồn
Ý tưởng

Dã số Fibonacci 1, 1, 2, 3, 5, 8, 13, 21….

Thuật toán về dãy số Fibonacci thường được dùng trong giảng dạy và kiểm tra kỹ năng về thuật toán. Do vậy, nắm rõ về thuật toán này là một lợi thế của bạn.

Chúng ta đều biết rằng, việc giải bài toán bằng máy tính nói chung và lập trình thi đấu nói riêng luôn luôn đối mặt với dữ liệu có kích thước rất lớn. Hiển nhiên là vì những dữ liệu quá lớn vượt ra ngoài khả năng tính toán của con người, nên mới cần tới sự trợ giúp của máy tính.

Với sự nâng cấp liên tục của máy tính điện tử, độ lớn dữ liệu mà máy tính có thể lưu trữ được cũng ngày càng tăng lên. Tuy nhiên, khả năng lưu trữ luôn luôn là hữu hạn, mà dữ liệu là vô hạn (dữ liệu dạng văn bản có thể dài vô hạn, dữ liệu dạng số có thể cực kỳ lớn,...). Ngôn ngữ lập trình đã có sẵn rất nhiều kiểu dữ liệu với khoảng giá trị rất lớn, nhưng cũng không phải luôn luôn lưu trữ được mọi giá trị.

Riêng đối với kiểu số trong C++, chúng ta có sẵn kiểu dữ liệu nguyên thủy là

typedef vector < int > vi;

7 với tầm lưu trữ lên tới khoảng 2020 chữ số. Nhưng nếu như có những dữ liệu số với độ dài nhiều hơn thế thì sao? Kĩ thuật xử lý số nguyên lớn ra đời nhằm giải quyết vấn đề đó. Trong chuyên đề này, chúng ta sẽ được học cách biểu diễn các số nguyên lên tới hàng trăm, hàng nghìn, thậm chí vài chục nghìn chữ số,...dựa vào khả năng lưu trữ chuỗi kí tự của máy tính. Các số nguyên sẽ được chuyển sang dạng chuỗi kí tự, sau đó thiết kế những phép toán cộng, trừ, nhân, chia, đồng dư tương ứng. Do độ dài của chuỗi kí tự phụ thuộc vào khả năng lưu trữ của trình biên dịch (mà thông thường rất lớn) nên ta dễ dàng giải quyết vấn đề.

Trước khi đọc chuyên đề này, bạn đọc nên nắm vững các kĩ thuật xử lý chuỗi kí tự, các quy tắc so sánh kí tự trong máy tính cũng như kiến thức về nạp chồng toán tử. Các cài đặt cụ thể trong bài viết sẽ được minh họa bằng ngôn ngữ C++11.

II. Cách biểu diễn số nguyên lớn

1. Biểu diễn bằng chuỗi kí tự

Một cách hay để biểu diễn các số nguyên lớn trong C++ là sử dụng lớp chuỗi kí tự

typedef vector < int > vi;

8 trong C++. Các chữ số sẽ tương ứng với các kí tự trong chuỗi, và độ dài của các số khi đó sẽ phụ thuộc vào chương trình biên dịch của ngôn ngữ. Phương pháp biểu diễn này khá được ưa chuộng vì nó đơn giản, dễ hiểu, tuy nhiên trong một số trường hợp cụ thể, thời gian chạy của chương trình cài đặt số lớn bằng

typedef vector < int > vi;

9 sẽ khá lâu. Tác giả sẽ giải thích cụ thể ở các thuật toán chi tiết.

2. Biểu diễn bằng mảng các kí tự

Sử dụng một mảng để chứa các chữ số cũng là một phương án thường được sử dụng. Với phương pháp này, mỗi chữ số sẽ tương ứng với một kí tự trong mảng, đồng thời ta duy trì một biến đếm để kiểm soát số chữ số của số ban đầu. Với phương pháp này, tuy cài đặt có khó hơn, nhưng tốc độ chạy chương trình sẽ nhanh hơn, và chúng ta cũng không cần tới thao tác chuyển đổi giữa kí tự và chữ số như phương pháp đầu tiên.

III. Các phép toán Nhập - Xuất, So sánh, Cộng và Trừ

Bây giờ thì chúng ta sẽ đi vào cách cài đặt cụ thể với từng phép toán đối với số nguyên lớn. Tôi sẽ cài đặt các phép toán ở cả hai phương pháp sử dụng chuỗi kí tự và mảng các chữ số. Để cho đơn giản, chúng ta sẽ quy định như sau:

Đối với phương pháp thứ nhất, tôi định nghĩa một kiểu void input(bignum_str &number) { cin >> number; } void output(bignum_str number) { cout << number; } int main() { string a, b; input(a); input(b); output(a); output(b); }
0 để biểu diễn các số lớn (chính là
typedef vector < int > vi;
9):
typedef string bignum_str;
Đối với phương pháp thứ hai, tôi định nghĩa một kiểu void input(bignum_str &number) { cin >> number; } void output(bignum_str number) { cout << number; } int main() { string a, b; input(a); input(b); output(a); output(b); }
2 để biểu diễn mảng chứa các chữ số của số nguyên, ở đây sử dụng kiểu
void input(bignum_str &number) { cin >> number; } void output(bignum_str number) { cout << number; } int main() { string a, b; input(a); input(b); output(a); output(b); }
3:
typedef vector < int > vi;

Ngoài ra, chúng ta sẽ coi như chỉ thực hiện các phép toán đối với các số nguyên không âm thôi. Nếu muốn sử dụng tính toán số lớn với các số nguyên có dấu, các bạn chỉ cần biến đổi một chút từ code gốc là được. Chẳng hạn, khi cộng hai số nguyên âm với nhau, các bạn chỉ cần coi như đang cộng hai số nguyên dương rồi thêm dấu trừ vào phía trước,...Giờ thì bắt đầu thôi!

1. Nhập xuất các số nguyên lớn

Đối với cách biểu diễn bằng chuỗi kí tự, chúng ta chỉ cần trực tiếp nhập - xuất các chuỗi kí tự biểu diễn số nguyên là xong. Cài đặt như sau:

void input(bignum_str &number)
{
    cin >> number;
}
void output(bignum_str number)
{
    cout << number;
}
int main()
{
    string a, b;
    input(a);
    input(b);
    output(a);
    output(b);
}

Còn đối với cách biểu diễn bằng mảng, ta vẫn nhập chuỗi bằng kiểu

typedef vector < int > vi;

9, nhưng sau đó ta sẽ đưa lần lượt từng kí tự số vào

void input(bignum_str &number)
{
    cin >> number;
}
void output(bignum_str number)
{
    cout << number;
}
int main()
{
    string a, b;
    input(a);
    input(b);
    output(a);
    output(b);
}

3, và đổi chúng thành chữ số luôn.

Cài đặt 2: Đối với hai hàm

void input(bignum_str &number)
{
    cin >> number;
}
void output(bignum_str number)
{
    cout << number;
}
int main()
{
    string a, b;
    input(a);
    input(b);
    output(a);
    output(b);
}

6 và

void input(bignum_str &number)
{
    cin >> number;
}
void output(bignum_str number)
{
    cout << number;
}
int main()
{
    string a, b;
    input(a);
    input(b);
    output(a);
    output(b);
}

7, tôi sẽ sử dụng nạp chồng các toán tử

void input(bignum_str &number)
{
    cin >> number;
}
void output(bignum_str number)
{
    cout << number;
}
int main()
{
    string a, b;
    input(a);
    input(b);
    output(a);
    output(b);
}

8 và

void input(bignum_str &number)
{
    cin >> number;
}
void output(bignum_str number)
{
    cout << number;
}
int main()
{
    string a, b;
    input(a);
    input(b);
    output(a);
    output(b);
}

9, kèm theo luôn cách sử dụng trong chương trình chính:

// Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &number)
{
    string s;
    cin >> s;
    number.clear();
    for (int i = 0; i < s.size(); ++i)
        number.push_back(s[i] - '0');
    return cin;
}
// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a) 
{
    for (auto d: a) 
        cout << d;
    return cout;
} 
int main()
{
    // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout.
    vi a, b;
    cin >> a >> b;
    cout << a << endl << b;
    return 0;
}

2. So sánh hai số nguyên lớn

Nguyên tắc so sánh hai số nguyên lớn khi sử dụng chuỗi kí tự như sau:

Bước 11: Chuẩn hóa hai chuỗi bằng cách cân bằng độ dài của chúng. Nếu chuỗi nào ngắn hơn thì ta thêm kí tự // Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn. istream &operator >> (istream &cin, vi &number) { string s; cin >> s; number.clear(); for (int i = 0; i < s.size(); ++i) number.push_back(s[i] - '0'); return cin; } // Nạp chồng toán tử chèn luồng, dùng để in ra số lớn. ostream &operator << (ostream &cout, const vi &a) { for (auto d: a) cout << d; return cout; } int main() { // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout. vi a, b; cin >> a >> b; cout << a << endl << b; return 0; } 0 vào đầu chuỗi đó tới khi độ dài hai chuỗi bằng nhau.
Bước 22: So sánh hai chuỗi sử dụng trực tiếp các toán tử // Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn. istream &operator >> (istream &cin, vi &number) { string s; cin >> s; number.clear(); for (int i = 0; i < s.size(); ++i) number.push_back(s[i] - '0'); return cin; } // Nạp chồng toán tử chèn luồng, dùng để in ra số lớn. ostream &operator << (ostream &cout, const vi &a) { for (auto d: a) cout << d; return cout; } int main() { // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout. vi a, b; cin >> a >> b; cout << a << endl << b; return 0; } 1. Những toán tử này sẽ so sánh các chuỗi theo mã ASCII của từng cặp kí tự, và "vô tình" thứ tự ASCII lại chính là thứ tự đúng của các số.

Cài đặt 1: Hàm

// Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &number)
{
    string s;
    cin >> s;
    number.clear();
    for (int i = 0; i < s.size(); ++i)
        number.push_back(s[i] - '0');
    return cin;
}
// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a) 
{
    for (auto d: a) 
        cout << d;
    return cout;
} 
int main()
{
    // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout.
    vi a, b;
    cin >> a >> b;
    cout << a << endl << b;
    return 0;
}

2 dưới đây sẽ so sánh hai chuỗi số aa và b,b, nếu a<ba < b thì trả về −1,-1, nếu a>ba > b thì trả về 1,1, còn a=ba = b thì trả về 00. Ngoài ra, tôi viết sẵn hàm

// Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &number)
{
    string s;
    cin >> s;
    number.clear();
    for (int i = 0; i < s.size(); ++i)
        number.push_back(s[i] - '0');
    return cin;
}
// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a) 
{
    for (auto d: a) 
        cout << d;
    return cout;
} 
int main()
{
    // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout.
    vi a, b;
    cin >> a >> b;
    cout << a << endl << b;
    return 0;
}

3 để cân bằng độ dài hai chuỗi số aa và bb. Từ các phép tính dưới sẽ sử dụng luôn chứ không viết lại nữa.

void equal_length(bignum_str &a, bignum_str &b)
{
    while (a.size() < b.size())
        a = '0' + a;
    while (b.size() < a.size())
        b = '0' + b;
}
int compare(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    if (a < b) // Có thể là a <= b.
        return -1;
    if (a > b) // Có thể là a >= b.
        return 1;
    return 0;
}

Đối với phương pháp dùng mảng, ta thực hiện hai bước:

Bước 11: Cân bằng độ dài hai số, bằng cách đẩy thêm các số 00 vào đầu hai số.

Bước 22: Chúng ta sẽ nạp chồng toán tử cho các toán tử

 // Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &number)
{ 
string s;  
cin >> s;  
number.clear();  
for (int i = 0; i < s.size(); ++i)  
    number.push_back(s[i] - '0');  
return cin;  
}
// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a)
{ for (auto d: a)  
    cout << d;  
return cout;  
}
int main()
{ // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout.  
vi a, b;  
cin >> a >> b;  
cout << a << endl << b;  
return 0;  
}

4,

 // Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &number)
{ 
string s;  
cin >> s;  
number.clear();  
for (int i = 0; i < s.size(); ++i)  
    number.push_back(s[i] - '0');  
return cin;  
}
// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a)
{ for (auto d: a)  
    cout << d;  
return cout;  
}
int main()
{ // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout.  
vi a, b;  
cin >> a >> b;  
cout << a << endl << b;  
return 0;  
}

5,

 // Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &number)
{ 
string s;  
cin >> s;  
number.clear();  
for (int i = 0; i < s.size(); ++i)  
    number.push_back(s[i] - '0');  
return cin;  
}
// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a)
{ for (auto d: a)  
    cout << d;  
return cout;  
}
int main()
{ // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout.  
vi a, b;  
cin >> a >> b;  
cout << a << endl << b;  
return 0;  
}

6,

 // Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &number)
{ 
string s;  
cin >> s;  
number.clear();  
for (int i = 0; i < s.size(); ++i)  
    number.push_back(s[i] - '0');  
return cin;  
}
// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a)
{ for (auto d: a)  
    cout << d;  
return cout;  
}
int main()
{ // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout.  
vi a, b;  
cin >> a >> b;  
cout << a << endl << b;  
return 0;  
}

7 và

 // Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn.
istream &operator >> (istream &cin, vi &number)
{ 
string s;  
cin >> s;  
number.clear();  
for (int i = 0; i < s.size(); ++i)  
    number.push_back(s[i] - '0');  
return cin;  
}
// Nạp chồng toán tử chèn luồng, dùng để in ra số lớn.
ostream &operator << (ostream &cout, const vi &a)
{ for (auto d: a)  
    cout << d;  
return cout;  
}
int main()
{ // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout.  
vi a, b;  
cin >> a >> b;  
cout << a << endl << b;  
return 0;  
}

8. Thực tế, trong khi lập trình ta không cần dùng nhiều tới vậy vì các trường hợp có thể bù trừ cho nhau, tuy nhiên tôi vẫn viết đủ tất cả các toán tử để bạn đọc lựa chọn sử dụng tùy ý.

Cài đặt 2: So sánh hai số nguyên lớn aa và bb sử dụng mảng lưu chữ số:

// Viết thêm các số 0 ở đầu.
void add_zero(vi &a, int sz) 
{
    // Đầu tiên đảo ngược số để tối ưu thời gian khi thêm phần tử.
    reverse(a.begin(), a.end()); 
    while (a.size() < sz) 
        a.push_back(0); 
    reverse(a.begin(), a.end());
}
// Đưa 2 số về cùng một size bằng các push các số 0 lên đầu.
void change(vi &a, vi &b) 
{ 
    int sz = max(a.size(), b.size());
    add_zero(a, sz);
    add_zero(b, sz);
}
bool operator < (vi a, vi b) 
{
    change(a, b);
    for (int i = 0; i < a.size(); ++i) 
        if (a[i] < b[i]) 
            return true;
        else if (a[i] > b[i]) 
            return false;
    return false;
}
bool operator > (vi a, vi b) 
{
    change(a, b);
    for (int i = 0; i < a.size(); ++i) 
        if (a[i] > b[i]) 
            return true;
        else if (a[i] < b[i]) 
            return false;
    return false;
}
bool operator <= (vi a, vi b) 
{
    change(a, b);
    for (int i = 0; i < a.size(); ++i) 
        if (a[i] < b[i]) 
            return true;
        else if (a[i] > b[i]) 
            return false;
    return true;
}
bool operator >= (vi a, vi b) 
{
    change(a, b);
    for (int i = 0; i < a.size(); ++i) 
        if (a[i] > b[i]) 
            return true;
        else if (a[i] < b[i]) 
            return false;
    return true;
}
bool operator == (vi a, vi b) 
{
    change(a, b);
    for (int i = 0; i < a.size(); ++i) 
        if (a[i] != b[i]) return false;
    return true;
}

3. Phép cộng hai số nguyên lớn

Thuật toán cộng hai số nguyên lớn sử dụng chuỗi kí tự như sau:

Bước 11: Cân bằng độ dài hai chuỗi bằng cách thêm kí tự // Nạp chồng toán tử trích luồng, dùng để nhập vào số lớn. istream &operator >> (istream &cin, vi &number) { string s; cin >> s; number.clear(); for (int i = 0; i < s.size(); ++i) number.push_back(s[i] - '0'); return cin; } // Nạp chồng toán tử chèn luồng, dùng để in ra số lớn. ostream &operator << (ostream &cout, const vi &a) { for (auto d: a) cout << d; return cout; } int main() { // Khi nhập xuất thì khai báo biến kiểu vi và dùng trực tiếp lệnh cin, cout. vi a, b; cin >> a >> b; cout << a << endl << b; return 0; } 0 vào đầu chuỗi ngắn hơn.
Bước 22: Cộng từng kí tự chữ số của hai chuỗi từ phải qua trái giống như quy tắc đặt tính ở tiểu học, phần nhớ được mang theo sang bên trái ở mỗi lần cộng. Sau mỗi lần cộng ở một hàng, ta thêm kí tự cuối của kết quả cộng hàng đó vào bên trái chuỗi kết quả.

Bước 33: Nếu biến nhớ còn khác 0,0, viết thêm kí tự

 void equal_length(bignum_str &a, bignum_str &b)
{ 
while (a.size() < b.size())  
    a = '0' + a;  
while (b.size() < a.size())  
    b = '0' + b;  
}
int compare(bignum_str a, bignum_str b)
{ equal_length(a, b);  
if (a < b) // Có thể là a <= b.  
    return -1;  
if (a > b) // Có thể là a >= b.  
    return 1;  
return 0;  
}

0 vào bên trái chuỗi kết quả.

Cài đặt 1: Cộng hai số nguyên lớn aa và bb sau đó trả về tổng của chúng bằng chuỗi kí tự:

bignum_str add(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    int carry = 0;
    bignum_str res;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        // Cộng hai chữ số cùng hàng và thêm biến nhớ từ hàng bên phải dồn lên.
        int d = (a[i] - '0') + (b[i] - '0') + carry;
        carry = d / 10; // Biến nhớ bằng kết quả hàng trước chia 10.
        res = (char)(d % 10 + '0') + res; // Viết chữ số cuối của kết quả.
    }
    if (carry)
        res = '1' + res;
    return res;
}

Đối với phương pháp mảng chữ số, ta làm hoàn toàn tương tự. Nhưng vì ban đầu các số được đưa vào mảng theo thứ tự ngược lại, nghĩa là chữ số hàng đơn vị của số ban đầu sẽ là phần tử đầu tiên của mảng, nên bước cân bằng độ dài hai mảng là không cần thiết nữa. Điều này giúp tiết kiệm thời gian chạy đáng kể.

Cài đặt 2: Cộng hai số nguyên lớn sử dụng mảng chữ số. Sử dụng nạp chồng toán tử

void equal_length(bignum_str &a, bignum_str &b)
{
    while (a.size() < b.size())
        a = '0' + a;
    while (b.size() < a.size())
        b = '0' + b;
}
int compare(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    if (a < b) // Có thể là a <= b.
        return -1;
    if (a > b) // Có thể là a >= b.
        return 1;
    return 0;
}

1 đối với hai biến kiểu

void input(bignum_str &number)
{
    cin >> number;
}
void output(bignum_str number)
{
    cout << number;
}
int main()
{
    string a, b;
    input(a);
    input(b);
    output(a);
    output(b);
}

2. Ngoài ra, ta cần thiết kế một hàm

void equal_length(bignum_str &a, bignum_str &b)
{
    while (a.size() < b.size())
        a = '0' + a;
    while (b.size() < a.size())
        b = '0' + b;
}
int compare(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    if (a < b) // Có thể là a <= b.
        return -1;
    if (a > b) // Có thể là a >= b.
        return 1;
    return 0;
}

3 để xóa các chữ số 00 vô nghĩa ở đầu kết quả sau khi cộng xong. Hàm

void equal_length(bignum_str &a, bignum_str &b)
{
    while (a.size() < b.size())
        a = '0' + a;
    while (b.size() < a.size())
        b = '0' + b;
}
int compare(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    if (a < b) // Có thể là a <= b.
        return -1;
    if (a > b) // Có thể là a >= b.
        return 1;
    return 0;
}

4 sẽ được tái sử dụng từ cài đặt của phép so sánh.

// Xóa các số 0 vô nghĩa ở đầu.
void del_zero(vi &a) 
{ 
    reverse(a.begin(), a.end()); 
    while (a.size() >= 2) 
        if (a.back() == 0) 
            a.pop_back();
        else 
            break;
    reverse(a.begin(), a.end());
}
// Phép toán cộng.
vi operator + (vi a, vi b) 
{
    change(a, b);
    int sz = a.size();
    vi c;
    int rem = 0; 
    for (int i = sz - 1; i >= 0; --i) 
    {
        int x = a[i] + b[i] + rem;
        rem = x / 10; 
        x %= 10;
        c.push_back(x);
    }
    c.push_back(rem);
    reverse(c.begin(), c.end());
    del_zero(c);
    return c;
}

4. Phép trừ hai số nguyên lớn

Để cho đơn giản, chúng ta chỉ xét trường hợp lấy số lớn hơn trừ số nhỏ hơn. Nếu như a<ba < b thì phải hoán đổi vị trí của chúng trước khi trừ, rồi đưa ra kết quả có thêm dấu

void equal_length(bignum_str &a, bignum_str &b)
{
    while (a.size() < b.size())
        a = '0' + a;
    while (b.size() < a.size())
        b = '0' + b;
}
int compare(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    if (a < b) // Có thể là a <= b.
        return -1;
    if (a > b) // Có thể là a >= b.
        return 1;
    return 0;
}

5 ở đằng trước.

Đối với phương pháp chuỗi, thuật toán như sau:

Bước 11: Cân bằng độ dài hai chuỗi bằng cách thêm kí tự '0' vào đầu chuỗi ngắn hơn.
Bước 22: Lầy từng cặp chữ số trừ đi nhau theo chiều từ phải qua trái giống như đặt tính, nếu kết quả bị âm thì cộng thêm 1010 và nhớ −1-1 sang hàng phía trước.
Bước 33: Nếu kết quả cuối cùng còn số 00 vô nghĩa ở bên trái thì xóa nó đi. Lưu ý chỉ được xóa đến khi kết quả còn 11 chữ số thì dừng lại.

Cài đặt 1: Trừ hai số lớn kiểu chuỗi:

bignum_str diff(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    int d = 0, carry  = 0;
    bignum_str res;
    for (int i = a.size() - 1; i >= 0; --i)
    {
        d = (a[i] - '0') - (b[i] - '0') - carry;
        // Tính toán biến nhớ cho hàng này.
        if (d < 0)
        {
            d += 10;
            carry = 1;
        }
        else 
            carry = 0;
        // Thêm kí tự cuối cùng của kết quả trừ hàng vào đầu biến hiệu.
        res = (char) (d + '0') + res;
    }
    // Xóa chữ số 0 vô nghĩa ở đầu kết quả. Nếu kết quả bằng 0 thì giữ lại một kí tự.
    while (res.size() > 1 && res.front() == '0')
        res.erase(res.begin());
    return res;
}

Đối với phương pháp dùng mảng lưu chữ số, cách làm cũng hoàn toàn tương tự: Đầu tiên cân bằng độ dài hai mảng, rồi xét lần lượt từng cặp chữ số từ cuối về đầu, trừ chúng cho nhau và lưu biến nhớ để đẩy giá trị sang hàng phía trước khi cần thiết.

Cài đặt 2: Trừ hai số nguyên lớn cho nhau sử dụng phương pháp mảng lưu chữ số. Hàm

void equal_length(bignum_str &a, bignum_str &b)
{
    while (a.size() < b.size())
        a = '0' + a;
    while (b.size() < a.size())
        b = '0' + b;
}
int compare(bignum_str a, bignum_str b)
{
    equal_length(a, b);
    if (a < b) // Có thể là a <= b.
        return -1;
    if (a > b) // Có thể là a >= b.
        return 1;
    return 0;
}

4 được tái sử dụng từ đoạn chương trình so sánh hai số bên trên. Lưu ý, các bạn phải đảm bảo phép trừ được thực hiện bởi số lớn hơn trừ đi số bé hơn.

// Xóa các số 0 vô nghĩa ở đầu.
void del_zero(vi &a) 
{ 
    reverse(a.begin(), a.end()); 
    while (a.size() >= 2) 
        if (a.back() == 0) 
            a.pop_back();
        else 
            break;
    reverse(a.begin(), a.end());
}
vi operator - (vi a, vi b) 
{
    change(a, b);
    int sz = a.size();
    vi c;
    int rem = 0;
    for (int i = sz - 1; i >= 0; --i) 
    {
        int x = a[i] - b[i] - rem;
        if (x < 0) 
        {
            x += 10;
            rem = 1;
        }
        else 
            rem = 0;
        c.push_back(x);
    }
    reverse(c.begin(), c.end());
    del_zero(c);
    return c;
}

5. Chương trình đầy đủ

Dưới đây là chương trình gồm đầy đủ các thao tác nhập - xuất và các phép toán so sánh, cộng, trừ hai số nguyên lớn (chỉ sử dụng mảng lưu chữ số, vì cách làm này tối ưu hơn). Bạn đọc có thể tham khảo để có cái nhìn tổng quan hơn về các thao tác này:

typedef vector < int > vi;

0

IV. Bài toán minh họa

1. Số Fibonaci thứ n

Đề bài

Dãy số Fibonaci được định nghĩa theo công thức:

{f0=0,f1=1fi=fi−1+fi−2,∀i:i≥2\begin{cases}f_0 = 0, f_1 = 1 \\ f_i = f_{i - 1} + f_{i - 2}, &\forall i: i \ge 2\end{cases}

Yêu cầu: Tìm số fibonaci thứ n?n?

Input:

Một dòng duy nhất chứa số tự nhiên nn.

Ràng buộc:

0≤n≤1060 \le n \le 10^6.

Output:

In ra số Fibonacci thứ nn.

Sample Input:

typedef vector < int > vi;

1

Sample Output:

typedef vector < int > vi;

2

Ý tưởng

Chắc chắn số fibonacci thứ nn có thể sẽ vượt khỏi kiểu dữ liệu

typedef vector < int > vi;

7, mà đề bài lại không yêu cầu in ra kết quả mod cho giá trị nào cả. Do đó chúng ta cần sử dụng tới kiểu số lớn để tính toán ra số Fibonacci thứ nn.

Chỉ cần sử dụng phép cộng số lớn để có thể đưa ra số Fibonacci thứ nn. Ta dùng xâu hoặc dùng mảng lưu chữ số đều được.

Độ phức tạp: O(n×α)O(n \times \alpha) với α\alpha là độ phức tạp phép cộng số lớn. Nó sẽ bằng với độ dài của các xâu cần cộng ở mỗi lượt.

Cài đặt

Dưới đây tôi cài đặt bằng phương pháp sử dụng chuỗi kí tự vì bài toán khá đơn giản, chỉ phải sử dụng duy nhất phép cộng số lớn:

typedef vector < int > vi;

3

2. Số nguồn

Đề bài

Cho số nguyên dương NN. Gọi số nguyên MM là tổng của NN cộng với các chữ số của số NN. Như vậy, NN được gọi là số nguồn của MM. Lấy ví dụ, với N=245,N = 245, thì M=245+2+4+5=256M = 245 + 2 + 4 + 5 = 256. Ta nói nguồn của 256256 là 245245.

Có những số có nhiều nguồn và cũng có những số không có nguồn. Chẳng hạn, số 216216 có hai nguồn là 198198 và 207207.

Yêu cầu: Cho số nguyên dương M,M, hãy tìm nguồn nhỏ nhất của nó?

Input:

Một dòng duy nhất chứa số nguyên dương MM.

Ràng buộc:

1≤M≤101001 \le M \le 10^{100}.

Output:

Số nguyên duy nhất là nguồn nhỏ nhất tìm được. Trong trường hợp số MM đã cho không có nguồn nào, đưa ra 00.

Sample Input:

typedef vector < int > vi;

4

Sample Output:

typedef vector < int > vi;

5

Ý tưởng

Xét số nguyên dương mm. Ta gọi nguồn của mm là nn và tổng các chữ số của nn là d(n)d(n) (giả sử mm có số nguồn).

Theo đề bài, ta có:

n+d(n)=mn + d(n) = m

Từ đây suy ra, nn luôn luôn nhỏ hơn mm. Vì vậy, số chữ số của nn cũng không thể vượt quá số chữ số của m,m, dẫn đến d(n)d(n) cùng lắm chỉ đạt giá trị tối đa là 9x9x với xx là số chữ số của mm. Từ đây, ta phát triển một thuật toán như sau:

Thử xét tất cả các giá trị d(n)d(n) có thể (9x...19x...1). Do ta cần tìm nguồn nhỏ nhất, mà n=m−d(n)n = m - d(n) nên ta sẽ xét các d(n)d(n) từ lớn nhất về bé nhất.
Đặt diff=m−d(n)\text{diff} = m - d(n). Chỗ này ta phải thực hiện phép trừ số lớn do mm rất lớn. Nếu như m>d(n)m > d(n) thì ta sẽ thu được diff>0\text{diff} > 0. Tới đây có thể coi rằng diff\text{diff} có khả năng là nguồn nhỏ nhất của mm.
Điều kiện đủ cần kiểm tra là tổng các chữ số của diff\text{diff} phải chính bằng d(n)d(n) đang duyệt ở bước 11. Nếu đúng như vậy thì ta in ra diff\text{diff} chính là nguồn nhỏ nhất của mm.

Độ phức tạp: O(9×∣m∣×α)O\big(9 \times |m| \times \alpha\big) với α\alpha là độ phức tạp của thao tác trừ số lớn.

Code mẫu

Dưới đây, tôi cài đặt lời giải theo phương pháp biểu diễn số lớn bằng mảng chữ số. Cài đặt mặc dù khá dài, nhưng về thời gian chạy sẽ tối ưu hơn dùng chuỗi kí tự:

typedef vector < int > vi;

6

Như vậy, trong bài viết này tôi đã giới thiệu tới các bạn những kiến thức cơ bản đầu tiên về xử lý số nguyên lớn trong C++, kèm theo đó là các thao tác dễ nhất là so sánh và các phép cộng, trừ. Để tiếp tục theo dõi phần hai của series Xử lý số nguyên lớn trong C++, các bạn hãy nhấn vào đây.

đánh giá So Sánh So sánh