Giáo án và PPT Khoa học máy tính 11 kết nối Bài 19: Bài toán tìm kiếm

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

A. KHỞI ĐỘNG

- GV dẫn dắt, đặt vấn đề cho HS: Giả sử có một bộ thẻ, trên mỗi thẻ in một số bất kì. 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ố ghi trên thẻ. Người chơi mỗi lần chỉ được lật một thẻ để xe giá trị số in trên đó. Nếu giá trị số in trên thẻ lật lên bằng số K cho trước thì trò chơi 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ó chắc chắn xác định được thẻ nào in số K không? Em có cách nào xác định được thẻ in số K nhanh hơn An không?

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

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

Câu 1: 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 2: 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 3: Thực hiện thuật toán tìm kiếm tuần tự để tìm số 20 trong danh sách [1, 3, 5, 4, 20, 2, 11]. Đâu ra của thuật toán là?

A. Thông báo “Không tìm thấy”.

B. Thông báo “Tìm thấy”.

C. Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ 5 của danh sách.

D. Thông báo “Tìm thấy”, giá trị cần tìm tại vị trí thứ 20 của danh sách.

Câu 4: Thuật toán tìm kiếm nhị phân bắt đầu thực hiện ở vị trí nào trong danh sách?

A. Vị trí đầu tiên.

B. Vị trí cuối cùng.

C. Vị trí giữa.

D. Bất kì vị trí nào.

Câu 5: Khi thực hiện tìm kiếm nhị phân số 25 trong dãy số 18, 21, 25, 27, 67, 69, 72, 77, 79, 81 cần thực hiện mấy vòng lặp?

A. 3.

B. 4.

C. 5.

D. 6.

Sản phẩm dự kiến:

Câu 1: D

Câu 2: B

Câu 3: C 

Câu 4: C

Câu 5: A 

D. HOT ĐỘ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, viết chương trình tìm kiếm tuần tự để tìm ra các 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, viết chương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh.