Soạn giáo án chuyên đề Khoa học máy tính 11 kết nối tri thức Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị

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

Hãy thiết lập thuật toán và chương trình tính lũy thừa aⁿ với a là số bất kì khác 0, n là số nguyên không âm.

- GV mô tả bài toán và yêu cầu các nhóm giải bài toán bằng cách tính thông thường, bằng tay và chương trình.

- GV giới thiệu ý tưởng mới giải bài toán tính lũy thừa theo kĩ thuật chia để trị.

- Sau khi thực hiện việc cài đặt chương trình, GV cho các nhóm thảo luận về độ phức tạp thời gian của thuật toán.

- GV kết luận về nội dung độ phức tạp thời gian của thuật toán.

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

+ Câu 1: Mô tả các bước tính bằng tay phép tính lũy thừa 2¹¹ theo hai chương trình trên. Các nào nhanh hơn?

+ Câu 2: Phép tính a²¹ sẽ cần dùng bao nhiêu phép nhân?

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

- Các nhóm HS tìm hiểu lời giải của bài toán tính lũy thừa bằng chia để trị 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 (SGK – tr34)

Câu 1: Tính tay 2¹¹.

- Tính theo phương pháp cũ. Cần thực hiện 10 lần phép nhân với 2.

- Tính theo phương pháp chia để trị mới.

Bước 1. Tính 2 x 2 = 2²

Bước 2. Tính 4 x 4 = 2⁴

Bước 3. Tính 2⁴ x 2 = 2⁵

Bước 4. Tính 2⁵ x 2⁵ = 2¹⁰

Bước 5. Tính 2¹⁰ x 2 = 2¹¹

Vậy theo cách tính mới chỉ cần 5 phép nhân.

Câu 2: Tính a²¹

a²¹ = a x a¹⁰ x a¹⁰

Theo bài trên, tính a¹⁰ cần 4 phép nhân, vậy suy ra cần 4 + 2 = 6 phép nhân cho a²¹.

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

1. Bài toán tính lũy thừa

- Hoạt động 1

Vì aⁿ = a x a^n-1 nên có thể thiết lập ngay chương trình tính hàm lũy thừa đơn giản như sau:

Chương trình 1. Tính lũy thừa theo cách tự nhiên.

Chương trình 2. Tính lũy thừa theo cách nhị phân nhanh (chia để trị).

*Kết luận

- Hàm exp(a,n) trên được thiết lập theo kĩ thuật chia để trị có độ phức tạp thời gian O(logn).

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

Xây dựng thuật toán cho bài toán sau: Cho trước dãy các số đã được sắp xếp tăng dần. Với giá K cho trước cần tìm phần tử của dãy gốc có giá trị gần với K nhất.

- GV mô tả bài toán và yêu cầu các nhóm trao đổi, thực hiện bài toán theo cách tìm kiếm tuần tự, tức là thuật toán tự nhiên.

- Sau đó, GV thiết kế theo phương pháp chia để trị, cách làm này sẽ là một mở rộng của thuật toán tìm kiếm nhị phân đã biết từ các bài trước.

- GV kết luận về bài toán tìm kiếm nhị phân mở rộng.

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

+ Câu 1: Hãy giải thích kĩ hơn chương trình 2 ở trên tại các dòng 4 và 6.

+ Câu 2: Nêu những điểm khác biệt của chương trình trên với chương trình tìm kiếm nhị phân đã biết.

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

- Các nhóm HS tìm hiểu lời giải của bài toán tìm kiếm nhị phân mở rộng 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 (SGK – tr36)

Câu 1:

- Dòng 4 mô tả trường hợp A có một phần tử thì đáp số luôn là phần tử duy nhất này.

- Dòng 6 mô tả trường hợp A có hai phần tử, đáp án sẽ là phần tử nào gần K hơn về giá trị.

Câu 2: Chương trình trên khác thuật toán tìm kiếm nhị phân như sau:

- Cách xử lí các trường hợp cơ sở khi A có 1 hoặc 2 phần tử.

- Sau mỗi bước lặp (hoặc sau mỗi lần gọi đệ quy), phạm vi tìm kiếm sẽ tìm tiếp ở một trong hai khoảng [mid, right] hay [left, mid], điều này khác biệt với tìm kiếm nhị phân là sau mỗi vòng lặp miền tìm kiếm sẽ là [left, mid – 1] hoặc [mid + 1, right].

- 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 luyện tập.

2. Bài toán tìm kiếm nhị phân mở rộng

- Hoạt động 2

Chương trình 1. Sử dụng tìm kiếm tuần tự

Chương trình 2. Sử dụng tìm kiếm nhị phân

*Kết luận

- Thuật toán tìm kiếm nhị phân mở rộng có độ phức tạp thuật toán O(logn).