Bài 9.5: Bài tập thực hành lý thuyết số trong C++

Chào mừng các bạn quay trở lại với chuỗi bài viết về C++! Sau khi đã tìm hiểu về các cấu trúc dữ liệu cơ bản và một vài thuật toán sắp xếp, hôm nay chúng ta sẽ lặn sâu hơn vào một lĩnh vực cực kỳ quan trọng và thú vị trong lập trình giải thuật: Lý thuyết số (Number Theory).

Lý thuyết số là nhánh của toán học nghiên cứu về các số nguyên và những tính chất của chúng. Trong lập trình, các khái niệm của lý thuyết số xuất hiện rất thường xuyên, từ các bài toán cơ bản đến các thuật toán phức tạp hơn như mã hóa. Việc nắm vững các kiến thức nền tảng và cách áp dụng chúng vào code C++ là điều cần thiết.

Bài viết này sẽ không đi sâu vào lý thuyết toán học phức tạp mà sẽ tập trung vào việc thực hành các khái niệm cơ bản nhất thông qua các bài tập cụ thể trong C++. Chúng ta sẽ cùng nhau code, giải thích và hiểu cách biến lý thuyết thành những dòng lệnh hoạt động.

Hãy cùng bắt tay vào code thôi nào!

1. Kiểm tra tính chẵn lẻ (Even/Odd Check)

Đây là bài tập kinh điển và cơ bản nhất, sử dụng phép toán modulo (%). Một số là chẵn nếu chia hết cho 2 (phần dư bằng 0), ngược lại là lẻ.

Bài toán: Nhập vào một số nguyên n, kiểm tra xem n là số chẵn hay số lẻ.

Code C++:

#include <iostream>

int main() {
    int n;
    cout << "Nhap mot so nguyen: ";
    cin >> n;

    if (n % 2 == 0) {
        cout << n << " la so chan." << endl;
    } else {
        cout << n << " la so le." << endl;
    }

    return 0;
}

Giải thích code:

Chúng ta sử dụng cin để đọc số nguyên n từ bàn phím.
Câu lệnh if (n % 2 == 0) kiểm tra phần dư của n khi chia cho 2.
Nếu phần dư bằng 0, n là số chẵn, chúng ta in ra thông báo tương ứng.
Ngược lại (phần dư khác 0), n là số lẻ.

Đơn giản, đúng không? Nhưng đây là nền tảng của nhiều bài toán khác đấy!

2. Kiểm tra số nguyên tố (Primality Test)

Số nguyên tố là số nguyên lớn hơn 1 chỉ có đúng hai ước là 1 và chính nó. Kiểm tra một số có phải là số nguyên tố hay không là một bài toán cơ bản và rất phổ biến.

Bài toán: Viết hàm kiểm tra xem một số nguyên n có phải là số nguyên tố hay không.

Code C++:

#include <iostream>
#include <cmath> // Canh can bac hai

bool isPrime(int n) {
    // So nguyen to phai lon hon 1
    if (n <= 1) {
        return false;
    }
    // So 2 la so nguyen to duy nhat chan
    if (n == 2) {
        return true;
    }
    // Cac so chan lon hon 2 khong phai so nguyen to
    if (n % 2 == 0) {
        return false;
    }
    // Chi kiem tra cac uoc so le tu 3 den sqrt(n)
    // Vi neu n co uoc d > sqrt(n) thi n cung co uoc n/d < sqrt(n)
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return false; // Tim thay mot uoc so khac 1 va n
        }
    }
    // Neu khong tim thay uoc nao, n la so nguyen to
    return true;
}

int main() {
    int num;
    cout << "Nhap mot so nguyen duong de kiem tra so nguyen to: ";
    cin >> num;

    if (isPrime(num)) {
        cout << num << " la so nguyen to." << endl;
    } else {
        cout << num << " khong phai la so nguyen to." << endl;
    }

    return 0;
}

Giải thích code:

Hàm isPrime(int n) nhận vào một số nguyên n.
Các trường hợp đặc biệt được xử lý trước: số nhỏ hơn hoặc bằng 1 không phải số nguyên tố, số 2 là số nguyên tố.
Số chẵn lớn hơn 2 chắc chắn không phải số nguyên tố, nên ta kiểm tra và trả về false ngay.
Vòng lặp bắt đầu từ 3, chỉ kiểm tra các số lẻ (i += 2) cho đến căn bậc hai của n (sqrt(n)). Lý do là nếu n có một ước d lớn hơn sqrt(n), thì n/d sẽ là một ước nhỏ hơn sqrt(n), và chúng ta đã kiểm tra ước nhỏ hơn này rồi.
Nếu tìm thấy bất kỳ số i nào trong khoảng đó mà n % i == 0, tức là n có ước khác 1 và chính nó, thì n không phải số nguyên tố.
Nếu vòng lặp kết thúc mà không tìm thấy ước nào, thì n chính là số nguyên tố.

