Đảo ngược đệ quy

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Xâu

Đề bài

Cho một xâu kí tự $s$. Ta gọi xâu đảo ngược của $s$ là xâu có được khi viết $s$ theo thứ tự ngược lại. Ví dụ s = Huy thì xâu đảo ngược của nó là yuH.

Nhiệm vụ của bài tập này là xây dựng chương trình con đệ quy tìm và in ra màn hình xâu đảo ngược của một xâu kí tự được cho.

Dữ liệu vào:

Gồm một xâu kí tự có độ dài không quá $5000$.

Kết quả:

In ra xâu đảo ngược của xâu đã cho.

Ví dụ 1 – input

Huy

Ví dụ 1 – output

yuH

Ví dụ 2 – input

UYEN

Ví dụ 2 – output

NEYU

Lời mở đầu

Đảo ngược xâu thì dùng vòng lặp hay reverse là xong, nhưng bài này yêu cầu viết hàm đệ quy – một bài tập rất tốt để hiểu thứ tự "đi xuống – quay về" của đệ quy. Mình sẽ trình bày 2 cách đệ quy khác nhau, và chỉ ra một cái bẫy ở khâu đọc dữ liệu khiến rất nhiều bạn sai gần hết test. 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ưởngin khi quay về Cách 1rev(i)Cách 2rev(l, r)Tổng kếtkết quả

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

Bộ test có 100 test, mỗi test là một dòng gồm chữ cái, chữ số và dấu cách:

Test	Độ dài xâu	Số test có dấu cách	Có dấu cách ở đầu/cuối	Tỉ lệ dấu cách
1–30	3 … 10	24	11	24%
31–100	5.000	70	30	25%

Trừ 2 test của đề (Huy, UYEN), tất cả các test đều có dấu cách, nhiều test có dấu cách ngay ở đầu hoặc cuối xâu.
Test 31–100 có độ dài đúng $5000$ – đệ quy sâu 5000 tầng.

Cái bẫy: xâu có dấu cách

Nếu đọc bằng cin >> s thì máy chỉ lấy tới dấu cách đầu tiên (một "từ"). Phải đọc cả dòng bằng getline(cin, s). Mình đã thử bản dùng cin >> s: chỉ đúng 9/100 test.

Đề không chia subtask, mình chia 2 nhóm theo độ dài (kết quả chạy thật, giới hạn 1 giây):

Nhóm	Điều kiện	Test	Đọc bằng `cin >> s` (code sai)	Cách 1 (in khi quay về)	Cách 2 (đổi chỗ 2 đầu)
1	độ dài $\le 10$	1–30	9/30	30/30	30/30
2	độ dài $= 5000$	31–100	0/70	70/70	70/70

Ý tưởngMuốn in ngược s[i..], hãy in ngược phần sau trước

Gọi rev(i) là hàm in ngược đoạn $s[i], s[i+1], \ldots, s[n-1]$ (với $n$ là độ dài xâu). Xâu ngược của đoạn này gồm: xâu ngược của đoạn $s[i+1..n-1]$, rồi tới ký tự $s[i]$ ở cuối cùng. Vậy:

Hàm đệ quy rev(i)

Nếu $i = n$ (đoạn rỗng): không in gì, return. Đây là điểm dừng.
Ngược lại: gọi rev(i + 1) trước, sau khi nó xong mới in $s[i]$.

Mấu chốt là dòng in nằm sau lời gọi đệ quy: lúc đi xuống ($rev(0) \to rev(1) \to \ldots$) chưa ai in gì; tới đáy rồi các lời gọi lần lượt quay về và in $s[n-1], s[n-2], \ldots, s[0]$ – đúng thứ tự ngược. Em nhập xâu rồi bấm Tiếp để xem:

Xâu s =

Ví dụ nhanh:

Thử đổi chỗ 2 dòng (in $s[i]$ trước rồi mới gọi rev(i + 1)) thì xâu sẽ được in xuôi – các bạn thử nghĩ xem vì sao nhé.

Cách 1Gọi đệ quy trước, in sau – $O(n)$

C++▶ Chạy tay từng dòng codeCách 1: rev(i) gọi rev(i + 1) trước rồi mới in s[i] – in ngược khi các lời gọi quay về.

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

Dữ liệu mẫu:

getline(cin, s) đọc cả dòng, giữ nguyên mọi dấu cách.
Xâu s khai báo toàn cục để hàm rev dùng được mà không phải truyền xâu vào mỗi lần gọi (truyền string theo giá trị sẽ phải sao chép xâu ở mỗi tầng, rất chậm).
Độ sâu đệ quy $n + 1 \le 5001$ tầng – C++ không vấn đề gì. Bản Python phải tăng giới hạn bằng sys.setrecursionlimit (mặc định chỉ 1000 tầng) và gom ký tự vào list rồi in một lần.

Không gian$O(n)$ (ngăn xếp)

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.02s.

Cách 2Đổi chỗ 2 đầu, đảo phần giữa – $O(n)$

Cách khác: muốn đảo đoạn $s[l..r]$ thì đổi chỗ $s[l]$ và $s[r]$, rồi đảo tiếp đoạn bên trong $s[l+1..r-1]$. Dừng khi $l \ge r$ (đoạn rỗng hoặc chỉ còn 1 ký tự). Cách này sửa trực tiếp xâu thành xâu ngược rồi mới in, rất tiện nếu sau đó còn cần dùng xâu đã đảo.

C++▶ Chạy tay từng dòng codeCách 2: đổi chỗ 2 đầu s[l], s[r] rồi đảo tiếp đoạn bên trong.

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

Dữ liệu mẫu:

Gọi rev(0, s.size() - 1). Chú ý ép (int)s.size() trước khi trừ 1: nếu xâu rỗng, s.size() - 1 kiểu không dấu sẽ thành một số rất lớn.
Độ sâu đệ quy chỉ khoảng $n / 2$ tầng.

Không gian$O(n)$ (ngăn xếp)

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ú
Đọc bằng `cin >> s`	C++	9/100	0.00s	Chỉ đọc được từ đầu tiên
1. Gọi đệ quy trước, in sau	C++	100/100	0.00s	Full điểm
	Python	100/100	0.02s	Full (nhớ tăng giới hạn đệ quy)
2. Đổi chỗ 2 đầu rồi đảo phần giữa	C++	100/100	0.00s	Full điểm
	Python	100/100	0.03s	Full (nhớ tăng giới hạn đệ quy)

Ghi chú của mình: cả 2 cách đệ quy đều qua 100/100 test, mỗi test vài mili giây. Lỗi chết người của bài là đọc xâu bằng cin >> s – xâu trong test có dấu cách nên phải dùng getline. Với Python nhớ sys.setrecursionlimit vì xâu dài 5000.

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 😇

Lập Trình Thuật Toán