Cùng HOC247 củng cố các kiến thức về thuật toán tìm kiếm và sắp xếp thông qua nội dung của Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp trong chủ đề F của chương trình Tin học 7 Cánh diều. Nội dung chi tiết các em tham khảo nội dung bài giảng dưới đây!
Tóm tắt lý thuyết
1.1. Tìm hiểu bài 1
* Yêu cầu:
Cho dãy số ban đầu như sau:
Hãy mô phỏng thuật toán tìm kiếm tuần tự một số trong dãy số bằng cách trình bày diễn biến các bước thực hiện dưới dạng bảng.
a. Tìm x = 5.
b. Tìm x = 6.
* Hướng dẫn thực hiện:
a. x = 5
- Bước 1:
So sánh số ở đầu dãy với x
Vì a1 = 8 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy
- Bước 2:
So sánh số đang xét với x
Vì a2 = 17 ≠ x nên chuyển sang xét số tiếp theo a3 trong dãy
- Bước 3:
So sánh số đang xét với x
Vì a3 = 23 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy
- Bước 4:
So sánh số đang xét với x
Vì a4 = 1 ≠ x nên chuyển sang xét số tiếp theo a5 trong dãy
- Bước 5:
So sánh số đang xét với x
Vì a5 = 12 ≠ x nên chuyển sang xét số tiếp theo a6 trong dãy
- Bước 6:
So sánh số đang xét với x
Vì a6 = 7 ≠ x nên chuyển sang xét số tiếp theo a7 trong dãy
- Bước 7:
So sánh số đang xét với x
Vì a7 = 5 = x
Kết luận: Tìm thấy x ở vị trí thứ 7 trong dãy; kết thúc thuật toán
b. x = 6
Tương tự cách thực hiện câu a ta có:
|
Bước |
Thực hiện |
|
1 |
So sánh số ở đầu dãy với x Vì a1 = 8 ≠ x nên chuyển sang xét số tiếp theo a2 trong dãy |
|
2 |
So sánh số đang xét với x Vì a2 = 17 ≠ x nên chuyển sang xét số tiếp theo a3 trong dãy |
|
3 |
So sánh số đang xét với x Vì a3 = 23 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy |
|
4 |
So sánh số đang xét với x Vì a4 = 1 ≠ x nên chuyển sang xét số tiếp theo a5 trong dãy |
|
5 |
So sánh số đang xét với x Vì a5 = 12 ≠ x nên chuyển sang xét số tiếp theo a6 trong dãy |
|
6 |
So sánh số đang xét với x Vì a6 = 7 ≠ x nên chuyển sang xét số tiếp theo a7 trong dãy |
|
7 |
So sánh số đang xét với x Vì a7 = 5 ≠ x nên chuyển sang xét số tiếp theo a8 trong dãy |
|
8 |
So sánh số đang xét với x Vì a8 = 1 ≠ x nên chuyển sang xét số tiếp theo a9 trong dãy |
|
9 |
So sánh số đang xét với x Vì a9 = 13 ≠ x nên chuyển sang xét số tiếp theo a10 trong dãy |
|
10 |
So sánh số đang xét với x Vì a10 = 10 ≠ x. Hết dãy đã xét Kết luận: Không Tìm thấy x trong dãy; kết thúc thuật toán |
1.2. Tìm hiểu Bài 2
* Yêu cầu: Cho dãy số ban đầu như Bài 1. Bằng cách trình bày thông tin dưới dạng bảng, hãy mô phỏng diễn biến các bước của thuật toán sắp xếp chọn để sắp xếp dãy số theo chiều không tăng.
Gợi ý: Dựa theo các làm bài trong Bài “Sắp xếp chọn”.
* Hướng dẫn giải:
1.3. Tìm hiểu Bài 3
* Yêu cầu: Cho dãy số ban đầu như Bài 1. Bằng cách trình bày thông tin dưới dạng bảng, hãy mô phỏng diễn biến các bước của thuật toán sắp xếp nổi bọt để sắp xếp dãy số theo chiều không tăng.
Gợi ý: Dựa theo các làm bài trong Bài “Sắp xếp nổi bọt”.
* Hướng dẫn thực hiện:
Diễn biến các bước của thuật toán sắp xếp nổi bọt để sắp xếp dãy số theo chiều không tăng là:
- Lượt thứ nhất:
- Lượt thứ hai:
- Lượt thứ ba:
→ Tiếp tục quá trình cho đến khi thu được dãy giảm dần
1.4. Tìm hiểu Bài 4
* Yêu cầu: Hãy mô phỏng thuật toán tìm kiếm nhị phân trong dãy số đã sắp thứ tự là kết quả của Bài 2 và Bài 3.
a. Tìm x = 5.
b. Tìm x = 6.
* Hướng dẫn thực hiện:
a. Tìm x = 5
- Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a1 đến a10. Lấy a5 là số có vị trí giữa dãy; Vì x < a5 nên nửa đầu dãy chắc chắn không chứa x = 5, tiếp theo tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a6 đến a10.
- Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a6 đến a10. Lấy a8 là số có vị trí giữa dãy. Vì x = a8 nên kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ tám.
b. Tìm x = 6
- Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a1 đến a10. Lấy a5 là số có vị trí giữa dãy; Vì x < a5 nên nửa đầu dãy chắc chắn không chứa x = 6, tiếp theo tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a6 đến a10.
- Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a6 đến a10. Lấy a8 là số có vị trí giữa dãy. Vì x > a8 nên nửa sau dãy chắc chắn không chứa x = 6, tiếp theo tìm trong nửa đầu của dãy này. Như vậy, phạm vi tìm kiếm tiếp theo là dãy từ a5 đến a7.
- Chia đôi lần 3: Phạm vi tìm kiếm là dãy từ a5 đến a7. Lấy a6 là số có vị trí giữa dãy. Vì x < a6 nên nửa đầu dãy chắc chắn không chứa x = 6, tiếp theo tìm trong nửa sau của dãy này. Như vậy, phạm vi tìm kiếm tiếp theo là a7.
Phạm vi tìm kiếm chỉ còn một số nhưng không tìm thấy x. Kết thúc thuật toán với kết quả: Không có x trong dãy.
Luyện tập
Qua bài học các em có thể:
Mô phỏng được hoạt động của một số thuật toán tìm kiếm, sắp xếp bằng các bước thủ công (không cần dùng máy tính) trên một bộ dữ liệu có kích thước nhỏ.
2.1. Trắc nghiệm Bài 5 Chủ đề F Tin học 7 Cánh diều
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 5 cực hay có đáp án và lời giải chi tiết.
-
Câu 1:
Trong thuật toán tìm kiếm tuần tự có bao nhiêu khả năng xảy ra khi kết thúc tìm kiếm tuần tự?
- A. 1
- B. 2
- C. 3
- D. 4
-
- A. 1
- B. 2
- C. 3
- D. 4
-
Câu 3:
Kết quả của bài toán “Tìm xem số 13 có trong dãy này không” với dãy số: 12, 14, 32, 45, 3 là gì?
- A. Không tìm thấy
- B. Tìm thấy
- C. Tìm thấy ở đầu dãy
- D. Tìm thấy ở cuối dãy
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é!
2.2. Bài tập SGK Bài 5 Chủ đề F Tin học 7 Cánh diều
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 5 để 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.
Vận dụng trang 90 SGK Tin học 7 Cánh diều - CD
Hỏi đáp Bài 5 Chủ đề F Tin học 7 Cánh diều
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 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 7 HỌC247
