Cùng DapAnHay 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!
* 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 |
* 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:
* 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
* 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.
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ỏ.
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.
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ự?
Với 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?
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ì?
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 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
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ó bao nhiêu khả năng xảy ra khi kết thúc tìm kiếm tuần tự?
Với 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?
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ì?
Bài toán nào dưới đây áp dụng được thuật toán tìm kiếm nhị phân?
Với dãy số 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy” có phạm vi tìm kiếm là ở khoảng nào?
Cho một dãy số:
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
Khi thực hiện bài toán sắp xếp giảm dần dãy số 11, 70, 20, 39, 80, 52, 41, 5. Ở bước đầu tiên của sắp xếp chọn ta cần đổi chỗ phân tử 80 cho phần tử nào?
Muốn tìm vị trí số lớn nhất của dãy 3, 7, 9, 2 ta có bao nhiêu bước so sánh?
Với dãy 2, 4, 3, 8, 1. Để sắp xếp dãy tăng dần theo thuật toán sắp xếp nổi bọt, phần tử 8 có bao nhiêu lần đổi chỗ?
Khi sắp xếp dãy 1, 4, 2, 6 theo thứ tự tăng dân bằng thuật toán nổi bọt thì có bao nhiêu lần đổi chỗ hai phân tử liền kề?
Nếu được yêu cầu sắp xếp một dãy số, em lựa chọn thuật toán sắp xếp chọn hay sắp xếp nổi bọt? Giải thích tại sao.
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 *