Hiểu bài toán

Bài toán yêu cầu tính tổng Sn của một dãy số, trong đó mỗi phần tử thứ i là phân số 1/(1+2+...+i). Ta cần tính Sn cho T bộ test, mỗi test cho n (1 ≤ n ≤ 10^6, T ≤ 10^5). Kết quả cần làm tròn đến 8 chữ số thập phân.

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

Cách Công thức toán học (Tối ưu)

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        // S_n = 2 * (1 - 1/(n+1)) = 2 * n / (n+1)
        double ans = 2.0 * n / (n + 1);
        printf("%.8lf\n", ans);
    }
    return 0;
}

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

Đây là phương pháp hiệu quả nhất. Ta nhận thấy tử số của mỗi hạng tử là 1, còn mẫu số là tổng số tự nhiên từ 1 đến i, tức là i(i+1)/2. Vậy mỗi hạng tử có dạng 2/(i(i+1)). Sử dụng kỹ thuật phân rã phân thức, ta có: 2/(i(i+1)) = 2(1/i - 1/(i+1)). Khi thực hiện tổng hợp từ i=1 đến n, các hạng tử triệt tiêu lẫn nhau (telescoping sum), kết quả còn lại là 2(1 - 1/(n+1)) = 2n/(n+1). Với n dưới 10^6, phép chia số thực này rất nhanh và chính xác.

Cách Mô phỏng (Simulation)

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        double sum = 0.0;
        double triangular_sum = 0.0;
        for (int i = 1; i <= n; i++) {
            triangular_sum += i; // Tính tổng 1+2+...+i
            sum += 1.0 / triangular_sum;
        }
        printf("%.8lf\n", sum);
    }
    return 0;
}

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

Phương pháp này tính trực tiếp tổng theo định nghĩa. Với mỗi i, ta tính tổng các số từ 1 đến i (tổng tam giác), rồi cộng dồn 1/xác tổng đó vào biến sum. Độ phức tạp là O(n) cho mỗi test case. Với T=10^5 và n=10^6, tổng số phép toán là 10^11, quá lớn để chạy trong thời gian giới hạn (thường là 1 giây). Do đó, phương pháp này không khả thi.

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

Bài học kinh nghiệm

• Mẫu số của phân tử thứ i là tổng các số tự nhiên từ 1 đến i, có công thức i(i+1)/2.
• Phân tử thứ i có dạng 2/(i(i+1)).
• Sử dụng kỹ thuật 'Telescoping Sum' (tổng triệt tiêu) bằng cách phân rã phân thức để rút gọn biểu thức tổng S_n về công thức 2n/(n+1).

Lỗi thường gặp

• Làm tròn sai số: Cần dùng %.8lf để in ra đúng 8 chữ số thập phân.
• Kiểu dữ liệu: Nên dùng double để tính toán để đảm bảo độ chính xác.
• Sai công thức tổng quát: Không nhận ra mối liên hệ với tổng tam giác và không áp dụng được phép biến đổi toán học.