Nội dung Bài tập
- Mã:
- DeQuy
- Tên:
- Đệ Quy
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Nguồn bài tập:
- 22120417
- Được tạo bởi:
- 22120417
Bài toán gồm 3 cột (đóng vai trò như 3 chỗ đặt đĩa), n đĩa được đánh số từ 1 đến n, có kích thước khác nhau, đặt trên cột 1 sao cho đĩa nhỏ ở trên và đĩa lớn ở dưới. Yêu cầu di chuyển toàn bộ n đĩa từ cột 1 sang cột 3 sao cho không đặt đĩa lớn hơn lên đĩa nhỏ hơn trong quá trình di chuyển các đĩa.
Quảng cáo
Giải thuật:
Input:Với n > 1, các bước 1 và 3 được thực hiện bằng cách đệ quy với n-1 thay cho n
- Bước 1: Di chuyển n-1 đĩa từ cột 1 sang cột 2
- Bước 2: Di chuyển đĩa thứ n từ cột 1 sang cột 3
- Bước 3: Di chuyển n-1 đĩa từ cột 2 sang cột 3
Số đĩa n (n<10)
Output:
- Dòng 1 in ra số lần ít nhất để chuyển đĩa
Hướng dẫn di chuyển các đĩa để chuyển tất cả sang cột 3 với định dạng sau: Chuyen dia d tu cot x sang cot y
Ví dụ:
Input
Output
1
1
Chuyen dia 1 tu cot 1 sang cot 3
Ví dụ:
Input
Output
2
3
Chuyen dia 1 tu cot 1 sang cot 2
Chuyen dia 2 tu cot 1 sang cot 3
Chuyen dia 1 tu cot 2 sang cot 3
Ví dụ:
Input
Output
3
7
Chuyen dia 1 tu cot 1 sang cot 3
Chuyen dia 2 tu cot 1 sang cot 2
Chuyen dia 1 tu cot 3 sang cot 2
Chuyen dia 3 tu cot 1 sang cot 3
Chuyen dia 1 tu cot 2 sang cot 1
Chuyen dia 2 tu cot 2 sang cot 3
Chuyen dia 1 tu cot 1 sang cot 3
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...