Câu hỏi:
30/09/2022 2,154
Bạn em có một bộ 20 thẻ số, mỗi thẻ ghi một số khác nhau, được đặt úp trên bàn theo thứ tự giá trị các số tăng dần từ trái sang phải. Bạn đố em lật tìm được đúng một số trong 20 thẻ số đó chỉ với tối đa 5 lần lật. Em có thực hiện được không? Vì sao?
Quảng cáo
Trả lời:
Giải bởi Vietjack
Trả lời:
Thực hiện được, vì: Áp dụng thuật toán tìm kiếm nhị phân.
Theo công thức phần nguyên, ta xác định và lật thẻ ở giữa như sau (giả định trường hợp xấu nhất là lần lật cuối cùng mới đúng số cần tìm):
- Lần 1: lật 1 thẻ trong 20 thẻ, ta lật thẻ thứ 10.
- Lần 2: lật 1 thẻ trong 9 thẻ bên trái hoặc trong 10 thẻ bên phải thẻ thứ 10, ta lật thẻ thứ 5 hoặc lật thẻ thứ 15.
Cứ tiếp tục chọn và lật như vậy thì đến lần 5, sẽ chỉ còn 1 số để lật và chắc chắn tìm được một số theo yêu cầu.
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
Sách thầy cô Vietjack biên soạn:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Trả lời:
Sử dụng thuật toán tìm kiếm nhị phân là phù hợp nhất để tìm một số trong dãy số này vì đây là dãy số sắp xếp tăng dần, số lần lặp phải thực hiện ít hơn hẳn khi sử dụng thuật toán tìm kiếm tuần tự (ta sẽ thấy rõ khi dãy có nhiều phần tử và phần tử này cần tìm cách xa phần tử đầu tiên).
|
Lần lặp |
Số của dãy được kiểm tra |
Đúng số cần tìm |
Đã kiểm tra hết số |
|
1 |
25 |
Sai |
Sai |
|
2 |
52 |
Sai |
Sai |
|
3 |
30 |
Đúng |
|
Lời giải
Trả lời:
Đáp án đúng là: A
Số 36 đầu tiền nằm ở vị trí thứ 3 trong dãy nên khi tìm số 36 trong dãy số này bằng thuật toán tìm kiếm tuần tự, ta cần thực hiện 3 lần lặp.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
Đề kiểm tra học kì 2 Tin học 7 Kết nối tri thức có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 10 có đáp án
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 9 có đáp án
-
Đề kiểm tra học kì 2 Tin học 7 Cánh diều có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 14 có đáp án
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 15 có đáp án
-
Đề kiểm tra giữa học kì 2 Tin học 7 Kết nối tri thức có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 11 có đáp án