Nội dung Bài tập
- Mã:
- HanoiTower
- Tên:
- Tháp Hà Nội
- Dạng thi:
- oi
- Thang điểm:
- 20 điểm
- Giới hạn thời gian:
- 3 giây
- Giới hạn bộ nhớ:
- 64 MB
- Được tạo bởi:
- nguyenvlm
- Tháp Hà Nội (Tower of Hanoi) là một trò chơi giải đố toán học kinh điển, thường được lấy làm ví dụ cho phương pháp giải toán đệ quy.
Quảng cáo
- Luật chơi:
1. Có 3 cột để đặt đĩa được gọi tên lần lượt là A, B và C.
2. Ban đầu ở cột A có n đĩa được đánh số tăng dần theo kích thước của đĩa (như hình trên).
3. Mỗi lần chỉ được di chuyển 1 đĩa và đĩa đó phải nằm trên cùng của 1 trong 3 cột.
4. Một đĩa chỉ được đặt lên đĩa lớn hơn nó (kích thước không nhất thiết phải liền kề nhau, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất).
5. Người chơi thắng khi toàn bộ n đĩa ban đầu ở cột A đã được chuyển hết sang cột C.
INPUT
Một số tự nhiên n là số đĩa cho trước ở cột A. (1 <= n <= 20)
OUTPUT
Gồm nhiều dòng là các bước giải bài toán theo cách tối ưu nhất (ít bước chuyển đĩa nhất):
Mỗi dòng có cấu trúc "k Src Dest" (không có ngoặc kép) với:
- k là một số tự nhiên đại diện cho đĩa cần chuyển.
- Src là một chữ cái in hoa đại diện cho tên cột hiện tại của đĩa k.
- Dest là mọt chữ cái in hoa đại diện cho tên cột cần chuyển đến của đĩa k.
Lưu ý: Trò chơi tháp Hà Nội với 3 cọc đã được chứng minh là luôn có duy nhất một lời giải tối ưu với mọi số tự nhiên n.
Ví dụ:
Input Output
Giải thích ví dụ:
Ban đầu ở cột A có 2 đĩa. Để chuyển 2 đĩa đó sang cột C với số bước ít nhất và tuân thủ luật chơi, ta làm như sau:
- Đầu tiên chuyển đĩa thứ 1 từ A sang B.
- Kế đến chuyển đĩa thứ 2 từ A sang C.
- Cuối cùng chuyển đĩa thứ 1 từ B sang C.
Như vậy ở cột C đã có đủ 2 đĩa, bài toán kết thúc.
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
THPT_NK_DEQUY
#include <iostream>using namespace std;int main(){ cout << "Co ga...