3. Liệt kê các ước số (Listing Divisors)

Ước số của một số nguyên n là các số nguyên d sao cho n chia hết cho d.

Bài toán: Nhập vào một số nguyên dương n, liệt kê tất cả các ước số của n.

Code C++:

#include <iostream>
#include <vector> // De luu tru uoc so
#include <algorithm> // De sap xep (Tuy chon)
#include <cmath> // Canh can bac hai

int main() {
    int n;
    cout << "Nhap mot so nguyen duong de liet ke uoc so: ";
    cin >> n;

    if (n <= 0) {
        cout << "Vui long nhap mot so nguyen duong." << endl;
        return 1;
    }

    cout << "Cac uoc so cua " << n << " la: ";

    // Cach 1: Duyet tu 1 den n (don gian nhung co the cham voi so lon)
    /*
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            cout << i << " ";
        }
    }
    */

    // Cach 2: Duyet den sqrt(n) de hieu qua hon
    // Luu y: Cach nay can xu ly truong hop can bac hai la so nguyen
    vector<int> divisors;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i * i != n) { // Tranh them mot uoc lap lai neu i*i == n (tuc i la can bac hai)
                divisors.push_back(n / i);
            }
        }
    }

    // Sap xep lai de ket qua dep hon (Tuy chon)
    sort(divisors.begin(), divisors.end());

    // In cac uoc so da tim duoc
    for (int divisor : divisors) {
        cout << divisor << " ";
    }
    cout << endl;

    return 0;
}

Giải thích code:

Chúng ta đọc số n từ bàn phím.
Cách hiệu quả để tìm ước số là chỉ duyệt từ 1 đến sqrt(n). Nếu i là một ước của n, thì n/i cũng là một ước.
Ta dùng vector để lưu trữ các ước số tìm được.
Trong vòng lặp for (int i = 1; i * i <= n; ++i), nếu i là ước của n (n % i == 0), ta thêm i vào vector.
Đồng thời, ta kiểm tra nếu i * i != n, nghĩa là i không phải là căn bậc hai của n, thì n/i là một ước khác và ta cũng thêm n/i vào vector. Nếu i * i == n, thì i và n/i là cùng một số, ta chỉ thêm một lần.
Sau khi duyệt xong, vector divisors chứa tất cả các ước số.
Ta sử dụng sort để sắp xếp các ước số theo thứ tự tăng dần (bước này không bắt buộc về mặt logic nhưng giúp output dễ đọc hơn).
Cuối cùng, in tất cả các phần tử trong vector.

4. Ước số chung lớn nhất (GCD - Greatest Common Divisor)

GCD của hai hoặc nhiều số nguyên dương là số nguyên dương lớn nhất là ước của tất cả các số đó. Thuật toán Euclid là cách phổ biến và hiệu quả nhất để tính GCD.

Bài toán: Nhập vào hai số nguyên dương a và b, tính GCD của chúng.

Code C++:

#include <iostream>
#include <numeric> // Thu vien C++17 ho tro gcd

// Ham tinh GCD su dung thuat toan Euclid (de hieu)
int calculateGCD(int a, int b) {
    // Dam bao a va b la so duong
    a = abs(a); // Can #include <cmath> hoac <cstdlib> cho abs
    b = abs(b);

    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int a, b;
    cout << "Nhap hai so nguyen duong de tinh GCD: ";
    cin >> a >> b;

    // Su dung ham tu viet
    int result_manual = calculateGCD(a, b);
    cout << "GCD (" << a << ", " << b << ") bang (su dung ham tu viet): " << result_manual << endl;

    // Su dung gcd (chi kha dung tu C++17 tro len)
    // ifdef de dam bao code chay duoc tren cac trinh bien dich cu hon
    #if __cplusplus >= 201703L
    int result_std = gcd(a, b);
    cout << "GCD (" << a << ", " << b << ") bang (su dung gcd C++17): " << result_std << endl;
    #endif

    return 0;
}

Giải thích code:

Chúng ta định nghĩa hàm calculateGCD(int a, int b) theo thuật toán Euclid.
Thuật toán Euclid: GCD của hai số a và b (với a > b) bằng GCD của b và phần dư của a chia cho b (a % b). Quá trình này lặp lại cho đến khi số thứ hai bằng 0; khi đó, số thứ nhất là GCD.
Vòng lặp while (b != 0) thực hiện đúng quy trình này: gán b hiện tại cho temp, cập nhật b bằng a % b, và cập nhật a bằng giá trị b cũ (được lưu trong temp).
Khi b trở thành 0, giá trị của a chính là GCD cần tìm.
Lưu ý rằng từ C++17, thư viện <numeric> đã cung cấp sẵn hàm gcd tiện lợi. Tôi đã thêm cả hai cách để bạn thấy. #if __cplusplus >= 201703L là một chỉ thị tiền xử lý để chỉ biên dịch phần sử dụng gcd nếu phiên bản C++ hỗ trợ (từ C++17 trở lên).

