Problem
Câu đố “Tháp Hà Nội” gồm ba thanh được đánh số 1, 2, 3. Một hình chóp gồm n đĩa có đường kính khác nhau được đặt trên thanh 1 theo thứ tự đường kính tăng dần. Các đĩa có thể được chuyển từ thanh này sang thanh khác cùng một lúc, trong khi đĩa không thể được đặt trên một đĩa có đường kính nhỏ hơn. Cần phải chuyển toàn bộ kim tự tháp từ thanh 1 sang thanh 3 với số lần chuyển ít nhất.
Viết chương trình giải câu đố; đối với một số đĩa nhất định n in ra một chuỗi các hoán vị ở định dạng a b c, trong đó a — số của đĩa đã dịch chuyển, b — số thanh mà đĩa này được lấy ra, c — số thanh mà đĩa này được đặt trên đó.
Ví dụ, dòng 1 2 3 có nghĩa là di chuyển đĩa số 1 từ chân 2 sang chân 3. Một lệnh được in trên một dòng. Các đĩa được đánh số từ 1 đến n theo thứ tự đường kính tăng dần.
Đầu vào
Nhập số tự nhiên n ( 0 < n < 11).
Đầu ra
Chương trình sẽ hiển thị cách tối thiểu (về số lượng thao tác được thực hiện) để sắp xếp lại kim tự tháp từ số lượng đĩa đã cho.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
2 |
1 1 2
2 1 3
1 2 3
|
Запрещенные операторы: for; while; until