Giải chuyên đề Tin 11 Cánh diều Bài 4. Thực hành tổng hợp thiết kế thuật toán đệ quy có đáp án
24 người thi tuần này 4.6 546 lượt thi 2 câu hỏi
Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Dành cho bạn Hot
Danh sách câu hỏi:
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
Các Hình 1,2,3 lần lượt minh hoạ các bước di chuyển đĩa cần thực hiện khi số đĩa n = 1,2,3.
Với n = 1: Ta chỉ cần duy nhất một bước di chuyển đĩa từ cọc A sang cọc C.
Với n = 2: Ta cần 3 bước di chuyển đĩa.
Với n = 3: Ta cần 7 bước di chuyển đĩa
a) Trong quá trình di chuyển đĩa gồm 7 bước với n=3, nhận thấy bài toán Tháp Hà Nội cho trường hợp n=2 được giải hai lần: lần giải đầu tiên bởi ba bước 1, 2, 3 và lần giải thứ hai bởi ba bước 5, 6, 7. Sau ba bước 1, 2, 3 hai đĩa trên cùng của cọc A được chuyển sang cọc B. Do đó, ở lần giải đầu tiên này, cọc A được gọi là cọc xuất phát, cọc B được gọi là cọc đích. Em hãy nêu tên cọc xuất phát và cọc đích ở lần giải thứ hai tương ứng với ba bước 5, 6, 7.
b) Với n = 4, giả sử đã chuyển được ba đĩa trên cùng của cọc A sang cọc B. Em hãy thực hiện tiếp các bước để cả 4 đĩa đều ở cọc C và cho biết khi giải bài toán Tháp Hà Nội với n = 4 ta cần giải bao nhiêu lần bài toán này với n = 3.
c) Xây dựng thuật toán đệ quy giải quyết bài toán Tháp Hà Nội với n đĩa và cài đặt thuật toán đề xuất bằng một hàm đệ quy.
d) Viết chương trình yêu cầu người dùng nhập vào số lượng đĩa n và gọi hàm đệ quy đã xây dựng được, để hướng dẫn người chơi các bước di chuyển đĩa. Sau đó, em hãy chạy thử chương trình với các giá trị n lần lượt là 3, 4, 5 để kiểm thử chương trình.
Đăng nhập để xem lời giải
Lưu tiến độ và luyện tập hiệu quả hơn. Hoàn toàn miễn phí!
Lời giải
a) Hình 4 và 5 minh hoạ cách di chuyển đĩa với n = 1 và n = 2 tương ứng.
b) Khi giải bài toán với n = 3 thì phải giải bài toán với n nhỏ hơn nào, nêu tên cọc xuất phát và cọc đích ở từng lần giải đó.
c) Chạy hàm này với n lần lượt là 3, 4, 5 và kiểm tra kết quả thu được.
Đăng ký để học cùng Vietjack. Hoàn toàn miễn phí!
Bằng việc đăng ký, bạn đồng ý với Điều khoản sử dụng và Chính sách bảo mật của Vietjack.
Nhắn tin Zalo
Hỏi bài tập