Slide bài giảng Khoa học máy tính 11 kết nối Bài 19: Bài toán tìm kiếm

Tóm lược nội dung

BÀI 19: BÀI TOÁN TÌM KIẾM

KHỞI ĐỘNG

- GV dẫn dắt, đặt vấn đề cho HS: Giả sử có một bộ thẻ, mỗi thẻ in một số ngẫu nhiên. Các thẻ được xếp úp mặt xuống bàn theo thứ tự tăng dần của các số. Người chơi chỉ có thể lật một thẻ mỗi lần để xem giá trị số in trên đó. Nếu giá trị trên thẻ lật lên bằng số K đã cho, trò chơi sẽ kết thúc. Bạn An đã chơi bằng cách lật lần lượt từng thẻ từ đầu đến cuối.

- GV đặt câu hỏi yêu cầu HS trả lời: Theo em, An có thể chắc chắn xác định thẻ nào in số K không? Em có phương pháp nào để xác định thẻ in số K nhanh hơn An không?

NỘI DUNG BÀI HỌC GỒM

• Tìm hiểu bài toán tìm kiếm trên thực tế 

•  Tìm hiểu tìm kiếm tuần tự

• Luyện tập

• Vận dụng

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Tìm hiểu bài toán tìm kiếm trên thực tế 

Có thể nói tìm kiếm là một trong những bài toán quan trọng nhất của Tin học. Việc thiết kế thuật toán tìm kiếm sẽ phụ thuộc vào cấu trúc của miền dữ liệu cần tìm kiếm và tiêu chí cụ thể của bài toán tìm kiếm.

Hoạt động 2: Tìm hiểu tìm kiếm tuần tự

*Câu hỏi củng cố trang 91 SGK:

+ Câu 1: Cần duyệt 8 bước sẽ tìm thấy số 47.

+ Câu 2: Khi giá trị cần tìm trùng với số đầu tiên của dãy.

+ Câu 3: Khi số cần tìm không có trong dãy hoặc trùng với số cuối cùng của dãy.

 HOẠT ĐỘNG LUYỆN TẬP, THỰC HÀNH

Câu 1: Đâu là phát biểu đúng khi nói đến thuật toán tìm kiếm tuần tự?

A. Thực hiện tìm lần lượt từ đầu đến cuối danh sách.

B. Khi chưa tìm thấy và chưa tìm hết thì còn tìm tiếp.

C. Cả A, B đúng.

D. Cả A, B sai.

Câu 2: Thuật toán tìm kiếm tuần tự thực hiện công việc gì?

A. Lưu trữ dữ liệu.

B. Sắp xếp dữ liệu theo chiều tăng dần.

C. Xử lí dữ liệu.

D. Tìm kiếm dữ liệu cho trước trong một danh sách đã cho.

Câu 3: Thuật toán tìm kiếm tuần tự yêu cầu danh sách cần tìm phải được sắp xếp.

A. Đúng. 

B. Sai.

Câu 4: Thuật toán tìm kiếm tuần tự thực hiện công việc như thế nào?

A. Sắp xếp lại dữ liệu theo thứ tự bảng chữ cái.

B. Xem xét mục dữ liệu đầu tiên, sau đó xem xét từng mục dữ liệu tiếp theo cho đến khi tìm thấy mục dữ liệu được yêu cầu hoặc đến khi hết danh sách.

C. Cho nhỏ dữ liệu thành từng phần để tìm kiếm.

D. Bất đầu tìm từ vị trí bất kì trong danh sách.

Câu 5: Trong tìm kiếm tuần tự thì có mấy điều kiện cần kiểm tra để dừng vòng lặp?

A. 1

B. 2

C. 3

D. Không

Đáp án gợi ý:

Câu 1: C

Câu 2: D

Câu 3: B 

Câu 4: B

Câu 5: B 

HOẠT ĐỘNG VẬN DỤNG

- GV yêu cầu HS hoàn thành bài tập phần Vận dụng trang 93 SGK.

Bài 1. Cho A là danh sách tên các học sinh trong lớp, hãy viết chương trình tìm kiếm tuần tự để tìm ra những học sinh có tên là Hoàn.

Bài 2. Cho A là danh sách tên các học sinh trong lớp đã được sắp xếp theo thứ tự bảng chữ cái, hãy viết chương trình tìm kiếm nhị phân để tìm ra những học sinh có tên là Minh.