Bài 5. Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp trang 39 SBT Tin Học lớp 7 – Cánh Diều, mời các em tham khảo cùng Bumbii.
Bài 5. Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp
Câu F19
Hãy trình bày diễn biến từng bước của thuật toán tìm kiếm tuần tự áp dụng cho dãy số {11, 70, 18, 39, 63, 52, 41, 5} để tìm:
1) x = 39.
2) x = 60.
Đáp án:
Dãy xuất phát:
| Dãy | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
| 11 | 70 | 18 | 39 | 63 | 52 | 41 | 5 |
1) Số phải tìm là x (x = 39). Các bước thực hiện tìm kiếm:
| Bước | Thực hiện |
| 1 | So sánh số ở đầu dãy với x: Vì a1 = 11 ≠ 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 = 70 ≠ 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 = 18 ≠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 = 39 = x Kết luận: Tìm thấy x ở vị trí thứ 4 trong dãy; kết thúc thuật toán. |
2) Số phải tìm là x (x = 60). Các bước thực hiện tìm kiếm:
| Bước | Thực hiện |
| 1 | So sánh số ở đầu dãy với x: Vì a1 = 11 ≠ 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 = 70 ≠ 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 = 18 ≠ x nên chuyển sang xét số tiếp theo a4 trong dãy. |
| … | |
| 8 | So sánh số đang xét với x: Vì a8= 55 ≠ x và không chuyển số tiếp theo được nữa vì hết dãy. Kết quả “Không tìm thấy”. |
Câu F20
Hãy trình bày diễn biến từng bước của thuật toán sắp xếp chọn dần áp dụng cho dãy số {11, 70, 18, 39, 63, 52, 41, 5} để được dãy số giảm dần.
Đáp án:
| Dãy (a) | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
| Ban đầu, i = 1 | 11 | 70 | 18 | 39 | 63 | 52 | 41 | 5 |
| Sau bước 1, i = 2 | 70 | 11 | 18 | 39 | 63 | 52 | 41 | 5 |
| Sau bước 2, i = 3 | 70 | 63 | 18 | 39 | 11 | 52 | 41 | 5 |
| Sau bước 3, i = 4 | 70 | 63 | 52 | 39 | 11 | 18 | 41 | 5 |
| Sau bước 4, i = 5 | 70 | 63 | 52 | 41 | 11 | 18 | 39 | 5 |
| Sau bước 5, i = 6 | 70 | 63 | 52 | 41 | 39 | 18 | 11 | 5 |
| Sau bước 6, i = 7 | 70 | 63 | 52 | 41 | 39 | 18 | 11 | 5 |
| Sau bước 7 | 70 | 63 | 52 | 41 | 39 | 18 | 11 | 5 |
| Dãy kết quả | 70 | 63 | 52 | 41 | 39 | 18 | 11 | 5 |
Câu F21
Hãy trình bày diễn biến từng bước của thuật toán sắp xếp chọn dần áp dụng cho dãy số {11, 70, 18, 39, 63, 52, 41, 5} để được dãy số tăng dần.
Đáp án:
| Xuất phát, i=1 | 11 | 70 | 18 | 39 | 63 | 52 | 41 | 5 |
| Lượt thứ nhất | 11 | 18 | 39 | 63 | 52 | 41 | 5 | 70 |
| Lượt thứ hai | 11 | 18 | 39 | 52 | 41 | 5 | 63 | 70 |
| Lượt thứ ba | 11 | 18 | 39 | 41 | 5 | 52 | 63 | 70 |
| Lượt thứ tư | 11 | 18 | 39 | 5 | 41 | 52 | 63 | 70 |
| Lượt thứ năm | 11 | 18 | 5 | 39 | 41 | 52 | 63 | 70 |
| Lượt thứ sáu | 11 | 5 | 18 | 39 | 41 | 52 | 63 | 70 |
| Lượt thứ bảy | 5 | 11 | 18 | 39 | 41 | 52 | 63 | 70 |
| Lượt thứ tám | 5 | 11 | 18 | 39 | 41 | 52 | 63 | 70 |
| Dãy kết quả | 5 | 11 | 18 | 39 | 41 | 52 | 63 | 70 |
Câu F22
Cho dãy số {5, 11, 18, 39, 41, 52, 63, 70}. Hãy trình bày diễn biến từng bước của thuật toán tìm kiếm nhị phân để tìm kiếm x trong dãy.
1) x = 39
2) x = 60.
Đáp án:
| Dãy (a) | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
| Xuất phát | 5 | 11 | 18 | 39 | 41 | 52 | 63 | 70 |
| Bước 1 | 5 | 11 | 18 | 39 |
1) Số phải tìm là x = 39:
Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a1 đến a8. Lấy a4 là số có vị trí giữa dãy. Vì x = a4 nên đã tìm thấy x = 39 tại vị trí thứ 4.
2) Số phải tìm là x = 60.
| Dãy (a) | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
| Xuất phát | 5 | 11 | 18 | 39 | 41 | 52 | 63 | 70 |
| Bước 1 | 41 | 52 | 63 | 70 | ||||
| 63 | 70 | |||||||
| 63 |
Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a1 đến a8. Lấy a4 là số có vị trí giữa dãy.
Vì x > a4 nên nửa đầu dãy chắc chắn không chứa x = 60, tiếp theo chỉ cần 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 con từ a5 đến a8.
Chia đôi lần 2: lấy a6 là số có vị trí giữa dãy còn lại.
Vì x > a6 nên nửa đầu dãy chắc chắn không chứa x = 60, tiếp theo chỉ cần 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 con từ a7 đến a8.
Chia đôi lần 3: lấy a7 là số có vị trí giữa dãy còn lại.
Vì x < a7 nên nửa sau dãy chắc chắn không chứa x = 60, tiếp theo chỉ cần tìm trong nửa dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con một phần tử a7.
Chỉ còn một phần tử, không chia đôi nữa, so sánh thấy x khác a. Kết luận: Không tìm thấy.
Xem thêm các bài khác tại Giải sách bài tập tin học lớp 7 – NXB Cánh Diều
Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech
Không bao giờ từ bỏ hy vọng. Cố gắng mỗi ngày.