Chủ đề F. Bài 5. Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp

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
Dãy	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