Hiểu bài toán

Bài toán yêu cầu tính giá trị của biểu thức dạng căn bậc hai lồng nhau với n dấu căn. Cụ thể, với mỗi n, ta cần tính:

S_n = sqrt(2 + sqrt(2 + sqrt(2 + ... + sqrt(2 + sqrt(2))))) (với n dấu căn)

Ví dụ:

• n=1: S_1 = sqrt(2) ≈ 1.41421
• n=2: S_2 = sqrt(2 + sqrt(2)) ≈ 1.84776
• n=3: S_3 = sqrt(2 + sqrt(2 + sqrt(2))) ≈ 1.96157

Đầu vào có T test cases (T ≤ 1000), mỗi test cho n (1 ≤ n ≤ 10000). Với mỗi test, in ra S_n được làm tròn đến 5 chữ số thập phân.

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

Cách Đệ quy trực tiếp

#include <stdio.h>
#include <math.h>

double cb2(int n) {
    if (n == 0) return 0;
    return sqrt(2 + cb2(n - 1));
}

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

• Time Complexity: O(n) mỗi test case
• Space Complexity: O(n) (độ sâu stack)

Approach này sử dụng đệ quy trực tiếp để tính giá trị. Hàm cb2(n) trả về giá trị của biểu thức với n dấu căn. Điều kiện cơ sở: n=0 trả về 0. Công thức đệ quy: cb2(n) = sqrt(2 + cb2(n-1)). Với mỗi test case, ta gọi đệ quy để tính toán. Tuy nhiên, cách này có nhược điểm: (1) Nếu T lớn và n cũng lớn, ta phải tính lại từ đầu mỗi lần, không tận dụng được kết quả trước đó. (2) Có thể gây tràn stack nếu n quá lớn (dù n ≤ 10000 vẫn an toàn trong hầu hết trường hợp).

Cách Quy hoạch động với mảng

#include <stdio.h>
#include <math.h>

int main() {
    int T, n, i;
    double a[10001];

    // Khởi tạo mảng kết quả
    a[0] = 0; // Điều kiện cơ sở
    for (i = 1; i <= 10000; i++) {
        a[i] = sqrt(2 + a[i-1]);
    }

    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%.5lf\n", a[n]);
    }
    return 0;
}

• Time Complexity: O(10000) tiền xử lý + O(T) trả lời
• Space Complexity: O(10000)

Đây là approach tối ưu nhất. Ta tiền xử lý trước toàn bộ các giá trị Sn cho n từ 1 đến 10000 và lưu vào mảng. Sau đó với mỗi test case, chỉ cần truy vấn mảng O(1). Cách này tận dụng tính chất: Sn chỉ phụ thuộc vào S_{n-1}, nên có thể tính tuần tự. Với T test case, thay vì tính lại từ đầu, ta chỉ cần lookup trong mảng đã tính sẵn.

Cách Nâng cao - Mảng động với kiểm tra biên

#include <stdio.h>
#include <math.h>

int main() {
    int T, n;
    double s = sqrt(2);
    double results[10001];

    // Precompute all possible values
    results[0] = 0;
    results[1] = s;
    for (int i = 2; i <= 10000; i++) {
        results[i] = sqrt(2 + results[i-1]);
    }

    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if (n >= 1 && n <= 10000) {
            printf("%.5lf\n", results[n]);
        }
    }
    return 0;
}

• Time Complexity: O(MAX_N) tiền xử lý + O(T)
• Space Complexity: O(MAX_N)

Phiên bản cải tiến của approach quy hoạch động. Thêm kiểm tra biên để đảm bảo n nằm trong khoảng hợp lệ. Mảng được khởi tạo với kích thước cố định 10001. Đây là implementation chi tiết và an toàn cho các trường hợp biên.

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

Bài học kinh nghiệm

• Tính chất quy hoạch động: Sn = sqrt(2 + S{n-1}), nên ta có thể tính tuần tự từ n=1 lên n cao hơn
• Với T test case, tiền xử lý toàn bộ các giá trị từ 1 đến 10000 rồi trả lời O(1) mỗi test là tối ưu
• Giá trị S_n tăng dần và có giới hạn (tiếp cận 2 khi n → ∞), nên không cần lo lắng về số quá lớn
• Sử dụng double (hoặc float) là đủ chính xác cho yêu cầu làm tròn 5 chữ số thập phân

Lỗi thường gặp

• Lỗi index trong mảng: Nếu tính a[n-1] thay vì a[n] sẽ sai với n=1
• Quên tiền xử lý: Nếu dùng đệ quy không memoization, sẽ tính lại nhiều lần gây TLE
• Kiểu dữ liệu: Dùng float thay vì double có thể mất độ chính xác khi n lớn
• Điều kiện dừng đệ quy: Sai điều kiện cơ sở (ví dụ return sqrt(2) khi n=1 thay vì n=0) có thể gây lỗi