Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 4: Bài toán Tháp Hà Nội
Tải giáo án điện tử Chuyên đề học tập Tin học 11 - Khoa học máy tính (kết nối tri thức) Bài 4: Bài toán Tháp Hà Nội. Bộ giáo án chuyên đề được thiết kế sinh động, đẹp mắt. Thao tác tải về đơn giản, dễ dàng sử dụng và chỉnh sửa. Thầy, cô kéo xuống để xem chi tiết.
Xem: => Giáo án tin học 11 theo định hướng khoa học máy tính kết nối tri thức
Click vào ảnh dưới đây để xem 1 phần giáo án rõ nét












Xem toàn bộ: Giáo án điện tử chuyên đề Tin học 11 - Khoa học máy tính Kết nối tri thức
CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC MỚI!
KHỞI ĐỘNG
Hình 4.1. Tờ quảng cáo trò chơi “Tháp Hà Nội”, 1883
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" (La tour d'Hanoi). Trò chơi này được bán rộng rãi và theo một tờ quảng cáo vào thời gian đó là sẽ trao giải hàng triệu francs cho ai có thể giải được tất cả các mức từ thấp nhất đến cao nhất là 64 đĩa.
Trong tờ rơi đó cũng đưa ra con số 18 446 744 073 709 561 615 bước chuyển cho trường hợp 64 đĩa và khuyến cáo rằng sẽ cần hàng tỉ năm để giải được trò chơi này. Trò chơi như sau: có ba cái cọc (ví dụ cọc 1, 2, 3) và n cái đĩa được xếp tại cọc 1 theo thứ tự to dàn từ trên xuống. Yêu cầu chuyên n đĩa này sang cọc 3 với điều kiện là được dùng cọc 2 làm trung gian, mối lằn chỉ được phép chuyển 1 đĩa và không cho phép đặt đĩa to chồng lên đĩa nhỏ.
Em hãy suy nghĩ và thử giải trò chơi trên với n = 1, 2.
BÀI 4.
BÀI TOÁN THÁP HÀ NỘI
NỘI DUNG BÀI HỌC
Mô tả bài toán
1
Ý tưởng lời giải
2
Thiết lập chương trình
3
Mô tả bài toán
Tháp Hà Nội
1
Đọ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?
Hoạt động 1
Tìm hiểu bài toán Tháp Hà Nội
Hình 4.2. Bài toán Tháp Hà Nội
- Với n = 1 ta có H(1) = 1
- Với n = 2 ta có H(2) = 3
- Với n = 3 ta có H(3) = 7
Đọc thông tin và trả lời câu hỏi:
Câu 1: Mô tả lời giải bài toán với trường hợp n = 1, 2, 3 ở trên (không dùng hình vẽ mô tả).
Câu 2: 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 1 Sang cọc 2 (cọc 3 là cọc trung gian).
Hướng dẫn trả lời
1
Mô tả bằng lời lời giải bài toán Tháp Hà Nội: chuyển n dĩa từ cọc 1 sang cọc 3, lấy cọc 2 làm trung gian.
Với n = 1, chỉ cần 1 bước.
Với n = 2, cần 2 bước.
- Chuyển đĩa 1 từ cọc 1 sang cọc 2
- Chuyển đĩa 2 từ cọc 1 sang cọc 3
- Chuyển đĩa 1 từ cọc 2 sang cọc 3
Với n = 3, cần 6 bước
- Chuyển đĩa 1 từ cọc 1 sang cọc 3
- Chuyển đĩa 2 từ cọc 1 sang cọc 2
- Chuyển đĩa 1 từ cọc 3 sang cọc 2
- Chuyển đĩa 3 từ cọc 1 sang cọc 3
- Chuyển đĩa 1 từ cọc 2 sang cọc 1
- Chuyển đĩa 2 từ cọc 2 sang cọc 3
- Chuyển đĩa 1 từ cọc 1 sang cọc 3
2
Bài toán chuyển n đĩa từ cọc 1 sang cọc 2, lẩy cọc 3 làm trung gian.
Với n=2
- Chuyển đĩa 1 từ cọc 1 sang cọc 3
- Chuyển đĩa 2 từ cọc 1 sang cọc 2
- Chuyển đĩa 1 từ cọc 3 sang cọc 2
Với n=3
- Chuyển đĩa 1 từ cọc 1 sang cọc 2
- Chuyển đĩa 2 từ cọc 1 sang cọc 3
- Chuyển đĩa 1 từ cọc 2 sang cọc 3
- Chuyển đĩa 3 từ cọc 1 sang cọc 2
- Chuyển đĩa 1 từ cọc 3 sang cọc 1
- Chuyển đĩa 2 từ cọc 3 sang cọc 2
- Chuyển đĩa 1 từ cọc 1 sang cọc 2
Ý tưởng lời giải bài toán Tháp Hà Nội
2
Đọ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.
Hoạt động 2
Tìm hiểu ý tưởng thiết kế đệ quy cho lời giải bài toán Tháp Hà Nội
a. Trường hợp n = 1
Với n = 1, tại cọc 1 có một đĩa duy nhất, chúng ta sẽ chuyển đĩa này sang cọc 3.
b. Trường hợp n = 2
Với n = 2, chúng ta có hai đĩa đánh số 1, 2 tại cọc 1.
c. Trường hợp n = 3
Có ba đĩa đánh số 1, 2, 3. Lời giải của trường hợp này sẽ sử dụng kết quả của trường hợp n=2
1
Chuyển 2 đĩa từ cọc 1 sang cọc 2 lấy cọc 3 làm trung gian.
2
Chuyển đĩa 3 từ cọc 1 sang cọc 3.
3
Chuyển 2 đĩa từ cọc 2 sang cọc 3 lấy cọc 1 làm trung gian.
KẾT LUẬN
Ý 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:
1
Chuyền n - 1 đĩa từ cọc 1 sang cọc 2 lấy cọc 3 làm trung gian.
2
Chuyển đĩa n từ cọc 1 sang cọc 3.
3
Chuyển n -1 đĩa từ cọc 2 sang cọc 3 lấy cọc 1 làm trung gian.
Viết sơ đồ chi tiết giải bài toán Tháp Hà Nội cho trường hợp n = 4. Tính H(4).
- Sơ đồ lời giải cho n = 4. Chuyển n đĩa từ cọc 1 sang cọc 3, lấy cọc 2 làm trung gian.
Thiết lập chương trình giải bài toán Tháp Hà Nội
3
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:
- Các đĩa đánh số từ 1 đến n và có kích thước tăng dần.
- Mỗi lần chỉ được phép di chuyển một đĩa.
- Không được phép xếp đĩa to lên trên đĩa nhỏ.
Hoạt động 3
Thiết lập thuật toán và cài đặt chương trình cho bài toán Tháp Hà Nội
Hướng dẫn thực hiện
Lời giải đệ quy của bài toán Tháp Hà Nội như sau:
- Nếu n = 1 thì thực hiện chuyển đĩa 1 từ cọc i sang cọc j.
- Nếu n > 1 thì thực hiện theo ba bước như sau:
Bước 1: Chuyển n - 1 đĩa phía trên (từ 1 đến n - 1) từ cọc ¡ sang cọc k lấy cọc j làm trung gian.
Bước 2: Chuyển đĩa n từ cọc i sang cọc j.
Bước 3: Chuyển n - 1 đĩa từ cọc k sang cọc j lấy cọc i làm trung gian.
1 def Hanoi(n, i, j, k): 2 if n == 1: 3 chuyển đĩa n từ cọc i sang cọc j 4 else: 5 Hanoi (n-1, i, k, j) 6 chuyển đĩa n từ cọc i sang cọc j 7 Hanoi(n-1, k, j, i) |
Mã giả của bài toán
--------------- Còn tiếp ---------------
Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II
Hệ thống có đầy đủ các tài liệu:
- Giáo án word (350k)
- Giáo án Powerpoint (400k)
- Trắc nghiệm theo cấu trúc mới (200k)
- Đề thi cấu trúc mới: ma trận, đáp án, thang điểm..(200k)
- Phiếu trắc nghiệm câu trả lời ngắn (200k)
- Trắc nghiệm đúng sai (250k)
- Lý thuyết bài học và kiến thức trọng tâm (200k)
- File word giải bài tập sgk (150k)
- Phiếu bài tập để học sinh luyện kiến thức (200k)
Nâng cấp lên VIP đê tải tất cả ở tài liệu trên
- Phí nâng cấp VIP: 800k
=> Chỉ gửi 450k. Tải về dùng thực tế. Nếu hài lòng, 1 ngày sau mới gửi phí còn lại
Cách nâng cấp:
- Bước 1: Chuyển phí vào STK: 1214136868686 - cty Fidutech - MB(QR)
- Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo và nhận tài liệu
Xem toàn bộ: Giáo án điện tử chuyên đề Tin học 11 - Khoa học máy tính Kết nối tri thức
ĐẦY ĐỦ GIÁO ÁN CÁC BỘ SÁCH KHÁC
GIÁO ÁN WORD LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN POWERPOINT LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN CHUYÊN ĐỀ LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN DẠY THÊM 11 KẾT NỐI TRI THỨC
CÁCH ĐẶT MUA:
Liên hệ Zalo: Fidutech - nhấn vào đây