Số lần chuyển tối thiểu của Tháp Hà Nội

Gọi H(n) là số lần chuyển đĩa tối thiểu, với n≥1. Một đĩa cần H(1)=1. Với n>1, hai pha chuyển chồng n−1 đĩa cần H(n−1) lần mỗi pha; chuyển đĩa lớn nhất thêm một lần: $$H(n)=2H(n-1)+1.$$ Để thấy vì sao không thể dùng ít hơn, xét đĩa lớn nhất. Trước lần chuyển đầu tiên của nó, n−1 đĩa nhỏ phải được gom trên cọc còn lại, cần ít nhất H(n−1) lần. Sau lần cuối đưa đĩa lớn nhất vào đích, lại phải chuyển chồng n−1 đĩa nhỏ lên nó, cần ít nhất H(n−1) lần. Đĩa lớn nhất phải chuyển ít nhất một lần. Cách giải ba pha đạt đúng tổng đó, nên đạt số lần chuyển tối thiểu.

Có thể viết riêng hàm tính số lần chuyển theo truy hồi: ```python def H(n): if n == 1: return 1 return 2 * H(n - 1) + 1 ``` Hàm này nhận n≥1 và chỉ trả một số. Với n=64, kết quả là 18 446 744 073 709 551 615. Tính con số ấy bằng hàm đếm hoặc 2**64−1 không có nghĩa đã thực hiện hay lưu từng ấy lần chuyển. Bản tạo danh sách phải lưu toàn bộ các bộ ba, nên không dùng để thử 64 đĩa.

Dùng tệp Python ở bài trước và chạy: ```text python3 g11-cs-thap-ha-noi.py 64 --count-only ``` Cần nhận đúng dòng `H(64) = 18446744073709551615`, không có dòng chuyển đĩa. Cờ --count-only chọn hàm đếm và bỏ phần tạo danh sách. Mẫu chế độ này nhận n từ 1 đến 512 để kiểm nhỏ với giới hạn đệ quy Python đang dùng; giới hạn của mẫu không phải giới hạn toán học của công thức. Với n=4, có thể so sánh số đếm 15 với độ dài danh sách của lời giải nhỏ. Không tăng giới hạn đệ quy hoặc chạy bộ liệt kê với n lớn để kiểm một công thức có thể tính trực tiếp.