CHUYEcirc;N ĐỀ 1: THỰC HAgrave;NH THIẾT KẾ THUẬT TOAacute;N THEO KĨ THUẬT ĐỆ QUY

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

Quan saacute;t mocirc; higrave;nh datilde;y số được tạo ra (Higrave;nh 1.4) vagrave; trả lời cacirc;u hỏi:

+ Datilde;y số được tạo ra theo quy luật nagrave;o?

+ Em hatilde;y xaacute;c định higrave;nh vagrave; datilde;y số trong trường hợp n = 6.

- GV yecirc;u cầu HS tigrave;m hiểu khaacute;i niệm đệ quy trong saacute;ch, sau đoacute; tigrave;m hiểu thecirc;m viacute; dụ khaacute;c từ thực tế để hiểu sacirc;u hơn định nghĩa vagrave; yacute; nghĩa của khaacute;i niệm đệ quy. Tigrave;m caacute;c viacute; dụ để thấy nếu khocirc;ng dugrave;ng định nghĩa đệ quy thigrave; sẽ rất khoacute; trigrave;nh bagrave;y đuacute;ng về khaacute;i niệm đoacute;.

- 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: Trường hợp nagrave;o sau đacirc;y khocirc;ng coacute; tiacute;nh chất đệ quy?

+ Cacirc;u 2: Phaacute;t biểu nagrave;o sau đacirc;y sai về đệ quy?

A. Một đối tượng được gọi lagrave; đệ quy nếu noacute; hoặc một phần của noacute; được định nghĩa thocirc;ng qua khaacute;i niệm về chiacute;nh noacute;.

B. Đối tượng đệ quy thigrave; sự vật, hiện tượng liecirc;n quan đến đối tượng sẽ được lặp lại nhiều lần.

C. Trong đệ quy, lời giải của một bagrave;i toaacute;n phụ thuộc vagrave;o lời giải của caacute;c trường hợp nhỏ hơn cả cugrave;ng một bagrave;i toaacute;n.

D. Đệ quy lagrave; caacute;ch gọi khaacute;c của lặp.

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. Khaacute;i niệm đệ quy

- Hoạt động 1:

+ Higrave;nh 1.4 lagrave; mocirc; higrave;nh để tiacute;nh tổng datilde;y số tự nhiecirc;n từ 1 đến k. Higrave;nh caacute;c ocirc; vuocirc;ng bước thứ k + 1 được thiết lập bằng caacute;ch bổ sung thecirc;m phiacute;a dưới mẫu higrave;nh thứ k một hagrave;ng gồm k + 1 ocirc; vuocirc;ng (k = 1, 2,...)

rarr; tiacute;nh chất của mẫu higrave;nh lagrave; bước sau coacute; sử dụng lại mocirc; higrave;nh của bước trước.

+ Higrave;nh vagrave; datilde;y số trong trường hợp n = 6 lagrave;:

f(6) = (1 + 2 + 3 + 4 + 5) + 6 = 21

= f(5) + 6

- Khaacute;i niệm đệ quy: Khi một sự vật, hiện tượng coacute; tiacute;nh chất lặp lại chiacute;nh noacute; hoặc được định nghĩa theo chiacute;nh sự vật, hiện tượng đoacute; thigrave; được gọi lagrave; đệ quy.

- Viacute; dụ:

+ Datilde;y số tự nhiecirc;n coacute; thể định nghĩa đơn giản như sau:

a) Số 0 lagrave; số tự nhiecirc;n.

b) Nếu n lagrave; số tự nhiecirc;n thigrave; n + 1 cũng lagrave; số tự nhiecirc;n.

+ Datilde;y Fibonacci F(n) được định nghĩa đơn giản như sau:

a) F_shy;0 = 0, F₁ = 1

b) F_n = F_{n - 1} + F_{n - 2} với n > 1.

Cacirc;u hỏi:

Cacirc;u 1: Trường hợp D khocirc;ng coacute; tiacute;nh chất đệ quy.

Cacirc;u 2: Đaacute;p aacute;n D sai.

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 3 nhoacute;m, yecirc;u cầu mỗi nhoacute;m tigrave;m hiểu một datilde;y số nổi tiếng để phaacute;t hiện caacute;c đặc điểm tương tự giữa caacute;c cocirc;ng thức nagrave;y vagrave; khaacute;i niệm đệ quy.

+ Nhoacute;m 1: Tigrave;m hiểu datilde;y số Fibonacci

+ Nhoacute;m 2: Tigrave;m hiểu datilde;y số Lucas

+ Nhoacute;m 3: Tigrave;m hiểu datilde;y số Pell

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

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

+ Cacirc;u 1: Em hatilde;y xaacute;c định phần cơ sở vagrave; phần đệ quy của n!.

+ Cacirc;u 2: Em hatilde;y xaacute;c định phần cơ sở vagrave; phần đệ quy của xⁿ.

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

- Caacute;c nhoacute;m HS tigrave;m hiểu mỗi datilde;y số đatilde; necirc;u 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. Cocirc;ng thức truy hồi

a) Datilde;y số Fibonacci

- Cocirc;ng thức:

+ Phần cơ sở: F_shy;0 = 0, F₁ = 1

+ Phần truy hồi: F_n = F_{n - 1} + F_{n - 2} với n > 1.

b) Datilde;y số Lucas

- Cocirc;ng thức:

+ Phần cơ sở: L_shy;0 = 2, L₁ = 1

+ Phần truy hồi: L_n = L_{n - 1} + L_{n - 2} với n > 1.

c) Datilde;y số Pell

- Cocirc;ng thức:

+ Phần cơ sở: P_shy;0 = 0, P₁ = 1

+ Phần truy hồi: P_n = 2P_{n - 1} + P_{n - 2} với n > 1.

rarr; Kết luận:

- Tất cả caacute;c cocirc;ng thức truy hồi đều coacute; hai phần: phần cơ sở để xaacute;c định caacute;c giaacute; trị ban đầu vagrave; phần truy hồi để tiacute;nh caacute;c phần tử tiếp theo.

- Tất cả caacute;c datilde;y số được định nghĩa thocirc;ng qua cocirc;ng thức truy hồi chiacute;nh lagrave; được định nghĩa bằng khaacute;i niệm đệ quy.

Cacirc;u hỏi:

Cacirc;u 1:

- Phần cơ sở: 0! = 1, 1! = 1.

- Phần đệ quy: n! = n times; (n - 1)!

Cacirc;u 2:

- Phần cơ sở: x⁰ = 1

- Phần đệ quy: xⁿ = x times; x^{n - 1}