Giáo án chuyên đề KHMT 11 kết nối: Bài 4 Bài toán Tháp Hà Nội

Trọn bộ giáo án chuyên đề tin học khoa học máy tính 11 sách kết nối tri thức cả năm file word. Giáo án bài 4 Bài toán Tháp Hà Nội. Bài soạn bám sát theo chương trình mới được trình bày khoa học, kiến thức trọng tâm, dễ dàng giảng dạy và chỉnh sửa đơn giản khi cần.

Nội dung chi tiết

Ngagrave;y soạn:hellip;/hellip;/hellip;

Ngagrave;y dạy:hellip;/hellip;/hellip;

BAgrave;I 4: BAgrave;I TOAacute;N THAacute;P HAgrave; NỘI

MỤC TIEcirc;U
Về kiến thức

Sau bagrave;i học nagrave;y, HS sẽ:

Biết vagrave; trigrave;nh bagrave;y được lời giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội sử dụng kĩ thuật đệ quy.
Thực hagrave;nh được trigrave;nh bagrave;y vagrave; lập trigrave;nh giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội.

Năng lực

Năng lực chung:

Năng lực tự chủ: Biết lựa chọn caacute;c nguồn tagrave;i liệu học tập phugrave; hợp.
Năng lực giải quyết vấn đề vagrave; saacute;ng tạo: Xaacute;c định vagrave; tigrave;m hiểu được caacute;c thocirc;ng tin liecirc;n quan đến vấn đề, đề xuất giải phaacute;p giải quyết vấn đề trong bagrave;i học.
Năng lực giao tiếp vagrave; hợp taacute;c: Thực hiện tốt nhiệm vụ trong hoạt động nhoacute;m.

Năng lực tin học:

Higrave;nh thagrave;nh, phaacute;t triển năng lực giải quyết vấn đề với sự hỗ trợ của cocirc;ng nghệ thocirc;ng tin vagrave; truyền thocirc;ng.
Sử dụng được ngocirc;n ngữ lập trigrave;nh bậc cao, qua đoacute; phaacute;t triển tư duy điều khiển vagrave; tự động hoacute;a.

Phẩm chất:

Higrave;nh thagrave;nh yacute; thức traacute;ch nhiệm, tiacute;nh cẩn thận khi lagrave;m việc nhoacute;m, phẩm chất lagrave;m việc chăm chỉ, chuyecirc;n cần để hoagrave;n thagrave;nh một nhiệm vụ.
Coacute; yacute; thức vận dụng kiến thức, kĩ năng đatilde; học ở nhagrave; trường vagrave;o thực tiễn.

THIẾT BỊ DẠY HỌC VAgrave; HỌC LIỆU
Đối với giaacute;o viecirc;n

Với bagrave;i học nagrave;y cần caacute;c cocirc;ng cụ trực quan để giuacute;p HS dễ hiểu hơn khi tiếp cận bagrave;i toaacute;n nagrave;y. Coacute; thể dugrave;ng caacute;c cocirc;ng cụ mocirc; tả caacute;c đĩa vagrave; cọc, hoặc dugrave;ng higrave;nh ảnh, hoặc dugrave;ng phần mềm mocirc; phỏng. Dưới đacirc;y lagrave; một link mocirc; phỏng như vậy:

https://scratch.mit.edu/projects/781207755/

SGK, SGV, Giaacute;o aacute;n;
Maacute;y tiacute;nh đatilde; cagrave;i đặt Python vagrave; maacute;y chiếu;
Higrave;nh ảnh, sơ đồ minh họa cho caacute;c bước thực hiện trecirc;n một mẫu dữ liệu đơn giản hoặc coacute; thể sử dụng caacute;c phần mềm mocirc; phỏng thuật toaacute;n để minh họa thecirc;m trong quaacute; trigrave;nh giảng dạy.

Đối với học sinh

SGK, vở ghi vagrave; kiến thức về Python cơ bản, kiến tức về đệ quy vagrave; hagrave;m đệ quy.

III. TIẾN TRIgrave;NH DẠY HỌC

HOẠT ĐỘNG KHỞI ĐỘNG
Mục tiecirc;u:

- HS lagrave;m quen với những hiện tượng, sự vật trong cuộc sống coacute; liecirc;n quan đến khaacute;i niệm đệ quy sẽ học trong bagrave;i.

- Kiacute;ch thiacute;ch sự tograve; mograve; cho người học.

