Hiểu bài toán

Bài toán yêu cầu tính tổng Sn của một chuỗi các phân số có dạng 1/(i*(i+1)) với i chạy từ 1 đến n. Ví dụ, với n=3, S3 = 1/(12) + 1/(23) + 1/(3*4). Kết quả cần được in ra với độ chính xác 5 chữ số sau dấu phẩy.

Các cách tiếp cận

Cách Brute Force Simulation

#include <stdio.h>
int main()
{
    int n;
    scanf("%d", &n);
    double tong = 0;
    for (int i = 1; i <= n; i++)
    {
        tong += 1.0 / (1ll*i * (i + 1));
    }
    printf("%.5lf", tong);
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Chúng ta sử dụng một vòng lặp từ i = 1 đến n, tính giá trị của mỗi phân số 1/(i*(i+1)) và cộng dồn vào biến tổng. Để tránh lỗi số học với số nguyên, ta ép kiểu 1.0 để phép chia thực hiện dưới dạng số thực. Với n <= 10^6, cách này chạy khá nhanh (chỉ vài mili giây).

Cách Mathematical Optimization

#include <stdio.h>

int main() {
    long double n;
    scanf("%Lf", &n);
    long double res = n / (n + 1);
    printf("%.5Lf", res);
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là phương pháp tối ưu nhất dựa trên tính chất toán học của tổng. Ta có thể biến đổi tổng: 1/(i*(i+1)) = 1/i - 1/(i+1). Khi đó tổng S_n là một chuỗi bù trừ (telescoping sum): (1/1 - 1/2) + (1/2 - 1/3) + ... + (1/n - 1/(n+1)). Các số hạng中间 biến mất, chỉ còn lại 1/1 - 1/(n+1) = 1 - 1/(n+1) = n/(n+1). Do đó, ta chỉ cần đọc n và in ra kết quả n/(n+1) mà không cần vòng lặp.

Cách Naive Loop (Low Precision)

#include <stdio.h>

int main(){
    long n;
    scanf("%ld", &n);
    double s=0;
    for (double i=1;i<=n;i++) s+=1/(i*(i+1));
    printf("%.5lf",s);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng vòng lặp tương tự như phương pháp Brute Force, nhưng có một số điểm khác biệt về kiểu dữ liệu. Biến i được khai báo là double và phép chia được thực hiện khi cả hai toán hạng đều là số nguyên (trước khi ép kiểu), điều này có thể gây mất mát độ chính xác trong một số trường hợp nhất định. Tuy nhiên, với giới hạn n <= 10^6, độ sai số này thường không ảnh hưởng đến 5 chữ số thập phân đầu tiên.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được giải quyết bằng phương pháp biến đổi toán học (telescoping series) để loại bỏ hoàn toàn vòng lặp, đạt độ phức tạp O(1).
• Nếu giải bằng vòng lặp, cần đảm bảo phép chia thực hiện dưới dạng số thực (float/double) để tránh bị chia lấy phần nguyên.

Lỗi thường gặp

• Việc khai báo biến vòng lặp 'i' là số nguyên trong biểu thức '1/(i*(i+1))' sẽ dẫn đến phép chia lấy phần nguyên (integer division), trả về 0 cho tất cả các i > 1.
• Quên sử dụng '1.0' hoặc ép kiểu(double) trong phép chia会导致 kết quả sai.