BÀI 19. BÀI TOÁN TÌM KIẾM
Trang bìa
Trang bìa
Ảnh
TIN HỌC 11
BÀI 19. BÀI TOÁN TÌM KIẾM
Ảnh
Mục tiêu bài học
Mục tiêu
Ảnh
Mục tiêu:
Biết được ý nghĩa của bài toán tìm kiếm trên thực tế. Biết và thực hiện được chương trình tìm kiếm tuần tự và tìm kiếm nhị phân.
Khởi động
- Trò chơi lật thẻ (- Khởi động)
Ảnh
- 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ẻ. Mỗi 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ẻ bằng 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?
Hình thành kiến thức
1. Bài toán tìm kiếm trên thực tế
1. Bài toán tìm kiếm trên thực tế
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: Bài toán 1. Em cần tìm hình ảnh các cây hoa hồng đẹp trên Intemet để đưa vào bài trình bày về cách trồng hoa. 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. 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 của thành phố.
Ảnh
- Hoạt động 1: Bài toán tìm kiếm
- Tìm hiểu
- Tìm hiểu:
Ảnh
Bài toán 1: Miền dữ liệu là tất cả ảnh trên mạng Internet, kết quả là các ảnh hoa hồng. Bài toán 2: Miền dữ liệu là các tệp văn bản trên đĩa cứng, kết quả là tệp bai-hoc-1.docx. Bài toán 3: Miền dữ liệu là danh sách học sinh và điểm thi, kết quả là danh sách 5 bạn có điểm trung bình cao nhất.
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng 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ú.
- Ghi nhớ
- Ghi nhớ:
Ả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.
2. Tìm kiếm tuần
Ảnh
2. Tìm kiếm tuần tự
Cách An lật thẻ từ đầu đến cuối là tìm kiếm tuần tự trong dãy đối tượng.
Bài toán tìm kiếm được mô tả như sau: Đầu vào: Bài toán tìm kiếm trên một dãy số: cho dãy A[0], A[1],..., A[n-1] và giá trị K, Đầu ra: Cần tìm chỉ số i mà A[i] = K, trả về -1 nếu không tìm thấy.
- Hoạt động 2
- Hoạt động 2: Thuật toán tìm kiếm tuần tự
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.
Ảnh
- Tìm hiểu
- Tìm hiểu:
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.
Ảnh
B1. i = 0: A[0] = 1 B2. i = 1: A[1] = 4 B3. i = 0: A[2] = 7 B4. i = 0: A[3] = 8 B5. i = 0: A[4] = 3 B6. i = 0: A[5] = 9
=> Phần từ cần tìm có chỉ số 5.
Hình vẽ
Các bước trên là các bước của thuật toán tìm kiếm tuần tự.
- Thuật toán tìm kiếm tuần tự
Duyệt lần lượt các phần tử của dãy để tìm phần tử có giá trị bằng K. Nếu tìm thấy, trả về chỉ số của phần tử bằng K; Ngược lại, thông báo không tìm thấy và trả về giá trị -1. Thuật toán có thể duyệt từ đầu dãy hoặc từ cuối dãy. Cách viết thuật toán tìm kiếm tuần tự:
- Thuật toán tìm kiếm tuần tự:
1 def LinearSeach (A, K): 2 for i in range (len(A)): 3 if A[i] == K: 4 return i 5 return -1
Ảnh
- Ghi nhớ
- Ghi nhớ:
Ảnh
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.
- Câu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
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? 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? 3. Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho VD.
3. Tìm kiếm nhị phân
3. Tìm kiếm nhị phân
- Hoạt động 3: Thuật toán tìm kiếm nhị phân
Ảnh
Cho trước một đâ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.
a. Phân tích bài toán
Ảnh
a. Phân tích 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. Duyệt phần tử bất kì, xác định phần tử cần tìm ở bên trái hay bên phải. 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
Ảnh
b. Thuật toán tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân thu hẹp phạm vi tìm kiếm liên tục. Nếu giá trị của phần tử ở giữa bằng K thì thông báo tìm thấy. Nếu K nhỏ hơn giá trị ở giữa, thu hẹp phạm vi tìm kiếm nửa đầu dãy tăng A (ngược lại thì phạm vi tìm kiếm nửa sau). Thiết lập left, right là chỉ số phần tử đầu và cuối của dãy cần tìm. Cần tìm K trong A[left..right]. Ban đầu đặt left = 0, right = n - 1.
+ tiếp (b. Thuật toán tìm kiếm nhị phân)
Ảnh
So sánh K với phần tử giữa dãy A[mid], có 3 TH có thể xảy ra:
+ Nếu K = A[mid] thì trả về chỉ số mid và kết thúc. + Nếu K < A[mid] thì phần tử cần tìm ở dãy con bên trái của A[mid], cập nhật right = mid - 1, giữ nguyên left. + Nếu K > A[mid] thì phần tử cần tìm ở dãy con bên phải của A[mid], cập nhật left = mid + 1, giữ nguyên right.
Lặp lại cho đến khi tìm thấy hoặc phạm vi tìm kiếm bằng rỗng (right < left).
c. Minh hoạ các bước của thuật toán tìm kiếm nhị phân
c. Minh hoạ các bước của thuật toán tìm kiếm nhị phân
Ví dụ: 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.
Ảnh
B1. Phạm vi tìm kiếm là các phần tử được in đậm [1, 3, 4, 7, 8, 9, 10].
B2. Phạm vi tìm kiếm là các phần tử được in đậm [1, 3, 4, 7, 8, 9, 10].
Ảnh
- Nhận xét
- Nhận xét:
Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự vì số phần tử cần duyệt giảm một nửa sau mỗi vòng lặp. Với cùng dãy số A và giá trị tìm kiếm K, thuật toán tìm kiếm tuần tự cần 6 bước, nhưng thuật toán tìm kiếm nhị phân chỉ cần 2 bước. Thuật toán tìm kiếm nhị phân trên dãy số đã sắp xếp tăng dần, hàm BinarySearch(A,K) trả lại chỉ số i nếu tìm thấy A[i] = K và -1 nếu không tìm thấy K trong dãy A.
Ảnh
+ tiếp
Ảnh
Ảnh
- Ghi nhớ
- Ghi nhớ:
Ảnh
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âu hỏi củng cố
Ảnh
- Câu hỏi củng cố:
Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. 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? 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? 3. Thay vị lần lượt 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 đó tuỳ 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?
Luyện tập & Vận dụng
- Luyện tập
Ảnh
- Luyện tập
Câu 1: Em hãy chỉnh sửa thuật toán tìm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phân tử bằng giá trị cần tìm. Câu 2: Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần.
Vận dụng
- Vận dụng
Ảnh
- Vận dụng:
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. 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 thương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh.
Dặn dò
Dặn dò
Ảnh
Dặn dò:
Ôn lại kiến thức vừa học. Làm bài tập trong SBT. Chuẩn bị bài sau: "Bài 21. Các thuật toán sắp xếp đơn giản".
Cảm ơn
Ảnh