Tìm kiếm tuần tự là gì? Cách tìm kiếm này được thực hiện như thế nào? Mời các em cùng tham khảo nội dung của Bài 1: Tìm kiếm tuần tự của chủ đề F trong chương trình Tin học 7 Cánh diều để có thể trả lời được các câu hỏi này.
- Quy trình để tìm một số trong dãy số không sắp thứ tự được minh hoa qua ví dụ sau:
Ví dụ: Cho dãy số 18, 94, 42, 06, 42, 44, 06, 55, 12, 67. Hãy tìm xem có số 44 trong dãy này hay không. Nếu có thì đưa ra vị trí đầu tiên tìm thấy.
Dãy xuất phát:
Gọi số phải tìm là x (x = 44). Các bước thực hiện tìm kiếm như sau:
Minh họa các bước tìm kiếm tuần tự
- Mô phỏng: Bài toán tìm kiếm tuần tự
Với x = 44
+ A[1] = 18 ≠ 44
+ A[2] = 94 ≠ 44
+ A[3] = 42 ≠ 44
+ A[4] = 44 = x
⇒ Với i = 4 thì A[4] = 44 = x
- Tình huống: Nếu thay x = 30 thì các bước tìm kiếm sẽ tiếp tục đến hết khi nào? Lúc đó câu trả lời cho bài toán tìm kiếm là gì?
⇒ Nếu thay x = 30 thì các bước tìm kiếm sẽ tiếp tục đến hết dãy (Bước 8) và cho kết luận “Không tìm thấy x trong dãy”
- Ý tưởng thuật toán tuần tự: Xuất phát từ đầu dãy, nếu có số ở đầu dãy không phải số cần tìm thì chuyển sang số tiếp theo, cứ thế cho đến khi tìm được hoặc xét hết dãy.
- Mô tả thuật toán:
Bài toán tìm kiếm trong dãy không sắp thứ tự
- Khi dãy không sắp thứ tự thì cần thực hiện tìm kiếm tuần tự.
- Ví dụ: Tập bài kiểm tra của lớp chưa được xếp theo thứ tự bảng chữ cái đối với tên học sinh, muốn tìm bài của em, giáo viên sẽ xem tên học sinh trên từng bài, cho đến bài của em.
Bài toán tìm kiếm trong dãy đã sắp thứ tự
Ví dụ: Tương tự như ví dụ trên, nếu danh sách tên học sinh trong lớp được xếp theo thứ tự chữ cái trong từ điển thì em có thể nhanh chóng thấy tên của mình.
Kết luận: Có hai loại bài toán tìm kiếm:
1) Tìm kiếm trong dãy không sắp thứ tự
2) Tìm kiếm trong dãy đã sắp thứ tự
- Bài toán tìm kiếm chia làm hai loại: tìm kiếm trong dãy không sắp thứ tự và tìm kiếm trong dãy đã sắp thứ tự. - Khi dãy không có thứ tự thì phải tìm kiếm tuần tự để đảm bảo không bỏ sót, cho đến khi tìm thấy hoặc hết dãy và không tìm thấy. |
---|
Bài tập 1: Trong thuật toán tìm kiềm tuần tự thao tác được lặp đi lặp lại là gì?
Hướng dẫn giải:
Thao tác so sánh từng phần tử của dãy với số cần tìm được lặp đi lặp lại cho tới khi tìm thấy kết quả hoặc tìm hết dãy.
Bài tập 2: Khi dãy không có thứ tự, ta áp dụng thuật toán tìm kiếm tuần tự để làm gì?
Hướng dẫn giải:
Dãy không có thứ tự ta áp dụng thuật toán tìm kiếm tuần tự để: Không bỏ sót cho đến khi tìm thấy hoặc tìm hết dãy và không tìm thấy.
Bài tập 3: Cho một dãy số: 12, 13, 32, 45, 33. Số lần so sánh trong bài toán “Tìm xem số 13 có trong dãy này không” là bao nhiêu?
Hướng dẫn giải:
Có 2 lần so sánh trong bài toán tìm kiếm trên vì:
- Lần 1: So sánh số đang xét ở đầu dây, kết quả = chưa tìm thấy.
- Lặp lần 2: So sánh số đang xét = 13, kết quả = tìm thấy
Qua bài học các em có thể:
- Mô phỏng được hoạt động của thuật toán tìm kiếm tuần tự trên một bộ dữ liệu đầu vào có kích thước nhỏ.
- Biết được khi dãy không có thứ tự thì phải tìm kiếm tuần tự.
- Biết được có hai loại bài toán tìm kiếm.
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 Cánh diều Chủ đề F Bài 1 cực hay có đáp án và lời giải chi tiết.
Trong thuật toán tìm kiếm tuần tự có mấy khả năng xảy ra khi kết thúc tìm kiếm tuần tự?
Trong thuật toán tìm kiếm tuần tự thao tác được lặp đi lặp lại là gì?
Có mấy loại bài toán tìm kiếm tuần tự?
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 Cánh diều Chủ đề F Bài 1để 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 78 SGK Tin học 7 Cánh diều - CD
Hoạt động trang 79 SGK Tin học 7 Cánh diều - CD
Luyện tập trang 80 SGK Tin học 7 Cánh diều - CD
Vận dụng 1 trang 80 SGK Tin học 7 Cánh diều - CD
Vận dụng 2 trang 80 SGK Tin học 7 Cánh diều - CD
Câu hỏi tự kiểm tra 1 trang 80 SGK Tin học 7 Cánh diều - CD
Câu hỏi tự kiểm tra 2 trang 80 SGK Tin học 7 Cánh diều - CD
Câu hỏi tự kiểm tra 3 trang 80 SGK Tin học 7 Cánh diều - CD
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
Trong thuật toán tìm kiếm tuần tự có mấy khả năng xảy ra khi kết thúc tìm kiếm tuần tự?
Trong thuật toán tìm kiếm tuần tự thao tác được lặp đi lặp lại là gì?
Có mấy loại bài toán tìm kiếm tuần tự?
Cho một dãy số: 12, 13, 32, 45, 33. Số lần so sánh trong bài toán “Tìm xem số 13 có trong dãy này không” là bao nhiêu?
Cho một dãy số: 12, 14, 32, 45, 3. Kết quả của bài toán “Tìm xem số 13 có trong dãy này không” là gì?
Trong thuật toán tìm kiếm tuần tự, việc tìm kiếm sẽ dừng khi nào?
Có 2 loại bài toán tìm kiếm đó là gì?
Cho một dãy số:
Em hãy sắp xếp từng bước của thuật toán giải bài toán “Tìm xem số 45 có trong dãy này không?
1. Gọi số phải tìm là x(x=45). Số đang xét là số ở đầu dãy: Kết quả chưa tìm thấy
2. Lặp khi (chưa xét hết dãy số) và (Kết quả = chưa tìm thấy):
Nếu số đang xét # x: chuyển đến số tiếp theo trong dãy.
Trái lại: Kết quả = tìm thấy: Thông báo vị trí tìm thấy x
Hết nhánh
Hết lặp
3. Nếu kết quả = chưa tìm thấy: Thông báo không có x trong dãy
Hết nhánh
Khả năng xảy ra khi thực hiện tìm kiếm tuần tự là gì?
Khi nào thì việc tìm kiếm tuần tự dò tìm đến phân tử ở cuồi dãy?
Giáo viên dạy Tin học lớp 7A trả kết quả bài kiểm tra và thông báo “Trong lớp có duy nhất một bạn đạt điểm 10". Xem danh sách lớp kèm cột điểm kiểm tra, em làm thế nào để biết ai được điểm 10?
Với dãy số đã cho ở ví dụ trên, em hãy thực hiện thuật toán được mô tả ở hình bên và cho biết đó có phải là thuật toán tìm kiếm tuần tự hay không?
Cho dãy số
Em hãy thể hiện từng bước của thuật toán giải bài toán “Tìm xem số 45 có trong dãy này không? Nếu có thì nằm ở vị trí nào?”.
Em có cách nào khác để giải bài toán tìm kiếm trong dãy không sắp thứ tự không? Tại sao?
Em có thể áp dụng thuật toán tìm kiếm tuần tự cho dãy đã sắp thứ tự không? Tại sao?
Hai khả năng xảy ra khi kết thúc tìm kiếm tuần tự là gì?
Khi nào thì việc tìm kiếm tuần tự kết thúc ở giữa chừng của dãy?
Khi nào thì việc tìm kiếm tuần tự dò tìm đến phần từ cuối dãy?
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 *