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

Hướng dẫn giải

tham khảo

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.

Bước 1. So sánh số ở đầu dãy với x. Vì a1 = 8 khác x nên chuyển sang xét số tiếp theo a2 trong dãy.

Bước 2. So sánh số ở đầu dãy với x. Vì a2 = 17 khác x nên chuyển sang xét số tiếp theo a3 trong dãy.

Bước 3. So sánh số ở đầu dãy với x. Vì a3 = 23 khác x nên chuyển sang xét số tiếp theo a4 trong dãy.

Bước 4. So sánh số ở đầu dãy với x. Vì a4 = 1 khác x nên chuyển sang xét số tiếp theo a5 trong dãy.

Bước 5. So sánh số ở đầu dãy với x. Vì a5 = 12 khác x nên chuyển sang xét số tiếp theo a6 trong dãy.

Bước 6. So sánh số ở đầu dãy với x. Vì a6 = 7 khác x nên chuyển sang xét số tiếp theo a7 trong dãy.

Bước 7. So sánh số ở đầu dãy với x. Vì a7 = 5 bằng 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.

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.

Bước 1. So sánh số ở đầu dãy với x. Vì a1 = 8 khác x nên chuyển sang xét số tiếp theo a2 trong dãy.

Bước 2. So sánh số ở đầu dãy với x. Vì a2 = 17 khác x nên chuyển sang xét số tiếp theo a3 trong dãy.

Bước 3. So sánh số ở đầu dãy với x. Vì a3 = 23 khác x nên chuyển sang xét số tiếp theo a4 trong dãy.

Bước 4. So sánh số ở đầu dãy với x. Vì a4 = 1 khác x nên chuyển sang xét số tiếp theo a5 trong dãy.

Bước 5. So sánh số ở đầu dãy với x. Vì a5 = 12 khác x nên chuyển sang xét số tiếp theo a6 trong dãy.

Bước 6. So sánh số ở đầu dãy với x. Vì a6 = 7 khác x nên chuyển sang xét số tiếp theo a7 trong dãy.

Bước 7. So sánh số ở đầu dãy với x. Vì a7 = 5 khác x nên chuyển sang xét số tiếp theo a8 trong dãy.

Bước 8. So sánh số ở đầu dãy với x. Vì a8 = 1 khác x nên chuyển sang xét số tiếp theo a9 trong dãy.

Bước 9. So sánh số ở đầu dãy với x. Vì a9 = 13 khác x nên chuyển sang xét số tiếp theo a10 trong dãy.

Bước 10. So sánh số ở đầu dãy với x. Vì a10 = 10 khác x, ta đã duyệt đến cuối dãy những không tìm thấy x = 6.

Kết luận: Không tìm thấy phần tử x = 6.

(Trả lời bởi Mai Trung Hải Phong)

Hướng dẫn giải

tham khảo

Dãy (a)	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	Giải thích
Ban đầu	8	17	23	1	12	7	5	1	13	10	Tiếp theo đổi chỗ 23 và a1
Sau bước 1	23	17	8	1	12	7	5	1	13	10	Tiếp theo không đổi chỗ
Sau bước 2	23	17	8	1	12	7	5	1	13	10	Tiếp theo đổi chỗ 13 và a3
Sau bước 3	23	17	13	1	12	7	5	1	8	10	Tiếp theo đổi chỗ 12 và a4
Sau bước 4	23	17	13	12	1	7	5	1	8	10	Tiếp theo đổi chỗ 10 và a5
Sau bước 5	23	17	13	12	10	7	5	1	8	1	Tiếp theo đổi chỗ 8 và a6
Sau bước 6	23	17	13	12	10	8	5	1	7	1	Tiếp theo đổi chỗ 7 và a7
Sau bước 7	23	17	13	12	10	8	7	1	5	1	Tiếp theo đổi chỗ 5 và a8
Sau bước 8	23	17	13	12	10	8	7	5	1	1	Tiếp theo không đổi chỗ
Sau bước 9	23	17	13	12	10	8	7	5	1	1	Tiếp theo không đổi chỗ
Dãy kết quả	23	17	13	12	10	8	7	5	1	1

(Trả lời bởi Mai Trung Hải Phong)

Hướng dẫn giải

tham khảo

Dãy (a)	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	Giải thích
Ban đầu	8	17	23	1	12	7	5	1	13	10	Tiếp theo so sánh a1 và a2, a2 > a2 đổi chổ a1 và a2
Sau bước 1	17	8	23	1	12	7	5	1	13	10	Tiếp theo so sánh a2 và a3, a3 > a2 đổi chổ a2 và a3
Sau bước 2	17	23	8	1	12	7	5	1	13	10	Tiếp theo so sánh a3 và a4, a3 > a4 giữ nguyên vị trí
Sau bước 3	17	23	8	1	12	7	5	1	13	10	Tiếp theo so sánh a4 và a5, a5 > a4 đổi chổ a4 và a5
Sau bước 4	17	23	8	12	1	7	5	1	13	10	Tiếp theo so sánh a5 và a6, a6 > a5 đổi chổ a5 và a6
Sau bước 5	17	23	8	12	7	1	5	1	13	10	Tiếp theo so sánh a6 và a7, a7 > a6 đổi chổ a6 và a7
Sau bước 6	17	23	8	12	7	5	1	1	13	10	Tiếp theo so sánh a7 và a8, a7 = a8 giữ nguyên vị trí
Sau bước 7	17	23	8	12	7	5	1	1	13	10	Tiếp theo so sánh a8 và a9, a9 > a8 đổi chổ a8 và a9
Sau bước 8	17	23	8	12	7	5	1	13	1	10	Tiếp theo so sánh a9 và a10, a10 > a9 đổi chổ a9 và a10
Sau bước 9	17	23	8	12	7	5	1	13	10	1	Tiếp theo ta quay lại lại bước 1và thực hiện vòng lặp tương tự.
Dãy kết quả	23	17	13	12	10	8	7	5	1	1

(Trả lời bởi Mai Trung Hải Phong)

Hướng dẫn giải

Thì chúng ta sẽ chia đôi ra và tìm cho đến khi nào tìm ra số đó hoặc không thể chia đôi được nữa là đc kết quả của bài toán

a: 

CHia đôi lần 1: Chúng ta sẽ lấy số a₅. Vì 6<a₅ nên sẽ chạy về phía bên phải của a₅.

Chia đôi lần 2: Lần này chúng ta sẽ chạy từ a6 đến a10. Vì x=a₈ nên kết thúc bài

b: Chia đôi lần 1: Chúng ta sẽ lấy số a5. Vì x<a₅ nên sẽ chạy về phía bên phải của a₅

Chia đôi lần 2: Chúng ta sẽ chạy từ a6 đến a10. Lấy số a8 nằm ở chính giữa. Vì x>a8 nên sẽ chạy về phía bên trái của a8

Chia đôi lần 3: Tương tự lần 2

=>Không tìm được kết quả

(Trả lời bởi Nguyễn Lê Phước Thịnh)

Hướng dẫn giải

sẽ chọn sắp xếp nổi bọt. Vì bản chất thì hai thuật toán này là như nhau, nhưng nếu chọn nổi bọt thì cái dãy khi mình quét lại chắc chắn đã sắp xếp giảm dần hoặc tăng dần rồi

(Trả lời bởi Nguyễn Lê Phước Thịnh)