Bài tập Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp có đáp á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.

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

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

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

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

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

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

Bước 7. So sánh số ở đầu dãy với x. Vì a₇ = 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ì a₁ = 8 khác x nên chuyển sang xét số tiếp theo a₂ trong dãy.

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

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

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

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

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

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

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

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

Bước 10. So sánh số ở đầu dãy với x. Vì a₁₀ = 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.

1) x = 5 

Bước 1. Chia đôi phạm vi tìm kiếm từ đầu dãy a1 đến a10.

Bước 2. Lấy a5 là vị trí cần chia đôi. Vì a5 > x. Ta sẽ thu hẹp được phạm vi tìm kiếm. Từ a1 đến a5 chắc chắn sẽ không chứa x cần tìm. Kết quả: Tìm thấy số x tại vị trí a8.

Bước 3. Lấy a8 là vị trí cần chia đôi. Khi ta chia đôi ở a8 ta thấy vị trí số x.

2) x = 6 

Bước 1. Chia đôi phạm vi tìm kiếm từ đầu dãy a1 đến a10.

Bước 2. Lấy a5 là vị trí cần chia đôi. Vì a5 > x. Ta sẽ thu hẹp được phạm vi tìm kiếm. Từ a1 đến a5 chắc chắn sẽ không chứa x cần tìm.

Bước 3. Lấy a8 là vị trí cần chia đôi. Ta sẽ thu hẹp được phạm vi tìm kiếm. Từ a8 đến a10 chắc chắn sẽ không chứa x cần tìm. Khi đó chỉ còn vị trí a6 và a7, thì ta kiểm tra không có số x cần tìm. Kết quả: Không tìm thấy số x.

Em sẽ lựa chọn thuật toán sắp xếp nổi bọt vì sắp xếp chọn hay nổi bọt đều như nhau, đều dùng phép so sánh để đưa ra kết quả lớn nhất và đổi chỗ vị trí với nhau. Nhưng khi dùng sắp xếp nổi bọt thì em thấy bước cuối cùng sẽ duyệt mảng lần nữa sẽ chắc chắn là mảng đó đã được sắp xếp theo thứ tự tăng hoặc giảm.