Soạn mới giáo án Khoa học máy tính 11 kết nối tri thức bài 19: Bài toán tìm kiếm

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV chia lớp thành 6 nhóm.

- GV yêu cầu HS giao nhiệm vụ cho các nhóm theo Hoạt động 1 trang 89 SGK:

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

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.

- GV đặt câu hỏi cho các nhóm và yêu cầu HS trả lời:

+ 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ó).

- Sau khi HS trả lời, GV kết luận về nội dung bài toán tìm kiếm trên thực tế.

- Dựa vào ví dụ vừa nêu ở Hoạt động 1, GV yêu cầu HS trả lời câu hỏi củng cố trang 90 SGK:

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.

+ Câu 1: Bài toán tìm đường đi từ nhà em đến trường học dựa trên bản đồ số.

+ Câu 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ú.

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

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- Đại diện nhóm HS trình bày.

*Hoạt động 1 trang 90 SGK:

Bài toán 1. Miền dữ liệu là tất cả các ảnh có trên các máy tính kết nối mạng Internet. Kết quả là các ảnh hình hoa hồng.

Bài toán 2. 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. Miền dữ liệu là danh sách học sinh vvaf điểm các bài dự thi của kì thi Olympic Tin học thành phố. Kết quả là danh sách 5 bạn có thành tích cao nhất tính theo điểm trung bình.

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

+ Câu 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.

+ Câu 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 đồ.

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

1. 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 CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV đặt vấn đề: 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.

- GV yêu cầu HS nghiên cứu SGK và trả lời nội dung Hoạt động 2 trang 91 SGK:

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.

- GV chú ý: 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.

- Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS khái quát về thuật toán tìm kiếm tuần tự.

- Dựa vào ví dụ vừa nêu ở Hoạt động 2, GV yêu cầu HS trả lời câu hỏi củng cố trang 91 SGK:

+ Câu 1: Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86].

Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy?

+ Câu 2: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?

+ Câu 3: Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.

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

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- Đại diện nhóm HS trình bày.

*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ác nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

2. Tìm kiếm tuần tự

- Thuật toán tìm kiếm tuần tự được thực hiện bằng cách duyệt lần lượt các phần tử của dãy từ đầu đến cuối để tìm phần tử có giá trị bằng giá trị cần tìm.

- Thuật toán tìm kiếm tuần tự có thể viết như sau:

1 deaf LinearSearch(A,K):

2    for i in range(len(A)):

3       if A[i] == K:

4           return i

5    return -1

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV yêu cầu các nhóm trả lời câu hỏi dựa theo Hoạt động 3 trang 91 SGK:

Cho trước một dãy số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dãy các phần tử đã sắp xếp.

- GV yêu cầu các nhóm nghiên cứu SGK và trả lời các câu hỏi sau:

+ Nêu ý tưởng của thuật toán tìm kiếm nhị phân trên dãy các phần tử đã được sắp xếp (tăng dần hoặc giảm dần).

+ Nêu các bước thực hiện chi tiết của thuật toán.

+ Vì sao thuật toán này lại nhanh hơn thuật toán tìm kiếm tuần tự đã nêu trong hoạt động 1.

+ Nêu cách mô tả thuật toán và cài đặt chương trình trên Python.

- GV tổ chức cho HS tìm hiểu ví dụ các bước của thuật toán tìm kiếm nhị phân.

- Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS khái quát về thuật toán tìm kiếm nhị phân.

- Dựa vào ví dụ vừa nêu ở Hoạt động 3, GV yêu cầu HS trả lời câu hỏi củng cố trang 93 SGK:

Cho dãy A = [0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67].

+ Câu 1: Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần tử có giá trị bằng 34?

+ Câu 2: Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phần tử có giá trị bằng 34?

+ Câu 3: Thay vì lần lượt các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu tiên Minh lật thẻ ở giữa, sau đó tùy theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lật tiếp thẻ ở ngay bên trái, hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?

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

- HS thảo luận nhóm, đọc SGK và trả lời câu hỏi.

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- Đại diện nhóm HS trình bày.

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

+ Câu 1: Thuật toán tìm kiếm tuần tự sẽ phải duyệt qua 11 phần tử để tìm được phần tử bằng 34.

+ Câu 2: Thuật toán tìm kiếm nhị phân sẽ phải duyệt qua 3 phần tử sau: 14, 20, 34.

+ Câu 3: Minh phải lật nhiều nhất là    thẻ với n là số thẻ ban đầu.

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

- GV tổng kết kiến thức và yêu cầu HS ghi chép vào vở.

3. Tìm kiếm nhị phân

a) Phân tích bài toán

- Bài toán tìm kiếm nhị phân tìm kiếm với dãy số đã được sắp xếp. Khi duyệt một phần tử bất kì của dãy số, em có thể xác định được phần tử cần tìm sẽ nằm ở bên trái hay bên phải phần tử đang duyệt, từ đó quyết định tìm tiếp theo hướng nào mà không cần duyệt tất cả các phần tử của dãy số.

b) Thuật toán tìm kiếm nhị phân

- Được áp dụng cho các dãy được sắp xếp theo thứ tự xác định. Sau mỗi bước lặp của thuật toán, phạm vi tìm kiếm được thu hẹp dần. Ví dụ với dãy tăng dần, nếu giá trị cần tìm nhỏ hơn giá trị của phần tử ở giữa của dãy thì phạm vi tìm kiếm thu hẹp vào nửa đầu của dãy, ngược lại, phạm vi tìm kiếm là nửa cuối của dãy. Cứ tiếp tục như vậy cho đến khi tìm thấy hoặc phạm vi tìm kiếm bằng rỗng.

c) Minh họa các bước của thuật toán tìm kiếm nhị phân

Giả sử dãy số đã sắp xếp là A = [1, 3, 4, 7, 8, 9, 10]. Giá trị cần tìm là K = 9.

Bước 1. Phạm vi tìm kiếm là các phần tử được in đậm [1, 3, 4, 7, 8, 9, 10]

1 left = 0, right = 6

2 mid = (0 + 6) // 2 = 3

3 A[mid] = A[3] = 7 < K # phần tử cần tìm nằm ở dãy con bên phải

Cập nhật chỉ số left = mid + 1 = 3 + 1 = 4

Bước 2. Phạm vi tìm kiếm là các phần tử được in đậm [1, 3, 4, 7, 8, 9, 10]

1 left = 4, right = 6

2 mid = (4 + 6) // 2 = 5

3 A[mid] = A[5] = 9 < K # phần tử cần tìm có chỉ số 5. Kết thúc chương trình.

Sơ đồ minh họa

® Thuật toán tìm kiếm nhị phân trên dãy số đã sắp xếp tăng dần có thể như sau, trong đó hàm BinarySearch(A,K) trả lại chỉ số I nếu tìm thấy A[i] = K và trả lại giá trị -1 nếu không tìm thấy K trong dãy A.

1 def BinarySearch(A,K):

2   left = 0

3   right = len(A) – 1

4   while left <= right:

5      mid = (left + right)//2

6      if A[mid] == K:

7        return mid

8      elif A[mid] < K:

9        left = mid + 1

10     else:

11       right = mid – 1

12 return -1