Đây là bài hướng dẫn các bài tập lập trình dành cho sinh viên năm nhất, với hạn chót nộp bài là 17:09 ngày 31 tháng 10.

Bài 1150: Thuốc lá của Peter

Tổng quan thuật toán

Bài toán này chủ yếu kiểm tra kỹ năng sử dụng thuật toán mô phỏng. Thuật toán mô phỏng thường áp dụng cho các bài toán cơ bản, đưa các tình huống thực tế vào dạng bài lập trình. Yêu cầu của bài toán là bạn cần thực hiện từng bước theo đúng mô tả. Tuy nhiên, cần lưu ý rằng thuật toán mô phỏng cũng dễ gây ra lỗi, đặc biệt là các lỗi liên quan đến biên.

Mã nguồn

#include <iostream>

int main() {
    int so_luong_thuoc = 0; // Tổng số thuốc có thể đổi được
    int n, m; // n: số lượng thuốc ban đầu, m: số bao thuốc cần để đổi 1 điếu
    std::cin >> n >> m;

    int dau_thuoc = 0; // Biến tạm lưu số lượng đầu thuốc sau mỗi lần đổi
    while (n > 0) { // Tiếp tục vòng lặp khi còn thuốc để hút
        so_luong_thuoc += n; // Cộng số thuốc hiện có vào tổng số thuốc
        dau_thuoc += n;      // Số thuốc vừa hút trở thành đầu thuốc
        
        int thuoc_moi = dau_thuoc / m; // Số thuốc mới đổi được từ đầu thuốc
        dau_thuoc -= thuoc_moi * m;    // Số đầu thuốc còn lại sau khi đổi
        n = thuoc_moi;                // Cập nhật số lượng thuốc hiện có
    }

    std::cout << so_luong_thuoc << std::endl;
    return 0;
}

Lưu ý: Trong C++, phép chia giữa hai số nguyên sẽ thực hiện phép chia lấy phần nguyên (làm tròn xuống). Ví dụ: 4 / 3 sẽ cho kết quả là 1, không phải 1.33333.

Bài 1035: Tính tổng chuỗi số

Tổng quan thuật toán

Bài toán này cũng sử dụng thuật toán mô phỏng. Bạn chỉ cần viết chương trình thực hiện đúng công thức được đưa ra trong đề bài. Lưu ý: Công thức có chứa phép chia, do đó nên sử dụng kiểu dữ liệu số thực (double) để đảm bảo độ chính xác cho việc mô phỏng công thức.

Mã nguồn

#include <iostream>

int main() {
    int k; // Giá trị k cho trước
    std::cin >> k;

    double phan_tu_tu = 1.0;  // Tử số của các phân số trong chuỗi, luôn là 1
    int mau_so = 1;         // Mẫu số của các phân số, cũng là số thứ tự của hạng tử
    double tong_chuoi = 0.0; // Biến lưu tổng các hạng tử trước đó

    // Tiếp tục vòng lặp khi tổng các hạng tử trước đó vẫn nhỏ hơn hoặc bằng k
    while (tong_chuoi <= k) {
        tong_chuoi += phan_tu_tu / mau_so; // Cộng hạng tử hiện tại vào tổng chuỗi
        mau_so++;                         // Tăng mẫu số cho hạng tử tiếp theo
    }

    // Vì tong_chuoi là tổng của (mau_so - 1) hạng tử, nên kết quả là mau_so - 1
    std::cout << mau_so - 1 << std::endl; 
    return 0;
}

Lưu ý: Phép chia số thực khác với phép chia số nguyên. Trong C++, phép chia có một toán hạng là số thực sẽ giữ lại phần thập phân.

• Chia hai số nguyên: 3 / 4 = 0, 4 / 3 = 1.
• Chia số nguyên cho số thực hoặc ngược lại: 3 / 4.0 = 0.75, 4 / 3.0 = 1.33....
• Chia hai số thực: tương tự trường hợp trên, giữ lại độ chính xác.

Bài 1075: Phân tích thừa số nguyên tố

Tổng quan thuật toán

Bài toán này liên quan đến kiến thức toán học cơ bản về số nguyên tố. Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước số là 1 và chính nó. Đề bài yêu cầu tìm hai thừa số nguyên tố của một số cho trước, sau đó trả về thừa số nguyên tố lớn hơn.

Ví dụ: 21 = 3 * 7. Cả 3 và 7 đều là số nguyên tố. Số nguyên tố lớn hơn là 7, vậy kết quả là 7.

Quan trọng: Một số chỉ có thể phân tích thành tích của hai số nguyên tố (vì số nguyên tố không thể phân tích tiếp).

Phân tích chi tiết

Do giá trị của N có thể lên tới 2 * 10^9, trong khi C++ chỉ có thể thực hiện khoảng 10^7 đến 10^8 phép tính mỗi giây, chúng ta cần một phương pháp tối ưu để tránh bị Time Limit Exceeded (TLE).

Chúng ta biết rằng nếu tìm được một thừa số nguyên tố nhỏ, chúng ta có thể dễ dàng tìm được thừa số nguyên tố lớn hơn (vì tích của chúng là N). Hơn nữa, bình phương của thừa số nguyên tố nhỏ hơn sẽ luôn nhỏ hơn hoặc bằng N.

Giả sử thừa số nguyên tố nhỏ là x và thừa số nguyên tố lớn là y, với x * y = N và x <= y. Ta có x * x <= x * y = N. Điều này có thể được chứng minh bằng phản chứng:

Giả sử x * x > N, mà ta có x < y. Theo tính chất bắc cầu của bất đẳng thức, ta có N < x * x < x * y. Vì x * y = N, điều này dẫn đến mâu thuẫn N < N. Do đó, giả thiết ban đầu là sai, và ta phải có x * x <= N.

Việc chứng minh này giúp tối ưu hóa độ phức tạp thời gian tính toán của chúng ta.

Mã nguồn

#include <iostream>

int main() {
    int n; // Số cần phân tích
    std::cin >> n;

    // Bắt đầu tìm ước số nguyên tố nhỏ nhất từ 2.
    // Điều kiện i * i <= n tương đương với i <= n / i
    for (int i = 2; i * i <= n; ++i) { 
        if (n % i == 0) { // Nếu i là ước của n, thì i là thừa số nguyên tố nhỏ
            // n / i chính là thừa số nguyên tố lớn còn lại
            std::cout << n / i << std::endl; 
            return 0; // Kết thúc chương trình ngay lập tức
        }
    }
    
    // Trường hợp đặc biệt: Nếu n là số nguyên tố hoặc chỉ có 1 ước số nhỏ hơn sqrt(n)
    // (ví dụ n=7, vòng lặp trên không tìm thấy ước nào, thì n tự nó là số nguyên tố lớn nhất)
    // Tuy nhiên, đề bài đảm bảo n có thể phân tích thành 2 thừa số nguyên tố,
    // nên trường hợp này thường không xảy ra nếu n không phải là số nguyên tố.
    // Nếu n là số nguyên tố, thì theo logic bài toán, nó không có 2 thừa số nguyên tố khác nhau.
    // Với các bài toán dạng này, n thường là hợp số.
    
    return 0; 
}