Hiểu bài toán

Bài toán yêu cầu tính giá trị của một biểu thức liên phân số có độ sâu n. Biểu thức được định nghĩa đệ quy: $Sn = \frac{1}{1 + S{n-1}}$ với $S0 = 1$ (hoặc $S1 = \frac{1}{1+1} = \frac{1}{2}$ tùy cách diễn giải, nhưng các ví dụ và code mẫu chỉ ra $Sn$ là phân số có n dấu gạch chéo, bắt đầu từ $S1 = 1/(1+1)$). Dữ liệu đầu vào gồm T số test, mỗi test cho số nguyên dương n (1 ≤ n ≤ 10). Với mỗi n, in ra giá trị $S_n$ làm tròn đến 5 chữ số thập phân.

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

Cách Mảng động (Precomputation)

#include <stdio.h>

int main() {
    int t;
    scanf("%d", &t);
    // Mảng lưu kết quả, chỉ số từ 0 đến 10
    double res[11];
    // Khởi tạo giá trị cơ sở
    res[0] = 1.0;
    // Tính toán trước cho tất cả n có thể
    for (int i = 1; i <= 10; i++) {
        res[i] = 1.0 / (1.0 + res[i-1]);
    }
    while (t--) {
        int n;
        scanf("%d", &n);
        // In kết quả tương ứng với n
        printf("%.5f\n", res[n]);
    }
    return 0;
}

• Time Complexity: O(T + N_max)
• Space Complexity: O(N_max)

Phương pháp này tính toán trước các giá trị của $S_n$ và lưu vào mảng. Vì n chỉ tới 10, ta có thể tính hết trong một vòng lặp trước khi xử lý các test case. Cách tiếp cận này đảm bảo tốc độ nhanh nhất cho mỗi test case (chỉ mất O(1) để truy cập kết quả).

Cách Đệ quy (Recursion)

#include <stdio.h>

double Sn(int n) {
    if (n == 1) return 1.0 / 2.0;
    return 1.0 / (1.0 + Sn(n - 1));
}

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%.5f\n", Sn(n));
    }
    return 0;
}

• Time Complexity: O(T * N)
• Space Complexity: O(N)

Sử dụng hàm đệ quy trực tiếp để tính $Sn$ dựa trên công thức truy hồi $Sn = \frac{1}{1 + S_{n-1}}$. Với mỗi test case, máy tính sẽ gọi đệ quy cho đến khi chạm tới cơ sở $n=1$. Do n rất nhỏ, đệ quy không gặp vấn đề tràn stack.

Cách Vòng lặp (Iteration)

#include <stdio.h>

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        double val = 1.0;
        for (int i = 1; i <= n; i++) {
            val = 1.0 / (1.0 + val);
        }
        printf("%.5f\n", val);
    }
    return 0;
}

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

Giải quyết bài toán bằng cách mô phỏng chính xác quá trình tính toán bằng vòng lặp. Biến val được khởi tạo bằng 1.0 (tương ứng $S_0$) và được cập nhật n lần theo công thức.

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

Bài học kinh nghiệm

• Bài toán là một dãy số truy hồi đơn giản. Với n nhỏ (≤ 10), mọi phương pháp đều hiệu quả.
• Giá trị $S_n$ nhanh chóng hội tụ về một giá trị khoảng 0.618 (tỷ lệ vàng), nhưng với n nhỏ ta cần tính chính xác từng bước.

Lỗi thường gặp

• Lỗi định dạng in (phải in ra 5 chữ số thập phân, dùng %.5f).
• Lỗi logic index: Solution 3 của người dùng dùng a[n-1] vì họ khởi tạo a[0] là $S_1$. Cần thống nhất logic index với công thức tính.