Tính S đệ quy

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Căn lồng nhau

Đề bài

Nhiệm vụ của bài tập này là xây dựng chương trình con đệ quy tính giá trị của $S$ được cho bởi công thức:

$$S(n) = \sqrt{n + \sqrt{n - 1 + \sqrt{n - 2 + \ldots + \sqrt{2 + \sqrt{1}}}}}$$

Dữ liệu vào:

• Gồm số nguyên dương $n$ $(0 \le n \le 10^4)$.

Kết quả:

• In một số duy nhất là đáp án của bài. Đáp án làm tròn 3 chữ số thập phân.

Ví dụ 1 – input

1

Ví dụ 1 – output

1.000

Ví dụ 2 – input

2

Ví dụ 2 – output

1.732

Ví dụ 3 – input

3

Ví dụ 3 – output

2.175

Lời mở đầu

Bài này là một ví dụ rất "đẹp" để tập viết hàm đệ quy: nhìn kỹ công thức sẽ thấy bên trong căn lớn nhất lại chứa đúng biểu thức của $S(n - 1)$. Mình sẽ đi từ ý tưởng tới hai cách cài đặt (đệ quy và vòng lặp), kèm khung chạy tay để các bạn thấy rõ ngăn xếp lời gọi lớn lên rồi co lại như thế nào. Bài thuộc chương Đệ quy cơ bản trên CLUE OJ (nguồn bài: VinhDinhCoder).

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngcăn lồng nhauCách 1đệ quyCách 2vòng lặpTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 100 test, mỗi test chỉ là một số $n$:

Test	n	Đáp án nhỏ nhất	Đáp án lớn nhất
1–20	1 … 20	1.000	4.987
21–100	1.167 … 9.992	34.665	100.461

• Test 1–20 lần lượt là $n = 1, 2, \ldots, 20$ (đúng thứ tự) – dùng để soát công thức.
• Test 21–100 có $n$ ngẫu nhiên từ khoảng 1.100 tới gần $10^4$ – độ sâu đệ quy lên tới gần 10.000 tầng.
• Không có test $n = 0$, nhưng code bên dưới vẫn xử lý được ($S(0) = 0$, in 0.000).

Đề không chia subtask. Mình chia 2 nhóm theo độ lớn của $n$ để xem từng cách ăn được bao nhiêu (kết quả chạy thật, giới hạn 1 giây):

Nhóm	Điều kiện	Test	Cách 1 (đệ quy)	Cách 2 (vòng lặp)	Lồng ngược (code sai)
1	$n \le 20$	1–20	20/20	20/20	1/20
2	$1000 < n \le 10^4$	21–100	80/80	80/80	0/80

Ý tưởngCăn lớn chứa căn nhỏ

Viết công thức cho vài giá trị $n$ nhỏ:

• $S(1) = \sqrt{1} = 1$
• $S(2) = \sqrt{2 + \sqrt{1}}$ $= \sqrt{2 + S(1)}$ $\approx 1{,}732$
• $S(3) = \sqrt{3 + \sqrt{2 + \sqrt{1}}}$ $= \sqrt{3 + S(2)}$ $\approx 2{,}175$

Công thức đệ quy

$S(0) = 0$ (điểm dừng) và $S(n) = \sqrt{n + S(n - 1)}$ với $n \ge 1$.

Chọn $S(0) = 0$ cho gọn: khi đó $S(1) = \sqrt{1 + 0} = 1$ đúng như đề, và trường hợp $n = 0$ cũng có đáp án $0$. Chú ý số lớn nhất $n$ nằm ở căn ngoài cùng, số $1$ nằm ở căn trong cùng – nhầm thứ tự này là sai ngay từ test 2.

Khi gọi $S(4)$, máy chưa tính được ngay mà phải gọi $S(3)$, $S(3)$ lại gọi $S(2)$, ... cho tới $S(0)$. Sau đó các giá trị được trả ngược lên. Em nhập $n$ rồi bấm Tiếp để xem ngăn xếp lời gọi:

n =

Ví dụ nhanh:

Cách 1Hàm đệ quy S(n) – $O(n)$

Viết đúng y công thức đệ quy ở trên:

C++▶ Chạy tay từng dòng codeCách 1: hàm đệ quy S(n) = √(n + S(n − 1)), xem ngăn xếp lời gọi lớn lên rồi co lại.

Dữ liệu vào (stdin) – sửa thoải mái3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. if (n == 0) return 0; là điểm dừng: thiếu dòng này hàm sẽ gọi $S(-1), S(-2), \ldots$ mãi mãi tới khi tràn ngăn xếp.
2. return sqrt(n + S(n - 1));: máy phải tính xong $S(n - 1)$ rồi mới cộng $n$ và lấy căn. Trong lúc chờ, lời gọi $S(n)$ nằm im trong ngăn xếp.
3. printf("%.3f", ...) làm tròn đúng 3 chữ số thập phân như đề yêu cầu.
4. Độ sâu đệ quy tối đa là $n + 1 \le 10001$ tầng – C++ chạy thoải mái. Bản Python phải gọi sys.setrecursionlimit(20000) vì giới hạn mặc định chỉ 1000 tầng.

Không gian$O(n)$ (ngăn xếp lời gọi)

Thời gian$O(n)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.01s. Bản Python: đúng 100/100 test; test đúng chạy lâu nhất 0.03s.

Cách 2Khử đệ quy bằng vòng lặp – $O(n)$

Nhìn vào widget ở trên: các giá trị được tính theo thứ tự $S(0) \to S(1) \to S(2) \to \ldots \to S(n)$, tức là từ căn trong cùng ra ngoài. Vậy ta chỉ cần một biến s và một vòng lặp, không cần ngăn xếp lời gọi:

C++▶ Chạy tay từng dòng codeCách 2: tính S(1), S(2), ..., S(n) bằng một vòng lặp, từ căn trong cùng ra ngoài.

Dữ liệu vào (stdin) – sửa thoải mái3

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. s lúc đầu bằng $S(0) = 0$; sau vòng lặp thứ $i$, s chính là $S(i)$.
2. Vòng lặp phải chạy từ 1 lên $n$. Nếu ai viết đệ quy kiểu f(i) = sqrt(i + f(i + 1)) bắt đầu từ $i = 1$ thì số 1 lại nằm ở căn ngoài cùng – sai đề. Mình đã thử code "lồng ngược" đó trên bộ test: chỉ đúng 1/100 test (test $n = 1$).

Không gian$O(1)$

Thời gian$O(n)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.00s. Bản Python: đúng 100/100 test; test đúng chạy lâu nhất 0.03s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Hàm đệ quy S(n)	C++	100/100	0.01s	Full điểm
	Python	100/100	0.03s	Full (nhớ tăng giới hạn đệ quy)
2. Vòng lặp từ trong ra ngoài	C++	100/100	0.00s	Full điểm
	Python	100/100	0.03s	Full điểm
Lồng ngược (1 ở ngoài cùng)	C++	1/100	0.00s	Sai công thức, chỉ đúng test n = 1

Ghi chú của mình: cả hai cách (đệ quy và vòng lặp) đều qua 100/100 test, mỗi test dưới 0,01 giây với C++. Hai lỗi hay gặp: quên điểm dừng $S(0) = 0$ và lồng căn ngược thứ tự (số 1 ở ngoài cùng). Bản Python đệ quy nhớ tăng giới hạn đệ quy vì $n$ lên tới $10^4$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