Giả sử cần lưu dãy các bước chuyển của bài toán Tháp Hà Nội vào một danh sách để có thể sử dụng lại về sau. Mỗi bước chuyển dạng k: i → j sẽ được lưu trong một bộ ba số (k, i, j). Viết chương trình giải bài toán Tháp Hà Nội tổng quát Hanoi(n, i, j, k) chuyển n đĩa từ cọc i sang cọc j lấy cọc k làm trung gian với yêu cầu lưu tất cả các bước chuyển vào một danh sách (list). Như vậy, hàm Hanoi(n, i, j, k) sẽ trả về một danh sách bao gồm các bộ ba số dạng như đã mô tả ở trên.

Viết sơ đồ chi tiết giải bài toán Tháp Hà Nội cho trường hợp n = 4. Tính H(4).

Hãy chứng minh công thức $H\left(n\right)=2^n-1$ bằng quy nạp toán học. Hãy tính H(64) và so sánh với con số các bước đã được đưa ra trong tờ quảng cáo của trò chơi vào năm 1883.

Tính các giá trị H(2), H(3), H(4), H(5) của bài toán Tháp Hà Nội.

Đọc, tìm hiểu bài toán Tháp Hà Nội và thực hiện giải trò chơi này với số lượng đĩa nhỏ (1, 2, 3). Em có nhận xét gì về lời giải bài toán với n = 1, 2, 3?

Viết chương trình giải bài toán Tháp Hà Nội nhưng với tên các cọc là A, B, C.

Gọi Hanoi(n, i, j, k) là bài toán yêu cầu chuyển n đĩa đang xếp ở cọc i sang cọc j lấy cọc k làm trung gian. Các đĩa được đánh số từ 1 đến n và xếp theo thứ tự từ trên xuống. Các điều kiện của việc chuyển như sau:

1. Các đĩa đánh số từ 1 đến n và có kích thước tăng dần.

2. Mỗi lần chỉ được phép chuyển một đĩa.

3. Không được phép xếp đĩa to lên trên đĩa nhỏ.

Em hãy thiết kế thuật toán đệ quy tổng quát cho bài toán trên. Yêu cầu phải mô tả chi tiết từng bước chuyển.