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

Cho A, B, C, D lần lượt là các danh sách tên học sinh, điểm thi môn Toán, điểm thi môn Vật lí và điểm thi môn Hóa học. Danh sách điểm Toán được sắp xếp theo thứ tự tăng dần và các danh sách tên học sinh và điểm các môn còn lại được sắp xếp theo tương ứng

A = [“Nam”, “Sơn”, “Hương”, “Huyền”, “Hà”, “Hùng”]

B = [8.3, 8.4, 8.7, 8.9, 9.1.96]

C= [ 8.3, 7.8, 8.9, 9.5, 9.3, 9.0]

D= [7.9, 9.0, 8.9, 8.2, 9.5, 9.1]

Hãy thảo luận về kĩ thuật tìm kiếm được thực hiện với mỗi yêu cầu sau:

a) Tìm một học sinh có điểm Toán lớn hơn điểm Vật lí.

b) Tìm tất cả các học sinh có điểm Vật lí lớn hơn điểm Hoá học.

c) Tìm tất cả các học sinh có cả 3 điểm đều lớn hơn hoặc bằng 9.

- GV cho HS thảo luận nhóm, tìm cách tìm kiếm HS trên tập dữ liệu cho trước theo yêu cầu.

- GV giúp HS hiểu được sự khác nhau giữa yêu cầu tìm 1 HS thỏa mãn yêu cầu và tìm tất cả HS thỏa mãn yêu cầu cho trước.

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

+ Câu 1: So sánh số vòng lặp cần thực hiện để thực hiện các yêu cầu a, b, c trong ví dụ trên.

+ Câu 2: Phân tích và viết chương trình để thực hiện các yêu cầu sau:

a) Tìm học sinh có điểm Toán bằng 8.9.

b) Tìm một học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học lớn hơn 26.5.

c) Tìm học sinh có tổng điểm ba môn Toán, Vật lí, Hoá học nhỏ nhấ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 viên bi giả 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, hình thành kiến thức bài học.

- Đại diện các nhóm xung phong trả lời Câu hỏi (SGK – tr30)

- 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. Ý tưởng chia để trị

- Hoạt động 1

a) Ví dụ: Sơn.

b) Nam, Huyền.

c) Hà, Hùng.

*Kết luận

- Kĩ thuật duyệt: Sau khi xác định được miền tìm kiếm, kĩ thuật duyệt sẽ lần lượt xét các dữ liệu trong miền tìm kiếm để đưa ra được phần tử thỏa mãn.

- Các bài toán tìm kiếm có thể:

+ Đa dạng về yêu cầu tìm kiếm.

+ Đa dạng về miền tìm kiếm.

- Tùy thuộc vào yêu cầu tìm kiếm, miền tìm kiếm, ta thực hiện các kĩ thuật duyệt theo những cách khác nhau.

+ Ví dụ: bài toán yêu cầu tìm kiếm một nghiệm; hoặc bài toán tìm nghiệm tối ưu hoặc tìm tất cả các nghiệm.

+ Ví dụ: Miền tìm kiếm là danh sách thông thường chưa sắp xếp; hoặc miền tìm kiếm danh sách đã được sắp xếp.

Ví dụ: Chương trình mô tả thuật toán tìm kiếm theo ba yêu câu của Hoạt động 1

Câu hỏi (SGK -tr.50)

Câu 1:

- Với a) Nếu duyệt từ đầu dãy đến cuối dãy thì chương trình có thể kết thúc sau vòng lặp thứ hai.

- Với b) và c) cần duyệt toàn bộ HS có trong danh sách, số vòng lặp cần thực hiện là 6.

Câu 2:

- Với yêu cầu a) ta có thể duyệt từ đầu dãy và dừng lại khi tìm thấy một HS có điểm Toán bằng 8.9

- Với yêu cầu b) duyệt từ đầu dãy và dừng lại khi tìm thấy HS có tổng điểm ba môn lớn hơn 26.5.

- Với yêu cầu c) duyệt toàn bộ danh sách các HS trong danh sách.