Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Học ngay
Bài 4: Tháp Hà Nội - Chuyên đề Tin học 11 Kết nối tri thứcNă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” (La tour d’Hanoi).Tổng hợp đề thi học kì 2 lớp 11 tất cả 💝các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - SinhQuảng cáo
Lựa chọn câu để xem lời giải nhanh hơn
Câu 1 Trả lời câu hỏi khởi động trang 19 Chuyên đề Tin học 11 Kết nối tri thức
Lời giải chi tiết: Đọ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ỏ (1, 2, 3). Em có nhận xét gì về lời giải bài toán với n = 1, 2, 3? Với n = 2, ta có hai cái đĩa, ta sẽ di chuyển đĩa lớn nhất từ cọc 1 sang cọc trung gian 2, sau đó di chuyển đĩa nhỏ từ cọc 1 sang cọc đích 3, và cuối cùng di chuyển đĩa lớn từ cọc 2 sang cọc đích 3Câu 2 Trả lời câu hỏi hoạt động 1 trang 19 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: * Với n = 1, bài toán trở nên rất đơn giản, chỉ cần chuyển đĩa từ cột xuất phát sang cột đích là xong.
Câu 3 Trả lời câu hỏi 1 trang 21 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: * Với n = 1, bài toán trở nên rất đơn giản, chỉ cần chuyển đĩa từ cột xuất phát sang cột đích là xong. * Với n = 2, ta sẽ thực hiện theo các bước sau: Chuyển đĩa nhỏ từ cột xuất phát sang cột trung gian. Chuyển đĩa lớn từ cột xuất phát sang cột đích. Chuyển đĩa nhỏ từ cột trung gian sang cột đích. * Với n = 3, ta sẽ thực hiện theo các bước sau: Chuyển hai đĩa nhỏ từ cột xuất phát sang cột trung gian. Chuyển đĩa lớn từ cột xuất phát sang cột đích. Chuyển hai đĩa nhỏ từ cột trung gian sang cột đích. Chuyển đĩa nhỏ từ cột xuất phát sang cột trung gian. Chuyển đĩa lớn từ cột đích sang cột xuất phát. Chuyển đĩa nhỏ từ cột trung gian sang cột đích. Chuyển hai đĩa nhỏ từ cột xuất phát sang cột trung gian. Chuyển đĩa lớn từ cột xuất phát sang cột đích. Chuyển hai đĩa nhỏ từ cột trung gian sang cột đích.Câu 4 Trả lời câu hỏi 2 trang 21 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: * Giải trò chơi Tháp Hà Nội với n=1: Di chuyển đĩa 1 từ cọc 1 sang cọc 2. * Giải trò chơi Tháp Hà Nội với n=2: Di chuyển đĩa 1 từ cọc 1 sang cọc 3. Di chuyển đĩa 2 từ cọc 1 sang cọc 2. Di chuyển đĩa 1 từ cọc 3 sang cọc 2. * Giải trò chơi Tháp Hà Nội với n=3: Di chuyển đĩa 1 từ cọc 1 sang cọc 2. Di chuyển đĩa 2 từ cọc 1 sang cọc 3. Di chuyển đĩa 1 từ cọc 2 sang cọc 3. Di chuyển đĩa 3 từ cọc 1 sang cọc 2. Di chuyển đĩa 1 từ cọc 3 sang cọc 1. Di chuyển đĩa 2 từ cọc 3 sang cọc 2. Di chuyển đĩa 1 từ cọc 1 sang cọc 2. Nhận xét: Với n = 1, chỉ cần di chuyển một đĩa từ cọc 1 sang cọc 2. Với n = 2, ta thực hiện ba lần di chuyển. Với n = 3, ta thực hiện bảy lần di chuyển. Với mỗi tăng thêm một đĩa, số lần di chuyển tăng lên gấp đôi và cộng thêm một.Câu 5 Trả lời câu hỏi hoạt động 2 trang 21 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Ý tưởng giải bài toán Tháp Hà Nội có n đĩa từ cọc 1 sang cọc 3 như sau: Bước 1. Chuyển n - 1 đĩa từ cọc 1 sang cọc 2 lấy cọc 5 làm trung gian. Bước 2. Chuyển đĩa n từ cọc 1 sang cọc 3. Bước 3. Chuyển n - 1 đĩa từ cọc 2 sang cọc 3 lấy cọc 1 làm trung gian.Câu 6 Trả lời câu hỏi trang 22 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: 1. Di chuyển 3 đĩa từ cọc 1 sang cọc 3: 1.1 Di chuyển 2 đĩa từ cọc 1 sang cọc 2: - Di chuyển 1 đĩa từ cọc 1 sang cọc 3. - Di chuyển 1 đĩa từ cọc 1 sang cọc 2. - Di chuyển 1 đĩa từ cọc 3 sang cọc 2. 1.2. Di chuyển 1 đĩa từ cọc 1 sang cọc 3. 1.3. Di chuyển 2 đĩa từ cọc 2 sang cọc 3: - Di chuyển 1 đĩa từ cọc 2 sang cọc 1. - Di chuyển 1 đĩa từ cọc 2 sang cọc 3 - Di chuyển 1 đĩa từ cọc 1 sang cọc 3. 2. Di chuyển 1 đĩa từ cọc 1 sang cọc 2. 3. Di chuyển 3 đĩa từ cọc 3 sang cọc 2: 3.1 Di chuyển 2 đĩa từ cọc 3 sang cọc 1: - Di chuyển 1 đĩa từ cọc 3 sang cọc 2. 3.1.2 - Di chuyển 1 đĩa từ cọc 3 sang cọc 1. - Di chuyển 1 đĩa từ cọc 2 sang cọc 1. 3.2 Di chuyển 1 đĩa từ cọc 3 sang cọc 2. 3.3 Di chuyển 2 đĩa từ cọc 1 sang cọc 2: - Di chuyển 1 đĩa từ cọc 1 sang cọc 3. - Di chuyển 1 đĩa từ cọc 1 sang cọc 2. - Di chuyển 1 đĩa từ cọc 3 sang cọc 2. Vậy, tổng số bước để di chuyển 4 đĩa theo quy trình trên là: - Di chuyển 3 đĩa từ cọc 1 sang cọc 2: 7 bước - Di chuyển đĩa còn lại từ cọc 1 sang cọc 3: 1 bước - Di chuyển 3 đĩa từ cọc 2 sang cọc 3: 7 bước Vậy tổng số bước cần thiết để di chuyển 4 đĩa trong bài toán tháp Hà Nội là 15 bước.Top of FormCâu 7 Trả lời câu hỏi hoạt động 3 trang 23 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: 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.Câu 8 Trả lời câu hỏi 1 trang 24 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Để 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, ta có thể sử dụng công thức như sau: H(2) = 2 H(3) = 2 * H(2) + 1 = 2 * 2 + 1 = 5 H(4) = 2 * H(3) + 1 = 2 * 5 + 1 = 11 H(5) = 2 * H(4) + 1 = 2 * 11 + 1 = 23 Vậy H(2) = 2, H(3) = 5, H(4) = 11, H(5) = 23.Câu 9 Trả lời câu hỏi 2 trang 24 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: 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 Câu 1 Trả lời câu hỏi Luyện tập 1 trang 24 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiế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 Câu 2 Trả lời câu hỏi Luyện tập 2 trang 24 Chuyên đề Tin học 11 Kết nối tri thức
Lời giải chi tiết: Chương trình viết đúng. Thử với n = 4, kết quả thu được như sau:
Vận dụng Câu 1 Trả lời câu hỏi Vận dụng 1 trang 24 Chuyên đề Tin học 11 Kết nối tri thức H(n) = 2n - 1 bằng quy nạp toán học. Hãy tính H(64) vàꦑ so sánh với con số các bước đã được đưa ra trong tờ quảng cáo củ🐈a trò chơi vào năm 1883. Lời giải chi tiết: - Nếu chỉ có một đĩa (n=1), H(n) = 1. - Nếu có n đĩa, để chuyển tất cả các đĩa từ tháp ban đầu sang tháp đích, ta phải thực hiện các bước sau: Chuyển n-1 đĩa từ tháp ban đầu sang tháp trung gian. Chuyển đĩa cuối cùng (đĩa lớn nhất) từ tháp ban đầu sang tháp đích. Chuyển n-1 đĩa từ tháp trung gian sang tháp đích. Số bước chuyển tất cả các đĩa là H(n) = 2 * H(n-1) + 1. - Ta sẽ chứng minh công thức này bằng phương pháp quy nạp toán học: Bước 1: Giả sử công thức đúng với n-1, tức là H(n-1) = 2^(n-1) - 1 Bước 2: Chứng minh công thức đúng với n, tức là H(n) = 2^n - 1 Ta có: H(n) = 2 * H(n-1) + 1 (theo công thức đề bài) = 2 * (2^(n-1) - 1) + 1 (theo giả sử ở bước 1) = 2^n - 2 + 1 = 2^n - 1 Vậy ta đã chứng minh được công thức đúng với mọi n. Để tính H(64), ta áp dụng công thức đã chứng minh: H(64) = 2^64 - 1 = 18446744073709551615 Vậy H(64) = 18446744073709551615 trùng với con số ở trên bài báoVận dụng Câu 2 Trả lời câu hỏi Vận dụng 2 trang 24 Chuyên đề Tin học 11 Kết nối tri thức Lời giải chi tiết: Để giải bài toán Tháp Hà Nội và lưu các bước chuyển vào một danh sách, ta có thể sử dụng thuật toán đệ quy. Trong mỗi lần đệ quy, ta sẽ chuyển n-1 đĩa từ cọc ban đầu sang cọc trung gian, sau đó chuyển đĩa lớn nhất từ cọc ban đầu sang cọc đích và cuối cùng chuyển n-1 đĩa từ cọc trung gian sang cọc đích.
 Chia sẻ Bình luận
Quảng cáo
Tham Gia Group Dành Cho Lớp 11 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí |
Bài khác
