Mời các em cùng khám phá nội dung Bài 19: Bài toán tìm kiếm. Thông qua bài học này, các em sẽ biết được ý nghĩa của bài toán tìm kiếm và thực hiện được chương trình tìm kiếm. HOC247 hy vọng rằng qua các bài học của chương trình Khoa học máy tính, các em sẽ thu thập những kiến thức hữu ích và thú vị, giúp nâng cao kiến thức về môn Tin học.
Tóm tắt lý thuyết
1.1. Bài toán tìm kiếm trên thực tế
- 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.
1.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.
- Thuật toán tìm kiếm tuần tự : Cho dãy số A[0], A[1],..., A[n-1] và giá trị K, cần tìm chỉ số i mà A[i] = K, trả về -1 nếu không tìm thấy.
- Thuật toán tìm kiếm tuần tự có thể viết như sau:
1.3. Tìm kiếm nhị phân
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 trên thực tế
- 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].
- So sánh K với phần tử giữa dãy A[mid], có 3 trường hợp 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 họa các bước của thuật toán tìm kiếm nhị phân
- 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.
Bài tập minh họa
Hãy mô tả cách thực hiện thuật toán tìm kiếm tuần tự?
Hướng dẫn giải:
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.
3. Luyện tập Bài 19 SGK Tin học 11 Kết nối tri thức
Qua bài học này, các em sẽ có thể:
- 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.
3.1. Trắc nghiệm Bài 19 SGK Tin học 11 Kết nối tri thức
Như vậy là các em đã xem qua bài giảng Bài 19 Chủ đề 6 Tin học lớp 11 Kết nối tri thức. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Kết nối tri thức Bài 19.
Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!
3.2. Bài tập Bài 19 SGK Tin học 11 Kết nối tri thức
Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Kết nối tri thức Bài 19 để giúp các em nắm vững bài học và các phương pháp giải bài tập.
Khởi động trang 89 SGK Tin học 11 Kết nối tri thức - KNTT
Hoạt động 1 trang 89 SGK Tin học 11 Kết nối tri thức - KNTT
Câu hỏi 1 trang 90 SGK Tin học 11 Kết nối tri thức - KNTT
Câu hỏi 2 trang 90 SGK Tin học 11 Kết nối tri thức - KNTT
Hoạt động 2 trang 90 SGK Tin học 11 Kết nối tri thức - KNTT
Câu hỏi 1 trang 91 SGK Tin học 11 Kết nối tri thức - KNTT
Câu hỏi 2 trang 91 SGK Tin học 11 Kết nối tri thức - KNTT
Câu hỏi 3 trang 91 SGK Tin học 11 Kết nối tri thức - KNTT
Hoạt động 3 trang 91 SGK Tin học 11 Kết nối tri thức - KNTT
Câu hỏi 1 trang 93 SGK Tin học 11 Kết nối tri thức - KNTT
Câu hỏi 2 trang 93 SGK Tin học 11 Kết nối tri thức - KNTT
Câu hỏi 3 trang 93 SGK Tin học 11 Kết nối tri thức - KNTT
Luyện tập 1 trang 93 SGK Tin học 11 Kết nối tri thức - KNTT
Luyện tập 2 trang 93 SGK Tin học 11 Kết nối tri thức - KNTT
Vận dụng 1 trang 93 SGK Tin học 11 Kết nối tri thức - KNTT
Vận dụng 2 trang 93 SGK Tin học 11 Kết nối tri thức - KNTT
4. Hỏi đáp Bài 19 SGK Tin học 11 Kết nối tri thức
Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!
Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!
-- Mod Tin Học 11 HỌC247
