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ự trong bảng chữ cái)
Câu hỏi :
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ự trong 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?
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ự trong 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?
* Đáp án
* Hướng dẫn giải
a) Biển số xe cần tìm là 25.
|
Lần lặp |
Biển số xe tỉnh |
Cùng biển số xe |
Danh sách tìm kết toàn bộ bảng |
|
1 |
67 |
Sai |
Sai |
|
2 |
72 |
Sai |
Sai |
|
3 |
77 |
Sai |
Sai |
|
4 |
69 |
Sai |
Sai |
|
5 |
27 |
Sai |
Sai |
|
6 |
81 |
Sai |
Sai |
|
7 |
79 |
Sai |
Sai |
|
8 |
25 |
Đúng |
Sai |
|
Sau 8 lần lặp đã tìm được kết quả. Kết thúc tìm kiếm. |
|||
b)
Bước 1. Sắp xếp biển số xe theo thứ tự tăng dần hoặc giảm dần.
Bảng. Biển số xe tăng dần
Bước 2. Lật thẻ số ở giữa của dãy (thẻ thứ 5). So sánh số cần tìm là 25 trên thẻ vừa lật là 67. Do 25 < 67 nên chỉ cần tìm ở nửa đầu của dãy thẻ (gồm 1, 2, 3, 4)
Bước 4. Lật thẻ số ở giữa của dãy (thẻ thứ 2). So sánh số cần tìm là 25 trên thẻ vừa lật là 21. Do 25 > 21 nên số cần tìm ở nửa sau của dãy thẻ (vị trí số 3, 4).
Bước 5. Lật thẻ vị trí số 3. So sánh số cần tìm là 25 trên thẻ vừa lật là 25. Do 25 = 25 nên đưa ra thông báo đã tìm thấy kết quả. Kết thúc quá trình tìm kiếm.
c) Số lần lặp lại ở câu b ít hơn câu a. Vì tìm kiếm nhị phân chia nhỏ mảng tìm kiếm nên số lần lặp ít hơn.
d) Ta có thể 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. Vì khi thực hiện tìm kiếm ta sẽ chia nhỏ mảng số và tìm được số cần tìm.
Bạn có biết?
Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.
Nguồn : Wikipedia - Bách khoa toàn thưTâm sự Lớp 7
Lớp 7 - Năm thứ hai ở cấp trung học cơ sở, một cuồng quay mới lại đến vẫn bước tiếp trên đường đời học sinh. Học tập vẫn là nhiệm vụ chính!
Nguồn : ADMIN :))Copyright © 2021 HOCTAPSGK