Nội dung: GV cho caacute;c nhoacute;m HS trao đổi để nhận ra caacute;c tiacute;nh chất chung nhất của caacute;c hiện tượng, khaacute;i niệm nagrave;y vagrave; tigrave;m thecirc;m nhiều viacute; dụ khaacute;c trong thực tế
Sản phẩm học tập: HS dựa vagrave;o kiến thức vagrave; hiểu biết caacute; nhacirc;n để đưa ra cacirc;u trả lời.
Tổ chức thực hiện:

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

- GV dẫn dắt:

Năm 1883, tại một số tỉnh thagrave;nh của Việt Nam vagrave; tại Phaacute;p xuất hiện một trograve; chơi được quảng caacute;o với tecirc;n "Thaacute;p Hagrave; Nội" (La tour d'Hanoi). Trograve; chơi nagrave;yđược baacute;n rộng ratilde;i vagrave; theo một tờ quảng caacute;o vagrave;o thời

gian đoacute; lagrave; sẽ trao giải hagrave;ng triệu francs cho ai coacute;

thể giải được tất cả caacute;c mức từ thaacute;p nhất đến cao

nhất lagrave; 64 đĩa. Trong tờ rơi đoacute; cũng đưa ra con số

18 446 744 073 709 561 615 buớc chuyển cho

trường hợp 64 đĩa vagrave; khuyến caacute;o rằng sẽ cần hagrave;ng tỉ năm đẻ giải được trograve; chơi nagrave;y.

Trograve; chơi như sau: coacute; ba caacute;i cọc (viacute; dụ cọc 1, 2, 3) vagrave; n caacute;i đĩa được xếp tại cọc 1 theo thứ tự to dagrave;n từ trecirc;n xuống. Yecirc;u cầu chuyecirc;n n đĩa nagrave;y sang cọc 3 với điều kiện lagrave; được dugrave;ng cọc 2 lagrave;m trung gian, mối lằn chỉ được pheacute;p chuyển 1 đĩa vagrave; khocirc;ng cho pheacute;p đặt đĩa to chồng lecirc;n đĩa nhỏ.

Em hatilde;y suy nghĩ vagrave; thử giải trograve; chơi trecirc;n với n = 1, 2.

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

- HS lắng nghe, suy nghĩ vagrave; đưa ra cacirc;u trả lời.

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV mời HS trả lời cacirc;u hỏi.

- Caacute;c HS khaacute;c nhận xeacute;t, necirc;u yacute; kiến khaacute;c (nếu coacute;).

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

- GV nhận xeacute;t, đaacute;nh giaacute;, tuyecirc;n dương cacirc;u trả lời của HS.

- GV dẫn dắt vagrave;o nội dung bagrave;i mới: Lagrave;m thế nagrave;o để giải được bagrave;i toaacute;n Thaacute;p Hagrave; Nội bằng caacute;ch sử dụng kĩ thuật đệ quy. Hocirc;m nay chuacute;ng ta sẽ cugrave;ng tigrave;m hiểu - Bagrave;i 4: Bagrave;i toaacute;n thaacute;p Hagrave; Nội.

HOẠT ĐỘNG HIgrave;NH THAgrave;NH KIẾN THỨC

Hoạt động 1: Mocirc; tả bagrave;i toaacute;n Thaacute;p Hagrave; Nội

Mục tiecirc;u: HS biết được lời giải tường minh bằng higrave;nh ảnh của bagrave;i toaacute;n Thaacute;p Hagrave; Nội với caacute;c trường hợp nhỏ, n = 1,2,3.
Nội dung: GV yecirc;u cầu HS tigrave;m hiểu Hoạt động 1 SGK trang 19, đọc thocirc;ng tin mục 1, thảo luận nhoacute;m vagrave; xacirc;y dựng kiến thức mới.
Sản phẩm học tập: HS necirc;u được khaacute;i niệm đệ quy vagrave; trả lời được caacute;c Cacirc;u hỏi củng cố kiến thức SGK trang 21.
Tổ chức hoạt động:

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 thagrave;nh caacute;c nhoacute;m, yecirc;u cầu thảo luận để hoagrave;n thagrave;nh Hoạt động 1 SGK trang 19:

Đọc, tigrave;m hiểu bagrave;i toaacute;n Thaacute;p Hagrave; Nội vagrave; thực hiện giải trograve; chơi nagrave;y với số lượng đĩa nhỏ (1,2,3). Em coacute; nhận xeacute;t gigrave; về lời giải bagrave;i toaacute;n với n = 1, 2, 3?

- GV cho HS xem sơ đồ lời giải bagrave;i toaacute;n với caacute;c trường hợp nhỏ n = 1,2, 3 hoặc cho HS xem chương trigrave;nh mocirc; phỏng lời giải bagrave;i toaacute;n nagrave;y, từ đoacute; HS coacute; thể trao đổi, thảo luận để đưa ra caacute;c nhận xeacute;t ban đầu của migrave;nh.

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

Cacirc;u 1: Mocirc; tả lời giải bagrave;i toaacute;n với trường hợp n = 1, 2, 3 ở trecirc;n (khocirc;ng dugrave;ng higrave;nh vẽ mocirc; tả).

Cacirc;u 2: Mocirc; tả lời giải bagrave;i toaacute;n với n = 1, 2, 3 nếu yecirc;u cầu lagrave; di chuyền caacute;c đĩa từ cọc 1 Sang cọc 2 (cọc 3 lagrave; cọc trung gian).

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

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

- HS tigrave;m hiểu khaacute;i niệm đệ quy vagrave; caacute;c viacute; dụ minh họa.

- HS lagrave;m việc nhoacute;m đocirc;i để trả lời Cacirc;u hỏi củng cố kiến thức.

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

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV mời đại diện một số nhoacute;m trigrave;nh bagrave;y kết quả Hoạt động 1.

- HS xung phong phaacute;t biểu khaacute;i niệm đệ quy vagrave; necirc;u caacute;c viacute; dụ.

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

- GV mời HS nhoacute;m khaacute;c nhận xeacute;t, bổ sung.

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

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

1. Mocirc; tả bagrave;i toaacute;n Thaacute;p Hagrave; Nội

- Hoạt động 1:

Với n = 1 ta coacute; H(1) = 1

Caacute;c bước của bagrave;i toaacute;n được mocirc; tả ở higrave;nh 4.3 SGK tr20.

Với n = 2 ta coacute; H(2) = 3

Caacute;c bước của bagrave;i toaacute;n được mocirc; tả ở higrave;nh 4.4 SGK tr20.

Với n = 3 ta coacute; H(3) = 7

Caacute;c bước của bagrave;i toaacute;n được mocirc; tả ở higrave;nh 4.5 SGK tr21.

Cacirc;u hỏi:

Cacirc;u 1. Mocirc; tả bằng lời lời giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội: chuyển n dĩa từ cọc 1 sang cọc 3, lấy cọc 2 lagrave;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

Cacirc;u 2. Bagrave;i toaacute;n chuyển n đĩa từ cọc 1 sang cọc 2, lẩy cọc 3 lagrave;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 2: Yacute; tưởng lời giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội

Mục tiecirc;u: HS hiểu được yacute; tưởng thiết kế đệ quy của lời giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội.
Nội dung: GV đọc vagrave; yecirc;u cầu thực hiện Hoạt động 2 SGK trang 21, trả lời Cacirc;u hỏi SGK trang 22.
Sản phẩm học tập: HS hiểu được yacute; tưởng thiết kế đệ quy của lời giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội.
Tổ chức hoạt động:

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 thagrave;nh caacute;c nhoacute;m, yecirc;u cầu thảo luận để hoagrave;n thagrave;nh Hoạt động 2 SGK trang 21:

Đọc, trao đổi để hiểu được yacute; tưởng thiết kế đệ quy cho lời giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội.

- GV lần lượt cho caacute;c nhoacute;m lecirc;n trigrave;nh bagrave;y lời giải chỉ tiết cho caacute;c trường hợp n = 1,2, 3, từ đoacute; ruacute;t ra quy luật đệ quy. GV chốt kiến thức đưa ra sơ đồ lời giải tổng quaacute;t.

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

Viết sơ đồ chi tiết giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội cho trường hợp n = 4. Tiacute;nh H(4).

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

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

- HS lagrave;m việc nhoacute;m đocirc;i để trả lời Cacirc;u hỏi củng cố kiến thức.

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

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV mời đại diện một số nhoacute;m trigrave;nh bagrave;y kết quả Hoạt động 2.

- HS xung phong phaacute;t biểu yacute; tưởng giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội.

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

- GV mời HS nhoacute;m khaacute;c nhận xeacute;t, bổ sung.

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

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

2. Yacute; tưởng lời giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội

Đề mocirc; tả pheacute;p chuyển đĩa k từ cọc i đến cọc j chuacute;ng ta dugrave;ng kiacute; 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

rarr; Kết luận:

Yacute; tường giải bagrave;i toaacute;n Thaacute;p Hagrave; Nội coacute; 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 lagrave;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 lagrave;m trung gian.

Cacirc;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 lagrave;m trung gian.

--------------- Cograve;n tiếp ---------------