Câu hỏi:
30/05/2022 491
Em và bạn hãy thực hiện trò chơi mô phỏng thuật toán tìm kiếm nhị phân theo hướng dẫn sau:
a) Chuẩn bị 10 thẻ, mỗi thẻ ghi một số khác nhau. Sắp xếp các thẻ số thành một dãy trên
mặt bàn theo thứ tự giá trị tăng dần của số ghi trên thẻ. Đặt úp mặt ghi số để không nhìn
thấy số ghi trên các thẻ.
b) Em đề nghị bạn thực hiện thuật toán tìm kiếm nhị phân để tìm một số do em đưa ra.
c) Hoán đổi vai trò, em thực hiện tìm kiếm theo đề nghị của bạn.
Em và bạn hãy thực hiện trò chơi mô phỏng thuật toán tìm kiếm nhị phân theo hướng dẫn sau:
a) Chuẩn bị 10 thẻ, mỗi thẻ ghi một số khác nhau. Sắp xếp các thẻ số thành một dãy trên
mặt bàn theo thứ tự giá trị tăng dần của số ghi trên thẻ. Đặt úp mặt ghi số để không nhìn
thấy số ghi trên các thẻ.
b) Em đề nghị bạn thực hiện thuật toán tìm kiếm nhị phân để tìm một số do em đưa ra.
c) Hoán đổi vai trò, em thực hiện tìm kiếm theo đề nghị của bạn.
Câu hỏi trong đề:
Bài tập Thực toán tìm kiếm có đáp án !!
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Các em tham khảo hướng dẫn sau:
Chuẩn bị 10 thẻ được đánh thứ từ từ A, B, C, D, E, F, G, H, K, L và sau thẻ đánh số tương ứng 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 xếp sắp theo thứ tự tăng dần.
a) Thẻ số tăng dần: Tìm số 8
|
Dãy thẻ số |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
Thứ tự |
A |
B |
C |
D |
E |
F |
G |
H |
K |
L |
Hình 2: Thẻ số tăng dần
b)
Gọi số cần tìm là x = 8.
Bước 1. Lật thẻ ở vị trí E (E = 5).
Bước 2. So sánh số thấy vị trí E khác vị trí cần tìm (8 > 5) nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm F, G, H, K, L).
Bước 3. Lật thẻ vị trí H (H = 8).
Bước 4. So sánh số thấy vị trí H bằng với kết quả cần tìm. Kết quả tìm thấy số 8 trong dãy ở vị trí H và kết thúc quá trình tìm kiếm.
c) Thay đổi vai trò
Gọi số cần tìm là x = 10.
Bước 1. Lật thẻ ở vị trí E (E = 5).
Bước 2. So sánh số thấy vị trí E khác vị trí cần tìm (10 > 5) nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm F, G, H, K, L).
Bước 3. Lật thẻ vị trí H (H = 8).
Bước 4. So sánh số thấy vị trí H khác vị trí cần tìm (10 > 8). Nên ta chỉ cần tìm ở nữa sau của dãy thẻ (gồm K, L).
Bước 5. Ta lật ngẫu nhiên vị trí K hoặc L.
+ TH1: Lật thẻ vị trí K: So sánh số thấy vị trí K khác vị trí cần tìm (10 > 9). Tiếp theo ta lật thẻ còn lại, so sánh số thấy vị trí L bằng với kết quả cần tìm. Kết quả tìm thấy số 10 trong dãy ở vị trí L và kết thúc quá trình tìm kiếm.
+ TH2: Lật thẻ vị trí L: So sánh số thấy vị trí L bằng với kết quả cần tìm. Kết quả tìm thấy số 10 trong dãy ở vị trí L và kết thúc quá trình tìm kiếm.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Lựa chọn phương án đúng.
Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện:
A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
C. Sắp xếp dãy số theo thứ tự tăng dần.
D. So sánh số cần tìm với số ở giữa dãy số.
Lựa chọn phương án đúng.
Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, ta thực hiện:
A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
C. Sắp xếp dãy số theo thứ tự tăng dần.
D. So sánh số cần tìm với số ở giữa dãy số.
Xem đáp án »
11/07/2024
2,617
Câu 2:
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?
Xem đáp án »
30/05/2022
1,432
Câu 3:
Các số ghi trên mỗi thẻ ở Hình 1 lần lượt là: 26, 14, 24, 18, 15, 21, 19, 25, 12. Em hãy tạo Bảng 1 và điền thông tin của mỗi lần lặp để tìm số 21 trong dãy theo thuật toán tìm kiếm tuần tự.
Các số ghi trên mỗi thẻ ở Hình 1 lần lượt là: 26, 14, 24, 18, 15, 21, 19, 25, 12. Em hãy tạo Bảng 1 và điền thông tin của mỗi lần lặp để tìm số 21 trong dãy theo thuật toán tìm kiếm tuần tự.
Xem đáp án »
11/07/2024
866
Câu 4:
Hãy sử dụng thuật toán tìm kiếm tuần tự để tìm trong lớp em có bạn cùng tháng sinh với em hay không. Có thể sử dụng danh sách lớp có ghi thông tin ngày sinh hoặc hỏi trực tiếp. Lập Bảng 2 vào vở và ghi kết quả thực hiện (dòng 1 là ví dụ minh hoạ).
Hãy sử dụng thuật toán tìm kiếm tuần tự để tìm trong lớp em có bạn cùng tháng sinh với em hay không. Có thể sử dụng danh sách lớp có ghi thông tin ngày sinh hoặc hỏi trực tiếp. Lập Bảng 2 vào vở và ghi kết quả thực hiện (dòng 1 là ví dụ minh hoạ).
Xem đáp án »
30/05/2022
626
Câu 5:
Hãy vận dụng thuật toán tìm kiếm nhị phân để xác định một bạn trong lớp được sinh vào ngày nào trong tháng với không quá 5 câu hỏi trắc nghiệm Đúng/Sai. Tương tự, để xác định một bạn được sinh vào tháng nào trong năm thì em cần dùng nhiều nhất bao nhiêu câu hỏi Đúng/Sai?
Hãy vận dụng thuật toán tìm kiếm nhị phân để xác định một bạn trong lớp được sinh vào ngày nào trong tháng với không quá 5 câu hỏi trắc nghiệm Đúng/Sai. Tương tự, để xác định một bạn được sinh vào tháng nào trong năm thì em cần dùng nhiều nhất bao nhiêu câu hỏi Đúng/Sai?
Xem đáp án »
11/07/2024
554
Câu 6:
Em tìm một từ tiếng Anh trong cuốn từ điển theo cách nào? Tại sao em dùng cách đó?
Em tìm một từ tiếng Anh trong cuốn từ điển theo cách nào? Tại sao em dùng cách đó?
Xem đáp án »
11/07/2024
445
về câu hỏi!