Đề

Cọc A có ~n~ đĩa, đĩa to ở dưới, đĩa nhỏ ở trên. Cần chuyển cả chồng sang cọc C, mỗi lần chuyển một đĩa, không được đặt đĩa to lên trên đĩa nhỏ, được dùng cọc B làm trung gian.

Viết hàm đệ quy so_buoc(n) trả về số lần chuyển ít nhất (với ~n = 0~ trả về 0).

Gợi ý. Để chuyển ~n~ đĩa từ A sang C: chuyển ~n - 1~ đĩa trên cùng từ A sang B, chuyển đĩa to nhất từ A sang C, rồi chuyển ~n - 1~ đĩa từ B sang C. Hai lần chuyển ~n - 1~ đĩa tốn cùng một số bước.

Chương trình chính đọc T số ~n~, với mỗi số in số bước.

Dữ liệu vào

• Dòng đầu: số nguyên ~T~.
• ~T~ dòng tiếp theo, mỗi dòng một số nguyên ~n~ là số đĩa.

Kết quả

~T~ dòng; dòng thứ ~i~ là số bước ít nhất cho số đĩa thứ ~i~.

Ràng buộc

• ~1 \le T \le 100~.
• ~0 \le n \le 30~.

Ví dụ

Dữ liệu vào:

3
1
3
10

Kết quả:

1
7
1023

Giải thích ví dụ

Gọi ~S(n)~ là số bước ít nhất. Theo gợi ý: ~S(0) = 0~ và ~S(n) = S(n-1) + 1 + S(n-1) = 2\,S(n-1) + 1~.

Với ~n = 3~: chuyển 2 đĩa nhỏ sang B (3 bước), đĩa to nhất sang C (1 bước), 2 đĩa từ B sang C (3 bước): 3 + 1 + 3 = 7.

Ghi chú

• Hiệu năng. Viết đúng nguyên văn gợi ý thành hai lời gọi so_buoc(n - 1) + 1 + so_buoc(n - 1) thì kết quả đúng, nhưng mỗi tầng nhân đôi số lời gọi: ~n = 30~ cần hơn 2 tỉ lời gọi, bị Time Limit — giống hàm fib đệ quy ở mục 5.6.2. Hãy tính ~S(n-1)~ một lần rồi dùng lại.
• Đề cho phép ~n = 0~: hàm chỉ có trường hợp cơ sở n == 1 sẽ gọi so_buoc(-1), so_buoc(-2), … và dừng với RecursionError (Runtime Error).
• Máy chấm chỉ so kết quả, không kiểm được hàm có đệ quy hay không; yêu cầu "viết hàm đệ quy" là phần giảng viên kiểm khi chấm tay.

Nguồn trong sách: Bài C5-12, mục 5.10, giáo trình "Lập trình cơ sở với Python" — TS. Nguyễn Quốc Long · Mức: (****)