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$_{1}$ = 8 khác x nên chuyển sang xét số tiếp theo a$_{2}$ trong dãy.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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