Bài 13: Thuật toán tìm kiếm trong chủ đề 5 của chương trình Tin học 7 Chân trời sáng tạo bao gồm các kiến thức về thuật toán tìm kiếm sẽ giúp các em giải quyết bài toán một cách dễ dàng. Mời các em tham khảo nội dung bài giảng do DapAnHay biên soạn dưới đây!
Thuật toán tìm kiếm tuần tự thực hiện so sánh lần lượt từ phần tử đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy. |
---|
- Bài tìm kiếm một số trên thẻ được mô tả như sau:
+ Đầu vào: Dãy số (được ghi trên các thẻ) và số cần tìm.
+ Đầu ra: Thông báo vị trí tìm thấy hoặc thông báo không tìm thấy số cần tìm.
- Sơ đồ khối:
Sơ đồ khối mô tả thuật toán tìm kiếm tuần tự để tìm một số
* Bài toán:
Các số được ghi ở mặt úp của các thẻ
* Sơ đồ khối tìm kiếm nhị phân:
Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân để tìm một số trong một dãy thẻ số đã được sắp xếp theo thứ tự không giảm
- Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn. Việc chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.
Thuật toán tìm kiếm nhị phân - Áp dụng với dãy giá trị đã được sắp xếp. - Ở mỗi lần lặp, thực hiện: + Bước 1. So sánh giá trị cần tìm với giá trị của phần từ giữa dãy đang xét. + Bước 2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc. + Bước 3. Nếu nhỏ hơn thì xét dãy ở nửa trước, nếu lớn hơn thì xét dãy ở nửa sau. + Bước 4. Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc tìm kiếm, không thì quay lại Bước 1. Sắp xếp và tìm kiếm Sắp xếp giúp việc tìm kiếm được thực hiện nhanh hơn, hiệu quả hơn. |
---|
Bài tập 1: Tìm một từ tiếng Anh trong cuốn từ điển, em sẽ tìm kiếm theo cách nào nhanh nhất?
Hướng dẫn giải:
Cuốn từ điển đã được sắp xếp theo vần Alphabet. Do đó tìm kiếm nhị phân sẽ tiết kiệm được thời gian và tìm kiếm nhanh hơn.
Bài tập 2: Với dãy số lần lượt là: 12, 14, 15, 18, 19, 21, 24, 25, 26. Nếu thực hiện theo thuật toán tìm kiếm nhị phân để tìm số 21 ta cần thực hiện mấy lần lặp?
Hướng dẫn giải:
Với thuật toán tìm kiếm nhị phân ta cần thực hiện 3 lần lặp. Lần 1 so sánh 21 và 19, Lần 2 so sánh 21 và 24. Lần 3 tìm kiếm được số 21.
Bài tập 3: Ưu điểm của thuật toán tìm kiếm nhị phân là gì?
Hướng dẫn giải:
Thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp.
Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.
Qua bài học các em có thể:
- Giải thích được thuật toán tìm kiếm tuần tự, thuật toán tìm kiếm nhị phân.
- Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm trên bộ dữ liệu vào có kích thước nhỏ.
- Giải thích được mối liên quan giữa sắp xếp và tìm kiếm, nêu được ví dụ minh hoạ.
- Nêu được ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.
Các em có thể hệ thống lại nội dung kiến thức đã học được thông qua bài kiểm tra Trắc nghiệm Tin học 7 Chân trời sáng tạo Chủ đề 5 Bài 13 cực hay có đáp án và lời giải chi tiết.
Thuật toán tìm kiếm tuần tự kết thúc khi nào?
Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiềm tuần tự, ta thực hiện như thế nào?
Cho dãy số A = {24, 28, 14, 18, 19, 12, 19}. Để tìm kiếm số 39 trong dãy theo thuật toán tìm kiềm tuần tự cần thực hiện mấy lần lặp?
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é!
Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 7 Chân trời sáng tạo Chủ đề 5 Bài 13để 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 71 SGK Tin học 7 Chân trời sáng tạo - CTST
Khám phá 1 trang 72 SGK Tin học 7 Chân trời sáng tạo - CTST
Khám phá 2 trang 72 SGK Tin học 7 Chân trời sáng tạo - CTST
Khám phá trang 74 SGK Tin học 7 Chân trời sáng tạo - CTST
Luyện tập 1 trang 75 SGK Tin học 7 Chân trời sáng tạo - CTST
Luyện tập 2 trang 75 SGK Tin học 7 Chân trời sáng tạo - CTST
Vận dụng 1 trang 75 SGK Tin học 7 Chân trời sáng tạo - CTST
Vận dụng 2 trang 75 SGK Tin học 7 Chân trời sáng tạo - CTST
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 DapAnHay 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 7 DapAnHay
Thuật toán tìm kiếm tuần tự kết thúc khi nào?
Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiềm tuần tự, ta thực hiện như thế nào?
Cho dãy số A = {24, 28, 14, 18, 19, 12, 19}. Để tìm kiếm số 39 trong dãy theo thuật toán tìm kiềm tuần tự cần thực hiện mấy lần lặp?
Ưu điểm của thuật toán tìm kiềm nhị phân là gì?
Với dãy số lần lượt là: 12, 14, 15, 18, 19,21, 24, 25, 26. Nếu thực hiện theo thuật toán tìm kiếm nhị phân để tìm số 21 ta cần thực hiện mấy lần lặp?
Thuật toán tìm kiếm tuần tự thực hiện như thế nào?
Thuật toán tìm kiếm tuần tự có thể giúp em thực hiện những hành động nào?
Dùng thuật toán tìm kiếm nhị phân để tìm một số trong dãy thẻ số (được sắp xếp theo thứ tự không giảm), sau bước kiểm tra: số cần tìm nhỏ hơn giá trị trên thẻ nếu nhận kết quả Sai, ta thực hiện bước nào?
Trong thuật toán tìm kiếm nhị phân, ở mỗi lần lặp ta thực hiện mấy bước?
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?
Có 9 thẻ số, mỗi thẻ được ghi số ở một mặt và mặt còn lại không ghi gì. Đặt úp các thẻ số trên mặt bàn và xếp thành một dãy như Hình 1.
Em hãy trao đổi với bạn để thực hiện tìm một số bất kì trong dãy số ghi trên các thẻ ở Hình 1.
Các số ghi trên mỗi thẻ ở Hình 1 lần lượt là: 26, 14, 24, 18, 15, 21, 19, 25, 12.
Em hãy tạo Bảng 1 và điền thông tin của mỗi lần lặp để tìm số 21 trong dãy theo thuật toán tìm kiếm tuần tự.
Lựa chọn phương án đúng.
Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện:
A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
C. Sắp xếp dãy số theo thứ tự tăng dần.
D. So sánh số cần tìm với số ở giữa dãy số.
Em và bạn hãy thực hiện trò chơi mô phỏng thuật toán tìm kiếm nhị phân theo hướng dẫn sau:
a) Chuẩn bị 10 thẻ, mỗi thẻ ghi một số khác nhau. Sắp xếp các thẻ số thành một dãy trên mặt bàn theo thứ tự giá trị tăng dần của số ghi trên thẻ. Đặt úp mặt ghi số để không nhìn thấy số ghi trên các thẻ.
b) Em đề nghị bạn thực hiện thuật toán tìm kiếm nhị phân để tìm một số do em đưa ra.
c) Hoán đổi vai trò, em thực hiện tìm kiếm theo đề nghị của bạn.
Hãy sử dụng thuật toán tìm kiếm tuần tự để tìm trong lớp em có bạn cùng tháng sinh với em hay không. Có thể sử dụng danh sách lớp có ghi thông tin ngày sinh hoặc hỏi trực tiếp. Lập Bảng 2 vào vở và ghi kết quả thực hiện (dòng 1 là ví dụ minh hoạ).
Bảng 3 là danh sách hai số đầu biển số xe của một số tỉnh (tên tỉnh đã được sắp xếp theo thứ tự trong bảng chữ cái).
a) Áp dụng thuật toán tìm kiếm tuần tự để tìm ra tỉnh có hai số đầu của biển số xe là 25. Cho biết em đã thực hiện bao nhiêu lần lặp.
b) Áp dụng thuật toán tìm kiếm nhị phân để tìm hai số đầu tiên của biển số xe của tỉnh Lai Châu. Cho biết em đã thực hiện bao nhiêu lần lặp.
c) Số lần lặp em thực hiện ở câu a ít hơn hay ở câu b ít hơn? Tại sao?
d) Có thể áp dụng thuật toán tìm kiếm nhị phân để tìm ra tỉnh khi biết hai số đầu của biển số xe của tỉnh đó hay không? Tại sao?
Em tìm một từ tiếng Anh trong cuốn từ điển theo cách nào? Tại sao em dùng cách đó?
Hãy vận dụng thuật toán tìm kiếm nhị phân để xác định một bạn trong lớp được sinh vào ngày nào trong tháng với không quá 5 câu hỏi trắc nghiệm Đúng/Sai. Tương tự, để xác định một bạn được sinh vào tháng nào trong năm thì em cần dùng nhiều nhất bao nhiêu câu hỏi Đúng/Sai?
Họ và tên
Tiêu đề câu hỏi
Nội dung câu hỏi
0 Bình luận
Để lại bình luận
Địa chỉ email của hạn sẽ không được công bố. Các trường bắt buộc được đánh dấu *