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

Trao đổi, thảo luận vagrave; tigrave;m hiểu yacute; tưởng thực hiện caacute;c tiacute;nh toaacute;n sau bằng kĩ thuật đệ quy.

1. Tiacute;nh tổng S(n)= 1+2+...+n

2. Tiacute;nh luỹ thừa =a a ... a (n lần).

3. Tiacute;nh n giai thừa

- GV yecirc;u cầu HS chia thagrave;nh caacute;c nhoacute;m vagrave; mỗi nhoacute;m thực hiện đọc, trao đổi vagrave; thực hiện giải quyết một bagrave;i toaacute;n bằng thiết kế thuật toaacute;n đệ quy.

- GV hỏi một số cacirc;u hỏi:

+ Vigrave; sao lại thiết kế lập trigrave;nh đệ quy, caacute;c viacute; dụ nagrave;y coacute; những điểm gigrave; giống nhau.

- GV đưa ra kết luận:

Yacute; tưởng chiacute;nh của kĩ thuật đệ quy lagrave; biến đổi bagrave;i toaacute;n ban đầu về bagrave;i toaacute;n với kiacute;ch thước nhỏ hơn. Nếu bagrave;i toaacute;n coacute; kiacute;ch thước nhỏ coacute; thề giải được thigrave; coacute; thề thiết lập lời giải đệ quy cho bagrave;i toaacute;n nagrave;y. Lời giải của caacute;c bagrave;i toaacute;n sử dụng kĩ thuật đệ quy thường ngắn gọn vagrave; dễ hiểu.

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

1. Hatilde;y chỉ ra phần cơ sở vagrave; phần đệ quy của caacute;c chương trigrave;nh trecirc;n.

2. Vigrave; sao trong yacute; tưởng thiết kế đệ quy trecirc;n, yecirc;u cầu từ bagrave;i toaacute;n với kiacute;ch thước lớn cần phải đưa về cugrave;ng bagrave;i toaacute;n đoacute; với kiacute;ch thước nhỏ hơn?

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

- 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. Yacute; tưởng thiết kế theo kĩ thuật đệ quy

- Hoạt động 1:

1.

2.

3.

- Cả ba bagrave;i toaacute;n trecirc;n đều coacute; chung tiacute;nh chất lagrave; từ bagrave;i toaacute;n goacute;c coacute; thẻ đưa về trường hợp coacute; tham số đầu vagrave;o nhỏ hơn. Điều đoacute; sẽ dẫn đeacute;n việc coacute; thẻ dugrave;ng Kĩ thuật đệ quy đề gọi chiacute;nh hagrave;m goacute;c. Nếu với caacute;c dữ liệu đầu vagrave;o nhỏ coacute; thẻ giải trực tiếp (viacute; dụ caacute;c bagrave;i toaacute;n trecirc;n đều coacute; lời giải cho trường hợp n = 0) thigrave; phản cơ sở của đệ quy sẽ thực hiện lời giải trực tiếp nagrave;y.

- Trong cả ba chương trigrave;nh trecirc;n, caacute;c hagrave;m được định nghĩa với tham số n mặc định phải thoả matilde;n n > 0. Do đoacute;, caacute;c hagrave;m nagrave;y khocirc;ng cần coacute; lệnh điều khiển dừng tường minh. Nhoacute;m caacute;c lệnh cơ sở sẽ lagrave;m luocirc;n chức năng kiểm soaacute;t đugrave;ng của lặp đệ quy.

Cacirc;u hỏi:

Cacirc;u 1: a) Phần cơ sở lệnh lagrave; 2,3, phần đệ quy lagrave; lệnh 5.

b) Phần cơ sở lệnh lagrave; 2,3, phần đệ quy lagrave; lệnh 5.

c) Phần cơ sở lệnh lagrave; 2,3, phần đệ quy lagrave; lệnh 5.

Cacirc;u 2: Vigrave; trong tất cả caacute;c thuật toaacute;n đệ quy đều phải coacute; yecirc;u cầu bagrave;i toaacute;n coacute; kiacute;ch thước lớn hơn đưa về cugrave;ng bagrave;i toagrave;n đoacute; với kiacute;ch thước nhỏ hơn.

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

Chuacute;ng ta đatilde; biết thuật toaacute;n tigrave;m kiềm nhị phacirc;n trecirc;n datilde;y caacute;c phần tử đatilde; sắp xếp. Hatilde;y tigrave;m thiết kế mới của thuật toaacute;n nagrave;y theo kĩ thuật đệ quy. Trao đổi, thảo luận vagrave; trả lời caacute;c cacirc;u hỏi sau:

1. Necirc;u yacute; tưởng chiacute;nh của giải thuật tigrave;m kiếm nhị phacirc;n sử dụng Kĩ thuật đệ quy.

2. Vị triacute; nagrave;o trong thuật toaacute;n coacute; thẻ gợi yacute; cho kĩ thuật đệ quy?

3. Phần cơ sở của thiết kế đệ quy nằm ở bước nagrave;o?

