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.
Trả lời:
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 $\neq $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 $\neq $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 $\neq $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 $\neq $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 $\neq $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 $\neq $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 $\neq $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". |
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.
Trả lời:
|
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 |
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.
Trả lời:
|
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 |
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.
Trả lời:
1) Số phải tìm là x = 39:
|
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 |
|
|
|
|
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 (có nền màu xám nhạt) 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 (có nền màu xám nhạt) 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 (có nền màu xám nhạt) 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.