Soạn giáo án chuyên đề Khoa học máy tính 11 kết nối tri thức Bài 4: Bài toán Tháp Hà Nội

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 1 SGK trang 19:

Đọ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?

- GV cho HS xem sơ đồ lời giải bài toán với các trường hợp nhỏ n = 1,2, 3 hoặc cho HS xem chương trình mô phỏng lời giải bài toán này, từ đó HS có thể trao đổi, thảo luận để đưa ra các nhận xét ban đầu của mình.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi để củng cố kiến thức:

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).

Bước 2: HS thực hiện nhiệm vụ học tập

- HS chia nhóm, thảo luận để trả lời Hoạt động 1 SGK trang 19.

- HS tìm hiểu khái niệm đệ quy và các ví dụ minh họa.

- HS làm việc nhóm đôi để trả lời Câu hỏi củng cố kiến thức.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện một số nhóm trình bày kết quả Hoạt động 1.

- HS xung phong phát biểu khái niệm đệ quy và nêu các ví dụ.

- GV gọi 1 - 2 HS trả lời Câu hỏi.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, tổng kết, chuyển sang nội dung tiếp theo.

1. Mô tả bài toán Tháp Hà Nội

- Hoạt động 1:

Với n = 1 ta có H(1) = 1

Các bước của bài toán được mô tả ở hình 4.3 SGK tr20.

Với n = 2 ta có H(2) = 3

Các bước của bài toán được mô tả ở hình 4.4 SGK tr20.

Với n = 3 ta có H(3) = 7

Các bước của bài toán được mô tả ở hình 4.5 SGK tr21.

Câu hỏi:

Câu 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

Câu 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

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 2 SGK trang 21:

Đọ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.

- GV lần lượt cho các nhóm lên trình bày lời giải chỉ tiết cho các trường hợp n = 1,2, 3, từ đó rút ra quy luật đệ quy. GV chốt kiến thức đưa ra sơ đồ lời giải tổng quát.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi để củng cố kiến thức:

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).

Bước 2: HS thực hiện nhiệm vụ học tập

- HS chia nhóm, thảo luận để trả lời Hoạt động 2 SGK trang 21.

- HS làm việc nhóm đôi để trả lời Câu hỏi củng cố kiến thức.

- GV hướng dẫn, theo dõi, hỗ trợ HS khi cần.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện một số nhóm trình bày kết quả Hoạt động 2.

- HS xung phong phát biểu ý tưởng giải bài toán Tháp Hà Nội.

- GV gọi 1 - 2 HS trả lời Câu hỏi.

- GV mời HS nhóm khác nhận xét, bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- GV nhận xét, tổng kết, chuyển sang nội dung tiếp theo.

2. Ý tưởng lời giải bài toán Tháp Hà Nội

Đề mô tả phép chuyển đĩa k từ cọc i đến cọc j chúng ta dùng kí hiệu sau:

k:i j //chuyển đĩa k từ cọc i sang cọc j.

a) Trường hợp n = 1

1: 1 3

b) Trường hợp n = 2

1: 1 2

2: 1 3

1: 2 3

c) Trường hợp n = 3

Bước 1:

1: 1 3

2: 1 2

1: 3 2

Bươc 2:

3: 1 3

Bước 3:

1: 2 1

2: 2 3

1: 1 3

→ 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:

Bước 1. Chuyền n - 1 đĩa từ cọc 1 sang cọc 2 lấy cọc 3 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 hỏi:

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.