- GV trigrave;nh bagrave;y lại thuật toaacute;n tigrave;m kiếm nhị phacirc;n đatilde; được học trong SGK phần kiến thức thuật toaacute;n tigrave;m kiếm,

- GV đưa caacute;c cacirc;u hỏi để caacute;c nhoacute;m HS trao đổi, thảo luận về đặc điểm của thuật toaacute;n nagrave;y vagrave; caacute;c gợi yacute; để coacute; thể dẫn đến lời giải đệ quy của thuật toaacute;n. Đặc điểm quan trọng nhất của thuật toaacute;n tigrave;m kiếm nhị phacirc;n lagrave; sau mỗi bước việc tigrave;m kiếm sẽ được thu gọn lại trecirc;n miền dữ liệu coacute; độ dagrave;i bằng miền tigrave;m kiếm của bước trước. Đacirc;y chiacute;nh lagrave; gợi yacute; quan trọng nhất để dẫn đến yacute; tưởng thiết kế đệ quy.

- GV mocirc; tả thiết kế đệ quy của thuật toaacute;n vagrave; cugrave;ng caacute;c nhoacute;m thực hiện cagrave;i đặt thuật toaacute;n nagrave;y ngay trecirc;n lớp.

- GV chốt kiến thức về cocirc;ng thức truy hồi của caacute;c datilde;y số truy hồi, từ đoacute; necirc;u ra sự liecirc;n hệ với khaacute;i niệm đệ quy.

Thuật toaacute;n tigrave;m kiếm nhị phacirc;n coacute; thể biểu diễn bằng kĩ thuật đệ quy trecirc;n độ dagrave;i của dacirc;y cacirc;n tigrave;m kiếm. Mỗi lần gọi độ quy sẽ gọi hagrave;m tigrave;m kiếm trecirc;n datilde;y coacute; độ dagrave;i bằng độ dagrave;i của dacirc;y hiện tại.

- GV yecirc;u cầu HS giữ nguyecirc;n nhoacute;m, tiếp tục thảo luận để hoagrave;n thagrave;nh caacute;c bagrave;i tập trong phần Cacirc;u hỏi nhằm khắc sacirc;u kiến thức:

1. Trong chương trigrave;nh trecirc;n lệnh nagrave;o đoacute;ng vai trograve; lagrave; phần cơ sở của đệ quy?

2. Giả sử A = [1, 3, 7, 9] vagrave; K= 10. Nếu aacute;p dụng chương trigrave;nh trecirc;n thigrave; cần mấy lần gọi hagrave;m đệ quy??

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

- Caacute;c nhoacute;m HS tigrave;m hiểu kiến thức mới trong SGK.

- HS thảo luận nhoacute;m, hoagrave;n thagrave;nh bagrave;i tập phần Cacirc;u hỏi.

- GV theo dotilde;i, hỗ trợ HS trong quaacute; trigrave;nh học tập.

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

- GV mời đại diện caacute;c nhoacute;m trigrave;nh bagrave;y kết quả thảo luận của nhoacute;m migrave;nh.

- Đại diện caacute;c nhoacute;m xung phong trả lời Cacirc;u hỏi.

- Caacute;c HS cograve;n lại nhận xeacute;t, bổ sung (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, bổ sung, tuyecirc;n dương ghi điểm caacute;c nhoacute;m lagrave;m tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

2. Thuật toaacute;n tigrave;m kiếm nhị phacirc;n

Hoạt động 2

1.

2. Theo mocirc; tả ở trecirc;n, chuacute;ng ta thầy Bước 2.3 vagrave; Bước 2.4 thực hiện việc đưa bagrave;i toaacute;n tigrave;m kiềm về chiacute;nh bagrave;i toaacute;n đoacute; với caacute;c datilde;y con coacute; kiacute;ch thước nhỏ hơn, cụ thể lagrave; bằng: kiacute;ch thước datilde;y ban đầu. Như vậy, lệnh gọi đệ quy sẽ thực hiện tại caacute;c bước nagrave;y.

3. Bước 3 đoacute;ng vai trograve; phần cơ sở của đệ quy, khi độ dagrave;i của datilde;y cần tigrave;m kiếm bằng 0 thigrave; chương trigrave;nh sẽ dừng lại vagrave; thocirc;ng baacute;o khocirc;ng tim thầy.

Cacirc;u hỏi:

1. Phần cơ sở nằm ở caacute;c lệnh 10, 11 khi left > right, khi datilde;y rỗng.

2. Nếu A = [1,3,7, 9], K = 10 thigrave; lời gọi hagrave;m tigrave;m kiếm nhị phacirc;n sẽ gọi đệ quy ba lần.

Lần 1, hagrave;m sẽ gọi đệ quy đến đatilde;y [7, 9].

Lần 2, hagrave;m sẽ gọi đệ quy đến datilde;y [9].

Lần 3, hagrave;m sẽ gọi đệ quy đến datilde;y [].