Gọi Hanoi(n, i, j, k) là bài toán yêu cầu chuyển n đĩa đang xếp ở cọc i sang cọc j lấy cọc k làm trung gian

Giải Chuyên đề Tin 11 Bài 4: Tháp Hà Nội - Kết nối tri thức

Hoạt động 3 trang 23 Chuyên đề Tin học 11: Gọi Hanoi(n, i, j, k) là bài toán yêu cầu chuyển n đĩa đang xếp ở cọc i sang cọc j lấy cọc k làm trung gian. Các đĩa được đánh số từ 1 đến n và xếp theo thứ tự từ trên xuống. Các điều kiện của việc chuyển như sau:

1. Các đĩa đánh số từ 1 đến n và có kích thước tăng dần.

2. Mỗi lần chỉ được phép chuyển một đĩa.

3. Không được phép xếp đĩa to lên trên đĩa nhỏ.

Em hãy thiết kế thuật toán đệ quy tổng quát cho bài toán trên. Yêu cầu phải mô tả chi tiết từng bước chuyển.

Lời giải:

Mô tả chi tiết từng bước chuyển như sau:

1. Khi n = 1:

Di chuyển đĩa từ cọc i sang cọc j.

2. Khi n > 1:

- Bước 1: Chuyển n - 1 đĩa từ cọc i sang cọc k:

Gọi lại thuật toán Hanoi(n-1, i, k, j) để chuyển n - 1 đĩa từ cọc i sang cọc k.

- Bước 2: Chuyển đĩa lớn nhất từ cọc i sang cọc j:

Di chuyển đĩa từ cọc i sang cọc j.

- Bước 3: Chuyển n - 1 đĩa từ cọc k sang cọc j:

Gọi lại thuật toán Hanoi(n-1, k, j, i) để chuyển n - 1 đĩa từ cọc k sang cọc j.

Lời giải bài tập Chuyên đề Tin 11 Bài 4: Tháp Hà Nội hay, chi tiết khác:

• Khởi động trang 19 Chuyên đề Tin học 11: Năm 1883, tại một số tỉnh thành của Việt Nam và tại Pháp xuất hiện một trò chơi được quảng cáo với tên “Tháp Hà Nội” ....

• Hoạt động 1 trang 19 Chuyên đề Tin học 11: Đọc, tìm hiểu bài toán Tháp Hà Nội và thực hiện giải trò chơi này với số lượng đĩa nhỏ ....

• Câu hỏi 1 trang 21 Chuyên đề Tin học 11: Mô tả lời giải bài toán với trường hợp n = 1, 2, 3 ....

• Câu hỏi 2 trang 21 Chuyên đề Tin học 11: Mô tả lời giải bài toán với n = 1, 2, 3 nếu yêu cầu là di chuyển các đĩa từ cọc ....

• Hoạt động 2 trang 21 Chuyên đề Tin học 11: Đọc, trao đổi để hiểu được ý tưởng thiết kế đệ quy cho lời giải bài toán Tháp Hà Nội ....

• Câu hỏi trang 22 Chuyên đề Tin học 11: Viết sơ đồ chi tiết giải bài toán Tháp Hà Nội cho trường hợp n = 4 ....

• Câu hỏi 1 trang 24 Chuyên đề Tin học 11: Tính các giá trị H(2), H(3), H(4), H(5) của bài toán Tháp Hà Nội ....

• Câu hỏi 2 trang 24 Chuyên đề Tin học 11: Viết chương trình đệ quy để tính giá trị H(n) của bài toán Tháp Hà Nội ....

• Luyện tập 1 trang 24 Chuyên đề Tin học 11: Viết chương trình giải bài toán Tháp Hà Nội nhưng với tên các cọc là A, B, C ....

• Luyện tập 2 trang 24 Chuyên đề Tin học 11: Viết chương trình rút gọn của hàm Hanoi(n, i, j, k) như sau ....

• Vận dụng 1 trang 24 Chuyên đề Tin học 11: Hãy chứng minh công thức H(n)= 2^n - 1 bằng quy nạp toán học ....

• Vận dụng 2 trang 24 Chuyên đề Tin học 11: Giả sử cần lưu dãy các bước chuyển của bài toán Tháp Hà Nội vào một danh sách ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 11 Kết nối tri thức hay, chi tiết khác:

• Chuyên đề Tin học 11 Bài 5: Thực hành thiết kế thuật toán theo kĩ thuật đệ quy

• Chuyên đề Tin học 11 Bài 6: Ý tưởng và kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 9: Sắp xếp trộn

Săn SALE shopee Tết:

• Mỹ phẩm SACE LADY giảm tới 200k
• SRM Simple tặng tẩy trang 50k
• Combo Dầu Gội, Dầu Xả TRESEMME 80k

---