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

NHIỆT LIỆT CHÀO MỪNG CÁC EM ĐẾN VỚI TIẾT HỌC MỚI!

TRÒ CHƠI LẬT THẺ

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ẻ để xem 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.

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ÀI 19: BÀI TOÁN TÌM KIẾM

NỘI DUNG BÀI HỌC

Bài toán tìm kiếm trên thực tế

Tìm kiếm tuần tự

Tìm kiếm nhị phân

01 BÀI TOÁN TÌM KIẾM TRÊN THỰC TẾ

Chia lớp thành 6 nhóm, thực hiện Hoạt động 1

Với các bài toán tìm kiếm sau, hãy thảo luận về miền dữ liệu và khả năng các kết quả có thể tìm được của bài toán:

Nhóm 1, 4

Tìm hiểu Bài toán 1. Em cần tìm hình ảnh các cây hoa hồng đẹp trên Internet để đưa vào bài trình bày về cách trồng hoa.

Nhóm 2, 5

Tìm hiểu Bài toán 2. Em cần tìm một tệp văn bản có tên bai-hoc-1.docx trên máy tính của em những đã lâu rồi chưa sử dụng lại.

Nhóm 3, 6

Tìm hiểu Bài toán 3. Em cần tìm 5 bạn học sinh có điểm trung bình các bài thi cao nhất trong kì thi Olympic Tin học năm 2020 của thành phố Hà Nội.

Câu hỏi gợi ý tìm hiểu:

• Vì sao cần tìm kiếm?
• Miền tìm kiếm là gì? Dữ liệu tìm kiếm là gì?
• Nghiệm nếu tìm thấy là gì?
• Mô tả một kết quả có thể của nghiệm.
• Nêu cách tìm kiếm kiểm tra lời giải (nếu có).

Bài toán 1

Em cần tìm hình ảnh các cây hoa hồng đẹp trên Internet để đưa vào bài trình bày về cách trồng hoa.

Miền dữ liệu:

Là tất cả các ảnh có trên máy tính kết nối mạng Internet

Kết quả:

Là các ảnh có hình hoa hồng

Bài toán 2

Em cần tìm một tệp văn bản có tên bai-hoc-1.docx trên máy tính của em những đã lâu rồi chưa sử dụng lại.

Miền dữ liệu:

Là các tệp văn bản có trên đĩa cứng máy tính của em.

Kết quả:

Là tệp có tên bai-hoc-1.docx

Bài toán 3

Em cần tìm 5 bạn học sinh có điểm trung bình các bài thi cao nhất trong kì thi Olympic Tin học năm 2020 của thành phố Hà Nội.

Miền dữ liệu:

Là danh sách học sinh và điểm các bài thi của kì thi Olympic Tin học thành phố.

Kết quả:

Danh sách 5 bạn có thành tích cao nhất tính theo điểm trung điểm.

Câu hỏi củng cố kiến thức:

Em hãy xác định miền dữ liệu và nghiệm có thể của các bài toán tìm kiếm sau.

1. Bài toán tìm đường đi từ nhà em đến trường học dựa trên bản đồ số.
2. Bài toán tìm tất cả các trường trung học phổ thông (tên trường, địa chỉ) ở quận (huyện) em đang cư trú.

ĐÁP ÁN

Bài toán 1

Miền dữ liệu là tập hợp các vị trí và đường phố, hay nói cách khác là dữ liệu bản đồ số của địa phương nơi em đang sống.

Nghiệm có thể là một đường đi từ nhà em đến trường. Thể hiện nghiệm có thể hiện trên bản đồ hoặc dãy các bước đi cụ thể từ nhà em đến trường.

Bài toán 2

Miền dữ liệu là danh sách tất cả các trường học (thuộc các cấp khác nhau), có thể cả các cơ quan, công ti, văn phòng tại địa phương em đang sống.

Nghiệm sẽ là một danh sách các trường Trung học phổ thông trên địa bàn, hoặc có thể là các vị trí được đánh dấu trên bản đồ.

GHI NHỚ

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.

02 TÌM KIẾM TUẦN TỰ

Cách An lần lượt lật các thẻ từ đầu đến cuối trong phần khởi động chính là việc thực hiện tìm kiếm tuần tự trong các thẻ bài.

Hoạt động 2:

Quan sát cách thực hiện thuật toán tìm kiếm tuần tự trên ví dụ cụ thể sau. Hãy trao đổi, thảo luận để hiểu và mô tả được thuật toán trong trường hợp tổng quát.

Trường hợp tổng quát:

• Đầu vào: Cho trước dãy số A[0], A[1],..., A[n-1] và giá trị K.
• Đầu ra: Cần tìm ra chỉ số i mà phần tử A[i] có giá trị bằng K. Nếu không tìm thấy thì trả về giá trị -1.

Ví dụ cụ thể:

Cho dãy số A = [1, 4, 7, 8, 3, 9, 10] và cần tìm kiếm phần tử có giá trị bằng 9.

Có thể thực hiện tìm kiếm tuần tự như sau:

• Bước 1: i = 0: A[0] = 1 không bằng 9
• Bước 2: i = 1: A[1] = 4 không bằng 9
• Bước 3: i = 2: A[2] = 7 không bằng 9
• Bước 4: i = 3: A[3] = 8 không bằng 9
• Bước 5: i = 4: A[4] = 3 không bằng 9
• Bước 6: i = 5: A[5] = 9 là phần tử cần tìm.

Lưu ý

Miền dữ liệu tìm kiếm phải có

cấu trúc là một dãy tuyến tính các số được đánh số theo chỉ số, ví dụ đánh chỉ số từ 0, 1, 2,…, n – 1.

GHI NHỚ