Câu hỏi:
11/05/2023 234
Tìm chính xác số phép toán đơn cần thực hiện trong thuật toán tìm kiếm nhị phân nếu dãy gốc chỉ có 1 phần tử.
Tìm chính xác số phép toán đơn cần thực hiện trong thuật toán tìm kiếm nhị phân nếu dãy gốc chỉ có 1 phần tử.
Quảng cáo
Trả lời:
Giải bởi Vietjack
Nếu n = 1, tức là left = right. Nếu A[left] = K thì sẽ thực hiện ngay các lệnh tại dòng 5 và dừng chương trình. Nếu A[left] ≠ K thì sẽ gọi tiếp đệ quy tới các dòng 7 hoặc 9 nhưng sẽ trả về ngay –1. Vậy trong mọi trường hợp tổng số phép toán thực hiện khi n = 1 chỉ là hằng số, ta có T(1) = O(1).
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:
- Sách - Sổ tay kiến thức trọng tâm Vật lí 11 VietJack - Sách 2025 theo chương trình mới cho 2k8 ( 45.000₫ )
- Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025 ( 38.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Khi left = right, nghĩa là chỉ còn một phần tử để xét. Ta so sánh giá trị của phần tử đó với giá trị cần tìm x.
Nếu phần tử đó bằng x thì ta trả về vị trí của phần tử đó (left hoặc right).
Nếu phần tử đó khác x thì ta trả về giá trị -1 để thể hiện không tìm thấy phần tử x trong dãy.
Lời giải
Thuật toán tìm số nguyên lớn nhất không vượt quá căn bậc hai của n có thể được thiết kế bằng kĩ thuật chia để trị theo các bước sau:
1. Nếu n bằng 0 hoặc 1, trả về n.
2. Đặt a bằng căn bậc hai của n.
3. Nếu a bằng n, trả về a.
4. Ngược lại, tìm số nguyên lớn nhất không vượt quá căn bậc hai của n/2 và số nguyên lớn nhất không vượt quá căn bậc hai của n - 1. So sánh hai số này và trả về số lớn 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.
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.
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:
-
Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 2)
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 26 có đáp án
-
Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 1)
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 1: Một số thao tác chỉnh sửa ảnh và hỗ trợ chỉnh sửa ảnh có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 28 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 27 có đáp án
-
15 câu Trắc nghiệm Tin học 11 Cánh diều Bài 2: Tẩy xóa ảnh có đáp án
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận