Giáo án điện tử chuyên đề Khoa học máy tính 11 cánh diều Bài 1: Khái niệm đệ quy và ví dụ

CHÀO MỪNG CÁC EM ĐẾN VỚI BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Trong toán học, n giai thừa (kí hiệu n!) là tích của n số nguyên dương đầu tiên n! = n × (n – 1) × … × 1. Vậy ta có thể dùng công thức sau đây để tính n! được không?

KHỞI ĐỘNG

Công thức có thể dùng tính n! vì:

• Nếu n = 0 → 0! = 1.
• Nếu n  1, n  (n – 1)! = n  (n – 1)  … 1 = n!

CHUYÊN ĐỀ 1. THỰC HÀNH THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT ĐỆ QUY

BÀI 1.

KHÁI NIỆM ĐỆ QUY VÀ VÍ DỤ

NỘI DUNG BÀI HỌC

1

Một số ví dụ về đệ quy

Khái niệm và các thành phần cơ bản trong định nghĩa đệ quy

2

…

…

…

…

01

MỘT SỐ VÍ DỤ VỀ ĐỆ QUY

Thảo luận nhóm: Đọc thông tin và thực hiện nhiệm vụ ở mỗi trạm theo nội dung như sau:

Trạm 1

Xác định các công thức toán học mang tính đệ quy thông qua đọc thông tin mục 1 trang 5,6 và trả lời câu hỏi 1 phần Hoạt động trang 6 sách CĐHT.

Trạm 2

Ví dụ sự vật, sự việc, hiện tượng mang tính đệ quy trong đời sống hàng ngày và mô tả chúng.

Trong toán học có rất nhiều công thức được định nghĩa thông qua chính nó ở phiên bản nhỏ hơn

Công thức mang tính đệ quy

Ví dụ: Công thức sinh dãy số Fibonacci 0, 1, 1, 2, 3, 5, 8, 13,…

(1)

Hai công thức sau đều được sử dụng để tính số cách chọn k phần từ từ n phần tử:

(2)

(3)

Theo em, trong hai công thức (2) và (3), công thức nào là công thức mang tính đệ quy? Em hãy giải thích cho lựa chọn của mình.

(3)

Hướng dẫn thực hiện

→ Sử dụng công thức (3) để tiếp tục tính toán ta có:

Không có điểm dừng

(3)

Công thức (3) mang tính đệ quy

• Trong cuộc sống hằng ngày, có rất nhiều sự việc, hiện tượng, cách giải quyết một vấn đề được mô tả dưới góc nhìn mang tính đệ quy.
• Ví dụ: bộ búp bê Nga Matryoshka

Hình 1. Bộ búp bê Matryoshka

1

+1

+1

+1

+1

+1

Hình 2. Cách đếm số búp của bộ Matryoshka

…

…

…

…

02

KHÁI NIỆM VÀ CÁC THÀNH PHẦN CƠ BẢN TRONG ĐỊNH NGHĨA ĐỆ QUY

2. Hàm dem_Bupbe (búp bê A) ở Hình 3 được sử dụng để mô tả cách đếm số búp bê của bộ Matryoshka một cách đệ quy nếu búp bê A là búp bê lớn nhất của bộ. Em hãy cho biết dấu trong hàm dem_Bupbe (búp bê A) cần được thay bằng gì.

?

Hình 3. Hàm mô tả cách đếm búp bê của bộ Matryoshka nếu búp bê A là búp bê lớn nhất của bộ

def dem_Bupbe (búp bê A):

if (không mở được búp bê A):

return

else:

return dem_Bupbe (con của búp bê A) +

búp bê A

1

Phần cơ sở

Phần đệ quy

Hướng dẫn thực hiện

3. Xét tập S được định nghĩ đệ quy như sau:

• Phần cơ sở: 3 là phần tử của S.
• Phần đệ quy: Nếu x thuộc S và y thuộc S thì x + y thuộc S (chú ý: x và y có thể cùng giá trị).

4. Công thức toán học, dãy số hay hình ảnh nào sau đây được xây dựng mang tính đệ quy? Tại sao?

4. Công thức toán học, dãy số hay hình ảnh nào sau đây được xây dựng mang tính đệ quy? Tại sao?

4. Công thức toán học, dãy số hay hình ảnh nào sau đây được xây dựng mang tính đệ quy? Tại sao?

1. Định nghĩa: Đệ quy của một đối tượng là sự mô tả cách xây dựng đối tượng từ phiên bản nhỏ hơn của chính đối tượng đó.

Phần đệ quy: Phần chứa quy tắc để xây dựng đối tượng mới từ một đối tượng

Thành phần

Trong những câu sau đây, câu nào đúng khi nói về đệ quy?

a. Ưu điểm của đệ quy là giúp cho mô tả đối tượng, sự việc trở nên ngắn gọn.

b. khi đưa ra định nghĩa đệ quy của một đối tượng, không nhất thiết phải có phần cơ sở.

c. Trong một công thức đệ quy, phần đệ quy đưa ra quy tắc xây dựng đối tượng mới chỉ từ một đối tượng cùng dạng có kích thước nhỏ hơn.

d. Trong một công thức đệ quy, phần cơ sở là phần chứa quy tắc để xây dựng đối tượng mới từ một đối tượng cùng dạng có kích thước nhỏ hơn.

LUYỆN TẬP

Câu 1. Định nghĩa đệ quy của một đối tượng gồm:

A. phần cơ sở và phần quy tắc.

B. phần quy tắc và phần định nghĩa.

C. phần cơ sở và phần đệ quy.

D. phần quy tắc và phần đệ quy.

C. phần cơ sở và phần đệ quy.

Câu 2. Cho công thức toán học sau:

--------------- Còn tiếp ---------------