Xét bài toán Tháp Hà Nội trong trường hợp cọc A có một chông đĩa gồm 20 cái đĩa với n kích

Vận dụng trang 22 Chuyên đề Tin học 11Xét bài toán Tháp Hà Nội trong trường hợp cọc A có một chông đĩa gồm 20 cái đĩa với n kích thước khác nhau (mỗi kích thước có hai cái đĩa), đường kính giảm dần từ dưới lên trên. Em hãy thực hiện các yêu cầu sau:

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ài toán với n = 2 có 6 bước di chuyển đĩa. em hãy cho biết trong đó có bao nhiêu lần giải bài toán với n = 2. Nêu tên cọc xuất phát và cọc đích ở từng lần giải đó.

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) Viết hàm đệ quy giải quyết bài toán. Kết quả là hiện thị các bước di chuyển đĩa. Sau đó. 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.

Xét bài toán Tháp Hà Nội trong trường hợp cọc A có một chông đĩa gồm 20 cái

Xét bài toán Tháp Hà Nội trong trường hợp cọc A có một chông đĩa gồm 20 cái

Xét bài toán Tháp Hà Nội trong trường hợp cọc A có một chông đĩa gồm 20 cái

Trả lờ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.

Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Cánh diều hay, chi tiết khác:

Bài 2: Thuật toán đệ quy

Bài 3: Thực hành thiết kế thuật toán đệ quy

Bài 4: Thực hành tổng hợp thiết kế thuật toán đệ quy

Bài 1: Ý tưởng chia để trị

Bài 2: Kĩ thuật đệ quy trong chia để trị

Bài 3: Thực hành ứng dụng thuật toán tìm kiếm nhị phân bằng đệ quy