Bài toán Tháp Hà Nội

Buổi 05 — Hàm & Đệ quy Implementation
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Có $N$ chiếc đĩa kích thước khác nhau nằm ở cọc A, đĩa nhỏ hơn nằm trên đĩa lớn hơn. Cần chuyển toàn bộ $N$ đĩa sang cọc C bằng cách dùng cọc trung gian B, mỗi lần chỉ chuyển 1 đĩa và không được đặt đĩa lớn lên trên đĩa nhỏ. Hãy in ra tổng số bước và từng bước di chuyển theo định dạng X -> Y.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên dương $N$.

Dữ liệu ra

Dòng đầu tiên in tổng số bước di chuyển ($2^N - 1$). Các dòng tiếp theo mỗi dòng ghi một bước di chuyển dạng X -> Y.

Ví dụ
Input Output
2 3\nA -> B\nA -> C\nB -> C
1 1\nA -> C
Giới hạn

$1 \le N \le 10$.

Draft saved