5. Bội số chung nhỏ nhất (LCM - Least Common Multiple)

LCM của hai số nguyên dương a và b là số nguyên dương nhỏ nhất là bội của cả a và b. Có một công thức rất tiện lợi liên quan đến GCD:

$LCM(a, b) = \frac{|a \times b|}{GCD(a, b)}$

Với a, b dương thì công thức là $LCM(a, b) = (a \times b) / GCD(a, b)$. Tuy nhiên, để tránh trường hợp a * b bị tràn số (overflow) khi a và b quá lớn, ta nên tính theo công thức an toàn hơn:

$LCM(a, b) = (a / GCD(a, b)) \times b$

Bài toán: Nhập vào hai số nguyên dương a và b, tính LCM của chúng.

Code C++:

#include <iostream>
#include <numeric> // gcd tu C++17
#include <cmath> // abs cho calculateGCD

// Ham tinh GCD tu bai truoc
int calculateGCD(int a, int b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Ham tinh LCM
long long calculateLCM(int a, int b) {
    if (a == 0 || b == 0) return 0; // LCM cua 0 va bat ky so nao la 0

    // Su dung cong thuc LCM(a,b) = (|a*b|) / GCD(a,b)
    // De tranh overflow, tinh (a / GCD(a,b)) * b
    // Chuyen doi sang long long de co the chua gia tri lon hon
    long long abs_a = abs(a);
    long long abs_b = abs(b);

    // Dung gcd neu kha dung, neu khong dung ham tu viet
    #if __cplusplus >= 201703L
    long long common_divisor = gcd(abs_a, abs_b);
    #else
    long long common_divisor = calculateGCD(abs_a, abs_b);
    #endif

    return (abs_a / common_divisor) * abs_b;
}


int main() {
    int a, b;
    cout << "Nhap hai so nguyen de tinh LCM: ";
    cin >> a >> b;

    long long result = calculateLCM(a, b);

    cout << "LCM (" << a << ", " << b << ") bang: " << result << endl;

    return 0;
}

Giải thích code:

Chúng ta sử dụng lại hàm calculateGCD từ bài tập trước (hoặc gcd).
Hàm calculateLCM(int a, int b) sử dụng công thức liên quan đến GCD.
Chúng ta xử lý trường hợp a hoặc b bằng 0 (LCM là 0).
Giá trị của LCM có thể lớn hơn nhiều so với a hoặc b, nên ta sử dụng kiểu dữ liệu long long để lưu trữ kết quả, tránh tràn số.
Công thức được triển khai là (abs_a / common_divisor) * abs_b để giảm thiểu nguy cơ tràn số trung gian so với (abs_a * abs_b) / common_divisor.
Chúng ta cũng sử dụng abs để đảm bảo làm việc với giá trị tuyệt đối, vì GCD và LCM thường được định nghĩa cho số dương, và công thức vẫn đúng với trị tuyệt đối của số âm.

Bài tập ví dụ: C++ Bài 4.B4: Số Krishnamurthy

Số Krishnamurthy là số có tổng các giai thừa của các chữ số bằng chính nó. Ví dụ $145$ là số Krishnamurthy vì $1! + 4! + 5!$ $= 1 + 24 + 120 = 145$.

Hãy viết chương trình xác định xem số nguyên $N$ đã cho có là số Krishnamurthy hay không?

INPUT FORMAT

Một số nguyên dương $N (1 < N < 10^{8})$.

OUTPUT FORMAT

In raYES nếu số đã cho là số Krishnamurthy, in ra NO trong trường hợp ngược lại.

Ví dụ 1:

Input

Ouput

YES

Ví dụ 2:

Input

Output

NO

Giải thích ví dụ mẫu:

Ví dụ 1:
- Input: 145
- Output: YES
- Giải thích: Tổng các giai thừa của các chữ số của 145 là 1! + 4! + 5! = 145, nên 145 là số Krishnamurthy.
Ví dụ 2:
- Input: 235
- Output: NO
- Giải thích: Tổng các giai thừa của các chữ số của 235 là 2! + 3! + 5! = 2 + 6 + 120 = 128, không bằng 235, nên 235 không phải là số Krishnamurthy. <br>

Phân tích bài toán:

Bài toán yêu cầu kiểm tra xem một số nguyên dương N có phải là Số Krishnamurthy hay không. Một số là Krishnamurthy nếu tổng giai thừa của các chữ số của nó bằng chính nó.

Các bước thực hiện:

Đọc input: Đọc số nguyên dương N từ người dùng.
Lưu trữ số gốc: Bạn sẽ cần so sánh tổng giai thừa với số gốc N sau khi xử lý các chữ số. Do đó, hãy lưu trữ giá trị của N vào một biến tạm thời trước khi bắt đầu trích xuất chữ số.
Tính giai thừa các chữ số: Các chữ số có thể từ 0 đến 9. Bạn sẽ cần tính giai thừa cho từng chữ số này. Thay vì tính đi tính lại mỗi lần, bạn có thể tính trước giai thừa của các số từ 0 đến 9 và lưu trữ chúng. Một mảng (hoặc vector) có kích thước 10 là lựa chọn tốt để lưu trữ 0!, 1!, ..., 9!. Ví dụ: fact[0] = 1, fact[1] = 1, fact[2] = 2, ..., fact[9] = 362880. Việc này giúp tăng hiệu quả khi xử lý các chữ số.
Trích xuất chữ số và tính tổng giai thừa:
- Sử dụng một vòng lặp (ví dụ: while) để xử lý biến tạm chứa số. Vòng lặp này tiếp tục cho đến khi số tạm bằng 0.
- Trong mỗi lần lặp:
  - Trích xuất chữ số cuối cùng của số tạm bằng toán tử modulo (% 10).
  - Sử dụng chữ số vừa trích xuất làm chỉ mục để lấy giá trị giai thừa đã tính trước từ mảng/vector lưu trữ giai thừa.
  - Cộng giá trị giai thừa này vào một biến dùng để lưu tổng giai thừa của các chữ số.
  - Cập nhật số tạm bằng cách loại bỏ chữ số cuối cùng bằng phép chia nguyên (/ 10).
So sánh và in kết quả: Sau khi vòng lặp kết thúc (tức là đã xử lý hết tất cả các chữ số), so sánh tổng giai thừa vừa tính được với số gốc ban đầu.
- Nếu tổng bằng số gốc, in ra YES.
- Ngược lại, in ra NO.
Sử dụng std: Để đọc/ghi dữ liệu, bạn nên sử dụng cin và cout từ thư viện <iostream>.

Gợi ý cấu trúc code (không phải code hoàn chỉnh):

#include <iostream>
// Có thể cần thêm thư viện khác nếu bạn chọn cách tính giai thừa khác,
// nhưng với việc tiền tính toán và lưu vào mảng thì chỉ cần iostream là đủ cho phần chính.

int main() {
    // Sử dụng ios_base::sync_with_stdio(false); cin.tie(NULL);
    // nếu muốn tăng tốc độ nhập xuất, nhưng với N < 10^8 thì có thể không cần thiết.

    int N;
    // Đọc N

    // Lưu N gốc vào một biến khác, ví dụ: int originalN = N;

    // Khởi tạo mảng hoặc vector tiền tính giai thừa cho 0! đến 9!
    // int factorials[10];
    // factorials[0] = 1;
    // factorials[1] = 1;
    // ... tính đến factorials[9]

    // Khởi tạo biến tổng giai thừa, ví dụ: long long sumOfFactorials = 0;
    // Dùng long long để đảm bảo không tràn số, mặc dù với N < 10^8
    // và số chữ số tối đa là 8-9, tổng giai thừa (max 9! * 8 ~ 2.9e6) vẫn nhỏ hơn giới hạn int,
    // nhưng dùng long long an toàn hơn.

    // Biến tạm để xử lý các chữ số, ví dụ: int tempN = N;

    // Vòng lặp while để trích xuất chữ số từ tempN
    // while (tempN > 0) {
        // Lấy chữ số cuối cùng: digit = tempN % 10;
        // Cộng giai thừa của chữ số vào tổng: sumOfFactorials += factorials[digit];
        // Cập nhật tempN: tempN /= 10;
    // }

    // So sánh sumOfFactorials với originalN và in ra YES/NO
    // if (sumOfFactorials == originalN) {
    //     cout << "YES" << endl;
    // } else {
    //     cout << "NO" << endl;
    // }

    return 0;
}

Ưu điểm của hướng giải quyết này:

Hiệu quả tính giai thừa: Tiền tính toán và lưu giai thừa giúp việc tra cứu rất nhanh (thời gian O(1) cho mỗi chữ số), tránh lặp đi lặp lại việc tính giai thừa trong vòng lặp chính.
Đơn giản: Logic trích xuất chữ số và tính tổng khá trực quan.
Sử dụng std: Tận dụng các tính năng I/O cơ bản của thư viện chuẩn C++.

Hãy dựa vào hướng dẫn này để tự viết code hoàn chỉnh cho bài tập của bạn nhé! Chúc bạn thành công.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.