Hãy mô phỏng thuật toán tìm kiếm nhị phân trong dãy số đã sắp thứ tự là kết quả của Bài 2 và Bài 3
Giải Tin học lớp 7 Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp
Haylamdo biên soạn và sưu tầm lời giải Luyện tập 4 trang 90 Tin học lớp 7 Tin học lớp 7 trong Bài 5: Thực hành mô phỏng các thuật toán tìm kiếm, sắp xếp, lời giải chi tiết sẽ giúp học sinh biết cách làm bài tập Tin học 7.
Luyện tập 4 trang 90 Tin học lớp 7: Hãy mô phỏng thuật toán tìm kiếm nhị phân trong dãy số đã sắp thứ tự là kết quả của Bài 2 và Bài 3
1) Tìm x = 5.
2) Tìm x = 6.
Trả lời:
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
|
Dãy kết quả |
23 |
17 |
13 |
12 |
10 |
8 |
7 |
5 |
1 |
1 |
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.