Lý thuyết 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
Bài 1: Cho dãy số ban đầu
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. 1) Tìm x = 5. 2) Tìm x = 6. Hướng dẫn:
1) Đối với bài này ta sẽ sử dụng thuật toán tìm kiếm tuần tự để trình bày. Dãy a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 Giải thích (a)
So sánh số ở đầu dãy với x. Ban
Vì a1 = 8 khác x nên chuyển sang 8 17 23 1 12 7 5 1 13 10 đầu
xét số tiếp theo a2 trong dãy.
So sánh số ở đầu dãy với x. Sau
Vì a2 = 17 khác x nên chuyển sang 8 17 23 1 12 7 5 1 13 10 bước 1
xét số tiếp theo a3 trong dãy.
So sánh số ở đầu dãy với x. Sau 8 17 23 1 12 7 5
1 13 10 Vì a3 = 23 khác x nên chuyển sang bước 2
xét số tiếp theo a4 trong dãy.
So sánh số ở đầu dãy với x. Sau 8 17 23 1 12 7 5 1 13 10
Vì a4 = 1 khác x nên chuyển sang bước 3
xét số tiếp theo a5 trong dãy. Sau 8 17 23 1 12 7 5
1 13 10 So sánh số ở đầu dãy với x.


Vì a5 = 12 khác x nên chuyển sang bước 4
xét số tiếp theo a6 trong dãy.
So sánh số ở đầu dãy với x. Sau 8 17 23 1 12 7 5
1 13 10 Vì a6 = 7 khác x nên chuyển sang bước 5
xét số tiếp theo a7 trong dãy.
So sánh số ở đầu dãy với x. Sau
Vì a7 = 5 bằng x. Kết luận tìm 8 17 23 1 12 7 5 1 13 10 bước 6
thấy x ở vị trí thứ 7 trong dãy, kết thúc thuật toán.
2) Đối với bài này ta sẽ sử dụng thuật toán tìm kiếm tuần tự để trình bày. Dãy a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 Giải thích (a)
So sánh số ở đầu dãy với x. Ban
Vì a1 = 8 khác x nên chuyển sang 8 17 23 1 12 7 5 1 13 10 đầu
xét số tiếp theo a2 trong dãy.
So sánh số ở đầu dãy với x. Sau 8 17 23 1 12 7 5
1 13 10 Vì a2 = 17 khác x nên chuyển sang bước 1
xét số tiếp theo a3 trong dãy.
So sánh số ở đầu dãy với x. Sau 8 17 23 1 12 7 5
1 13 10 Vì a3 = 23 khác x nên chuyển sang bước 2
xét số tiếp theo a4 trong dãy.
So sánh số ở đầu dãy với x. Sau 8 17 23 1 12 7 5
1 13 10 Vì a4 = 1 khác x nên chuyển sang bước 3
xét số tiếp theo a5 trong dãy. Sau 8 17 23 1 12 7 5
1 13 10 So sánh số ở đầu dãy với x. bước 4
Vì a5 = 12 khác x nên chuyển sang


xét số tiếp theo a6 trong dãy.
So sánh số ở đầu dãy với x. Sau
Vì a6 = 7 khác x nên chuyển sang 8 17 23 1 12 7 5 1 13 10 bước 5
xét số tiếp theo a7 trong dãy.
So sánh số ở đầu dãy với x. Sau 8 17 23 1 12 7 5
1 13 10 Vì a7 = 5 khác x nên chuyển sang bước 6
xét số tiếp theo a8 trong dãy.
So sánh số ở đầu dãy với x. Sau
Vì a8 = 1 khác x nên chuyển sang 8 17 23 1 12 7 5 1 13 10 bước 7
xét số tiếp theo a9 trong dãy.
So sánh số ở đầu dãy với x. Sau
Vì a9 = 13 khác x nên chuyển sang 8 17 23 1 12 7 5 1 13 10 bước 8
xét số tiếp theo a10 trong dãy.
So sánh số ở đầu dãy với x.
Vì a10 = 10 khác x, ta đã duyệt đến Sau 8 17 23 1 12 7 5
1 13 10 cuối dãy những không tìm thấy bước 9
x = 6. Kết luận: Không tìm thấy phần tử x = 6.
Bài 2: Cho dãy số ban đầu như trong 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.

Hướng dẫn:
Cánh làm: tìm số lớn dãy trong dãy đưa lên đầu dãy. Chọn số lớn nhất trong dãy số còn
lại và đổi chỗ nó với số đứng đầu dãy này cho đến khi hết dãy ban đầu. Dãy a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 Giải thích (a) Ban
Tiếp theo đổi chỗ 23 và a1 vì 23 8 17 23 1 12 7 5 1 13 10 đầu
là số lớn nhất trong dãy
Tiếp theo không đổi chỗ vì từ a2 Sau 23 17 8 1 12 7 5 1
13 10 thì số lớn nhất là 17 đang ở vị trí bước 1 a2.
Tiếp theo đổi chỗ 13 và a3 vì từ vị Sau 23 17 8 1 12 7 5 1
13 10 trí a3 thì số lớn nhất là 13 đang ở bước 2
vị trí a9 nên cần đổi chỗ a3 và a9. Sau 23 17 13 1 12 7 5 1 8
10 Tiếp theo đổi chỗ 12 và a4 bước 3 Sau 23 17 13 12 1 7 5 1 8
10 Tiếp theo đổi chỗ 10 và a5 bước 4 Sau 23 17 13 12 10 7 5 1 8 1
Tiếp theo đổi chỗ 8 và a6 bước 5 Sau 23 17 13 12 10 8 5 1 7 1
Tiếp theo đổi chỗ 7 và a7 bước 6 Sau 23 17 13 12 10 8 7 1 5 1
Tiếp theo đổi chỗ 5 và a8 bước 7 Sau 23 17 13 12 10 8 7 5 1 1
Tiếp theo không đổi chỗ bước 8 Sau 23 17 13 12 10 8 7 5 1 1
Tiếp theo không đổi chỗ bước 9