Tháp Hà Nội

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Bài kinh điển

Đề bài

Trò chơi Tháp Hà Nội gồm có $3$ ngăn xếp (cọc số $1$ bên trái, số $2$ ở giữa và số $3$ bên phải) và $n$ tấm đĩa tròn có kích thước khác nhau. Lúc đầu, ngăn xếp bên trái chứa tất cả đĩa theo thứ tự tăng dần về kích thước từ trên xuống dưới đáy.

Mục tiêu là di chuyển tất cả tấm đĩa về ngăn xếp bên phải qua việc sử dụng ngăn xếp ở giữa. Ở mỗi lượt, bạn có thể chọn đĩa ở trên cùng của một ngăn xếp để chuyển nó tới một ngăn xếp khác. Ngoài ra, bạn không được phép đặt một chiếc đĩa lớn nằm trên một chiếc đĩa nhỏ hơn.

Nhiệm vụ của bạn là tìm ra lời giải sử dụng ít nước đi nhất.

Input: gồm một dòng duy nhất chứa số nguyên $n$ $(1 \le n \le 16)$ là số lượng đĩa.

Output:

• Dòng đầu tiên in số nguyên duy nhất $k$ là số lượng nước đi tối thiểu tìm được.
• Sau đó, in ra $k$ dòng miêu tả các nước đi. Mỗi dòng có hai số nguyên $a$ và $b$: bạn di chuyển tấm đĩa từ ngăn xếp $a$ sang ngăn xếp $b$.

Giới hạn thời gian: 1 giây, bộ nhớ: 512 MB. Nguồn bài: CSES – Tower of Hanoi (qua LQDOJ).

Ghi chú: đề gốc có ảnh động minh hoạ cách chơi tối ưu với $n = 5$; ở bài này mình thay bằng khung mô phỏng tự vẽ bên dưới, em chọn $n = 5$ rồi bấm Tự chạy là xem được.

Ví dụ – input

2

Ví dụ – output

3
1 2
1 3
2 3

Lời mở đầu

Tháp Hà Nội là bài toán "kinh điển nhất" của đệ quy: lời giải chỉ vài dòng, nhưng nếu thử tự chơi bằng tay với 5–6 đĩa thì rất dễ rối. Bí quyết là đừng nghĩ từng nước đi, mà hãy tin rằng "bài toán nhỏ hơn đã giải được" rồi ghép lại. Ở ví dụ với $n = 2$: chuyển đĩa nhỏ sang cọc 2, đĩa lớn sang cọc 3, rồi đĩa nhỏ từ cọc 2 sang cọc 3 – đúng 3 nước.

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ộ test16 testÝ tưởng3 bước đệ quyCodeC++ & PythonTổng kếtkết quả

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

Bộ test có 16 test, test thứ $i$ có đúng $n = i$ (đủ mọi giá trị từ 1 tới 16). Một vài dòng tiêu biểu:

Test	n	Số nước k	Số dòng output
1	1	1	2
2	2	3	4
3	3	7	8
8	8	255	256
15	15	32.767	32.768
16	16	65.535	65.536

• Mỗi $n$ chỉ có một lời giải tối ưu duy nhất, nên output phải khớp từng dòng – máy chấm so sánh y nguyên.
• Test lớn nhất in $65\,536$ dòng, nên nhớ dùng "\n" thay cho endl (mỗi endl sẽ đẩy bộ đệm ra màn hình, chậm hơn nhiều).
• Bài không chia subtask: $n \le 16$ nên lời giải đệ quy chạy chớp mắt cho mọi test.

Ý tưởngChuyển n đĩa = 2 lần chuyển (n − 1) đĩa + 1 nước

Gọi thap(n, a, b, c) là việc "chuyển $n$ đĩa trên cùng từ cọc $a$ sang cọc $c$, dùng cọc $b$ làm trung gian". Nhìn vào đĩa lớn nhất: muốn nhấc nó khỏi cọc $a$ đặt sang cọc $c$ thì $n - 1$ đĩa nhỏ phía trên phải nằm hết ở cọc còn lại là $b$. Vậy:

3 bước của thap(n, a, b, c)

1. thap(n − 1, a, c, b): chuyển $n - 1$ đĩa nhỏ từ $a$ sang $b$ (lấy $c$ làm trung gian).
2. Chuyển đĩa lớn nhất từ $a$ sang $c$ – in ra a c.
3. thap(n − 1, b, a, c): chuyển $n - 1$ đĩa nhỏ từ $b$ sang $c$ (lấy $a$ làm trung gian), đặt lên trên đĩa lớn.

Điểm dừng: $n = 0$ thì không làm gì.

Vì sao đây là ít nước nhất? Gọi $T(n)$ là số nước tối thiểu. Đĩa lớn nhất phải di chuyển ít nhất 1 lần; ngay trước lần di chuyển đầu tiên của nó, $n - 1$ đĩa kia phải nằm gọn ở cọc thứ ba (tốn $\ge T(n-1)$ nước), và sau lần di chuyển cuối của nó, chúng phải được chuyển lên trên nó (lại $\ge T(n-1)$ nước). Nên $T(n) \ge 2T(n-1) + 1$, và cách trên đạt đúng dấu bằng:

$$T(n) = 2T(n-1) + 1,\ T(0) = 0 \ \Rightarrow\ T(n) = 2^n - 1.$$

Em chọn $n$ rồi bấm Tiếp (hoặc Tự chạy) để xem từng nước đi, cùng với ngăn xếp lời gọi đệ quy ngay lúc nước đó được in ra:

Số đĩa n =

Ví dụ nhanh:

CodeCài đặt đệ quy

C++▶ Chạy tay từng dòng codeĐệ quy thap(n, a, b, c): dời n − 1 đĩa sang cọc trung gian, chuyển đĩa lớn, rồi dời n − 1 đĩa về đích.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Số nước đi $2^n - 1$ tính bằng phép dịch bit (1 << n) - 1, in trước khi gọi đệ quy (vì dòng đầu output là $k$).
2. Thứ tự tham số (n, a, b, c) = (số đĩa, cọc nguồn, cọc trung gian, cọc đích). Hai lời gọi con chỉ việc đổi vai các cọc: lần đầu đích là $b$, lần sau nguồn là $b$.
3. Điểm dừng n == 0 giúp code gọn: với $n = 1$, hai lời gọi con không làm gì, chỉ còn đúng nước a c.
4. Độ sâu đệ quy chỉ $n + 1 \le 17$ tầng; tổng số lời gọi là $2^{n+1} - 1$.
5. Bản Python gom các dòng vào danh sách rồi in một lần bằng "\n".join(...) cho nhanh.

Không gian$O(n)$ (độ sâu đệ quy)

Thời gian$O(2^n)$ – bằng số dòng phải in

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

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ú
Đệ quy chia 3 bước	C++	16/16	0.01s	Full điểm
	Python	16/16	0.04s	Full điểm

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình, giới hạn 1 giây. Bài chỉ có một cách giải chuẩn nên mình không chia nhiều cách. Điều đáng nhớ là cách nghĩ: giả sử đã biết chuyển $n - 1$ đĩa, ta chuyển được $n$ đĩa – đó chính là tinh thần của đệ quy (và quy nạp toán học).

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 😇