Giải bài tập sách bài tập (SBT) tin học lớp 7 Cánh diều 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 mô phỏng các thuật toán tìm kiếm, sắp xếp

Trong bài toán tìm kiếm tuần tự, chúng ta cần tìm một phần tử trong dãy số đã cho. Ví dụ, chúng ta cần tìm số 39 trong dãy số {11, 70, 18, 39, 63, 52, 41, 5}.

Quá trình tìm kiếm sẽ diễn ra như sau:

• So sánh từng phần tử trong dãy với số cần tìm.
• Nếu phần tử nào trùng khớp với số cần tìm, chúng ta sẽ kết thúc việc tìm kiếm và thông báo vị trí của số trong dãy.

Ví dụ, khi tìm số 39 trong dãy số ta sẽ thực hiện các bước sau:

• So sánh 11 với 39 (không trùng khớp), tiếp tục so sánh với các phần tử còn lại
• So sánh 70 với 39 (không trùng khớp), tiếp tục so sánh với các phần tử còn lại
• So sánh 18 với 39 (không trùng khớp), tiếp tục so sánh với các phần tử còn lại
• Kết thúc khi tìm thấy số 39 tại vị trí thứ 4 trong dãy.

Trong thuật toán sắp xếp chọn dần, chúng ta cần sắp xếp dãy số theo thứ tự tăng dần hoặc giảm dần. Ví dụ, đề bài yêu cầu sắp xếp dãy số {11, 70, 18, 39, 63, 52, 41, 5} theo thứ tự giảm dần.

Quá trình sắp xếp sẽ diễn ra như sau:

• Chọn phần tử nhỏ nhất hoặc lớn nhất trong dãy và đặt lên vị trí đầu tiên của dãy đã sắp xếp.
• Lặp lại quá trình trên với các phần tử còn lại cho đến khi dãy đã được sắp xếp hoàn chỉnh

Ví dụ, khi sắp xếp dãy số trên theo thứ tự giảm dần, chúng ta sẽ có kết quả là {70, 63, 52, 41, 39, 18, 11, 5}.

Đối với thuật toán tìm kiếm nhị phân, chúng ta chia dãy số ra làm hai phần và tìm kiếm phần tử trong phần đã được chia. Ví dụ, khi tìm số 60 trong dãy số {5, 11, 18, 39, 41, 52, 63, 70}, quá trình sẽ diễn ra như sau:

• Chia dãy số thành hai phần và so sánh với phần tử giữa dãy.
• Xác định vị trí của phần tử cần tìm trong dãy hoặc kết luận không tìm thấy nếu không có trong dãy.

Qua các ví dụ trên, chúng ta có thể thấy cách thức hoạt động của các thuật toán tìm kiếm và sắp xếp trong tin học.