Bảng 3 là danh sách hai số đầu biển số xe của một số tỉnh (tên tỉnh đã được sắp xếp theo thứ tự bảng chữ cái)

Luyện tập 2 trang 75 Tin học lớp 7: Bảng 3 là danh sách hai số đầu biển số xe của một số tỉnh (tên tỉnh đã được sắp xếp theo thứ tự bảng chữ cái).

a) Áp dụng thuật toán tìm kiếm tuần tự để tìm ra tỉnh có hai số đầu của biển số xe là 25. Cho biết em đã thực hiện bao nhiêu lần lặp.

b) Áp dụng thuật toán tìm kiếm nhị phân để tìm hai số đầu tiên của biển số xe của tỉnh Lai Châu. Cho biết em đã thực hiện bao nhiêu lần lặp.

c) Số lần lặp em thực hiện ở câu a ít hơn hay ở câu b ít hơn? Tại sao?

d) Có thể áp dụng thuật toán tìm kiếm nhị phân để tìm ra tỉnh khi biết hai số đầu của biển số xe của tỉnh đó hay không? Tại sao?

Trả lời

a)

b)

- Lần lặp 1: Lật thẻ ở giữa dãy: Điện Biên. Do Lai Châu > Điện Biên nên ta tìm ở nửa sau của dãy gồm Gia Lai, Khánh Hoà, Lai Châu, Nam Định, Yên Bái.

- Lần lặp 2: Lật thẻ ở giữa dãy: Lai Châu = Lai Châu nên ta dừng thuật toán ở đây. Hai số đầu của tỉnh Lai Châu là 25

Có 2 lần lặp được thực hiện.

c) Số lần lặp ở câu b ít hơn. Câu b sử dụng thuật toán tìm kiếm nhị phân hạn chế được số lần lặp nên ít hơn câu a.

d) Có thể

Ví dụ tìm tỉnh biết 2 số đầu của biển số xe đó là 25:

- Sắp xếp các số theo thứ tự tăng dần 18, 21, 25, 27, 67, 69, 72, 77, 79, 81.

- Lần lặp 1: Lật thẻ ở giữa dãy: 67. Do 25 < 67 nên chỉ cần tìm ở nửa trước gồm 18, 21, 25, 27

- Lần lặp 2: Lật thẻ ở giữa dãy: 21. Do 25 > 21 nên ta tìm ở nửa sau gồm 25, 27.

- Lần lặp 3: Lật thẻ ở giữa dãy: 25. Do 25 = 25 nên ta dừng thuật toán. Tỉnh cần tìm là tỉnh Lai Châu

Có 3 lần lặp được thực hiện.

Xem thêm lời giải bài tập Tin học lớp 7 Chân trời sáng tạo hay, chi tiết khác:

Bài 9: Định dạng trang tính, chèn thêm và xóa hàng, cột

Bài 10: Sử dụng hàm để tính toán

Bài 11: Tạo bài trình chiếu

Bài 12: Sử dụng ảnh minh họa, hiệu ứng động trong bài trình chiếu

Bài 13: Thực toán tìm kiếm

Bài 14: Thuật toán sắp xếp