Giáo án chuyên đề Khoa học máy tính 11 kết nối Bài 2: Thiết kế thuật toán đệ 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 thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 1 SGK trang 11:

Trao đổi, thảo luận và tìm hiểu ý tưởng thực hiện các tính toán sau bằng kĩ thuật đệ quy.

1. Tính tổng S(n)= 1+2+...+n

2. Tính luỹ thừa =a a  ... a (n lần).

3. Tính n giai thừa

- GV yêu cầu HS chia thành các nhóm và mỗi nhóm thực hiện đọc, trao đổi và thực hiện giải quyết một bài toán bằng thiết kế thuật toán đệ quy.

- GV hỏi một số câu hỏi:

+ Vì sao lại thiết kế lập trình đệ quy, các ví dụ này có những điểm gì giống nhau.

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

Ý tưởng chính của kĩ thuật đệ quy là biến đổi bài toán ban đầu về bài toán với kích thước nhỏ hơn. Nếu bài toán có kích thước nhỏ có thề giải được thì có thề thiết lập lời giải đệ quy cho bài toán này. Lời giải của các bài toán sử dụng kĩ thuật đệ quy thường ngắn gọn và dễ hiểu.

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

1. Hãy chỉ ra phần cơ sở và phần đệ quy của các chương trình trên.

2. Vì sao trong ý tưởng thiết kế đệ quy trên, yêu cầu từ bài toán với kích thước lớn cần phải đưa về cùng bài toán đó với kích thước nhỏ hơn?

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

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

- Hoạt động 1:

1.

2.

3.

- Cả ba bài toán trên đều có chung tính chất là từ bài toán góc có thẻ đưa về trường hợp có tham số đầu vào nhỏ hơn. Điều đó sẽ dẫn đén việc có thẻ dùng Kĩ thuật đệ quy đề gọi chính hàm góc. Nếu với các dữ liệu đầu vào nhỏ có thẻ giải trực tiếp (ví dụ các bài toán trên đều có lời giải cho trường hợp n = 0) thì phản cơ sở của đệ quy sẽ thực hiện lời giải trực tiếp này.

- Trong cả ba chương trình trên, các hàm được định nghĩa với tham số n mặc định phải thoả mãn n > 0. Do đó, các hàm này không cần có lệnh điều khiển dừng tường minh. Nhóm các lệnh cơ sở sẽ làm luôn chức năng kiểm soát đùng của lặp đệ quy.

Câu hỏi:

Câu 1: a) Phần cơ sở lệnh là 2,3, phần đệ quy là lệnh 5.

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

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

Câu 2: Vì trong tất cả các thuật toán đệ quy đều phải có yêu cầu bài toán có kích thước lớn hơn đưa về cùng bài toàn đó với kí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 thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 2 SGK trang 13:

Chúng ta đã biết thuật toán tìm kiềm nhị phân trên dãy các phần tử đã sắp xếp. Hãy tìm thiết kế mới của thuật toán này theo kĩ thuật đệ quy. Trao đổi, thảo luận và trả lời các câu hỏi sau:

1. Nêu ý tưởng chính của giải thuật tìm kiếm nhị phân sử dụng Kĩ thuật đệ quy.

2. Vị trí nào trong thuật toán có thẻ gợi ý cho kĩ thuật đệ quy?

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

- GV trình bày lại thuật toán tìm kiếm nhị phân đã được học trong SGK phần kiến thức thuật toán tìm kiếm,

- GV đưa các câu hỏi để các nhóm HS trao đổi, thảo luận về đặc điểm của thuật toán này và các gợi ý để có thể dẫn đến lời giải đệ quy của thuật toán. Đặc điểm quan trọng nhất của thuật toán tìm kiếm nhị phân là sau mỗi bước việc tìm kiếm sẽ được thu gọn lại trên miền dữ liệu có độ dài bằng  miền tìm kiếm của bước trước. Đây chính là gợi ý quan trọng nhất để dẫn đến ý tưởng thiết kế đệ quy.

- GV mô tả thiết kế đệ quy của thuật toán và cùng các nhóm thực hiện cài đặt thuật toán này ngay trên lớp.

- GV chốt kiến thức về công thức truy hồi của các dãy số truy hồi, từ đó nêu ra sự liên hệ với khái niệm đệ quy.

Thuật toán tìm kiếm nhị phân có thể biểu diễn bằng kĩ thuật đệ quy trên độ dài của dây cân tìm kiếm. Mỗi lần gọi độ quy sẽ gọi hàm tìm kiếm trên dãy có độ dài bằng  độ dài của dây hiện tại.

- GV yêu cầu HS giữ nguyên nhóm, tiếp tục thảo luận để hoàn thành các bài tập trong phần Câu hỏi nhằm khắc sâu kiến thức:

1. Trong chương trình trên lệnh nào đóng vai trò là phần cơ sở của đệ quy?

2. Giả sử A = [1, 3, 7, 9] và K= 10. Nếu áp dụng chương trình trên thì cần mấy lần gọi hàm đệ quy??

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

- Các nhóm HS tìm hiểu kiến thức mới trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

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

- GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình.

- Đại diện các nhóm xung phong trả lời Câu hỏi.

- Các HS còn lại nhận xét, bổ sung (nếu có).

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

- GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm là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 toán tìm kiếm nhị phân

Hoạt động 2

1.

2. Theo mô tả ở trên, chúng ta thầy Bước 2.3 và Bước 2.4 thực hiện việc đưa bài toán tìm kiềm về chính bài toán đó với các dãy con có kích thước nhỏ hơn, cụ thể là bằng: kích thước dãy ban đầu. Như vậy, lệnh gọi đệ quy sẽ thực hiện tại các bước này.

3. Bước 3 đóng vai trò phần cơ sở của đệ quy, khi độ dài của dãy cần tìm kiếm bằng 0 thì chương trình sẽ dừng lại và thông báo không tim thầy.

Câu hỏi:

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

2. Nếu A = [1,3,7, 9], K = 10 thì lời gọi hàm tìm kiếm nhị phân sẽ gọi đệ quy ba lần.

Lần 1, hàm sẽ gọi đệ quy đến đãy [7, 9].

Lần 2, hàm sẽ gọi đệ quy đến dãy [9].

Lần 3, hàm sẽ gọi đệ quy đến dãy [].