Hiểu bài toán

Bài toán yêu cầu tính giá trị của biểu thức lồng nhau gồm n dấu căn bậc hai: Sn = sqrt(1 + sqrt(2 + sqrt(3 + ... + sqrt(n - 1 + sqrt(n))...))). Với mỗi test case gồm một số nguyên dương n, ta cần tính giá trị Sn và làm tròn đến 5 chữ số thập phân. Dữ liệu输入: T (số lượng test) ≤ 100, n ≤ 1000.

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

Cách Hàm Đệ Quy (Recursive)

double S(int n) {
    if (n == 1) return 1.0;
    return sqrt(n + S(n - 1));
}

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

Đây là cách biểu diễn trực tiếp nhất của công thức toán học. Hàm S(n) gọi đệ quy S(n-1) cho đến khi đạt tới cơ sở S(1)=1. Với n tối đa 1000, độ sâu đệ quy là 1000, đủ an toàn trong hầu hết các môi trường lập trình thi đấu (thường có giới hạn stack khoảng 1-8MB). Tuy nhiên, cách này tiêu tốn bộ nhớ cho các khung stack.

Cách Vòng Lặp Ngược (Iterative Bottom-Up)

double can(int n) {
    double result = sqrt(n);
    for(int i = n - 1; i > 0; i--) {
        result = sqrt(i + result);
    }
    return result;
}

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

Phương pháp này tính toán từ trong ra ngoài (từ n xuống 1). Ban đầu gán result = sqrt(n), sau đó lặp từ n-1 về 1, cập nhật result = sqrt(i + result). Đây là cách hiệu quả nhất về bộ nhớ, không dùng đệ quy, và logic tính toán rất rõ ràng.

Cách Vòng Lặp Xuống Dưới (Iterative Top-Down)

double loopSqrt(int n) {
    double sum = 0;
    while(n >= 1) {
        sum += n;
        sum = sqrt(sum);
        n--;
    }
    return sum;
}

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

Cách tiếp cận này mô phỏng phép tính từ trong ra ngoài nhưng theo hướng từ trên xuống dưới. Nó tích lũy giá trị vào biến sum và thực hiện sqrt sau mỗi bước. Ví dụ: với n=3, nó sẽ tính sqrt(3) -> sqrt(2 + sqrt(3)) -> sqrt(1 + sqrt(2 + sqrt(3))). Logic này đúng nhưng hơi trừu tượng hơn so với cách lặp ngược từ n về 1.

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

Bài học kinh nghiệm

• Công thức toán học có tính chất đệ quy tự nhiên: S(n) = sqrt(n + S(n-1)).
• Với n ≤ 1000, độ phức tạp O(n) là hoàn toàn chấp nhận được (1000 phép tính là rất nhỏ).
• Lặp ngược (từ n về 1) là cách tối ưu nhất về cả thời gian và bộ nhớ (O(1) space) so với đệ quy.

Lỗi thường gặp

• Lỗi logic tính toán: Phải thực hiện phép tính từ trong ra ngoài (hoặc từ dưới lên). Ví dụ, không thể tính sqrt(1+2) rồi sqrt(3+...) mà phải tính sqrt(n) trước, rồi dùng kết quả đó cho phép tính involving n-1.
• Sai kiểu dữ liệu: Phải dùng double cho giá trị tính toán để đảm bảo độ chính xác. Dùng int sẽ gây lỗi số học.
• Định dạng output: Yêu cầu in ra 5 chữ số thập phân. Ở C/C++, dùng %.5lf (hoặc %.5f).