Câu hỏi:
11/05/2023 309
Xây dựng thuật toán cho bài toán sau: Cho trước dãy các số đã được sắp xếp tăng dần. Với giá trị K cho trước cần tìm phần tử của dãy gốc có giá trị gần với K nhất.
Xây dựng thuật toán cho bài toán sau: Cho trước dãy các số đã được sắp xếp tăng dần. Với giá trị K cho trước cần tìm phần tử của dãy gốc có giá trị gần với K nhất.
Quảng cáo
Trả lời:
Giải bởi Vietjack
- Để tìm ra các phần tử của dãy gần K nhất chúng ta cần thêm các tính toán phụ tại dòng 10
- Chương trình trên hoàn toàn tương tự thuật toán tìm kiếm tuần tự, chỉ có một vòng lặp tại dòng 9, do đó có thời gian chạy O(n).
- Chúng ta thiết kế thuật toán thứ hai dựa trên tìm kiếm nhị phân. Hàm đệ quy chính sẽ được thiết kế theo dạng valueClosest(A, left, right, K) sẽ tìm phần tử gần K nhất trong khoảng chỉ số từ left đến right. Trước tiên có một số nhận xét cho các trường hợp đặc biệt.
+ Nếu n = 1, dãy A chỉ có một phần tử, khi đó hàm sẽ trả lại phần tử duy nhất của A.
+ Nếu n = 2, dãy A có hai phần tử thì cần so sánh phần tử nào gần K hơn chính
là phần tử cần tìm.
Chương trình cuối cùng có dạng như sau
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
Sách thầy cô Vietjack biên soạn:
Trọng tâm Hóa học 11 dùng cho cả 3 bộ sách Kết nối, Cánh diều, Chân trời sáng tạo VietJack - Sách 2025
Đã bán 244
₫ 136.000
₫ 58.000
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
Đã bán 211
₫ 119.000
₫ 45.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
Đã bán 1k
₫ 104.000
₫ 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
Đã bán 218
₫ 130.000
₫ 75.000
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 2:
Mô tả các bước tính bằng tay phép tính luỹ thừa 
theo hai chương trình trên. Cách nào nhanh hơn?
Mô tả các bước tính bằng tay phép tính luỹ thừa theo hai chương trình trên. Cách nào nhanh hơn?
Xem đáp án »
12/07/2024
470
Câu 3:
Tìm cách thiết lập thuật toán tính theo phương pháp chia để trị nhưng không sử dụng đệ quy.
Tìm cách thiết lập thuật toán tính theo phương pháp chia để trị nhưng không sử dụng đệ quy.
Xem đáp án »
11/05/2023
397
Câu 4:
Viết chương trình đo thời gian thực chạy để so sánh hai phương án của bài toán.
Viết chương trình đo thời gian thực chạy để so sánh hai phương án của bài toán.
Xem đáp án »
12/07/2024
383
Câu 5:
Hãy thiết lập thuật toán và chương trình tính luỹ thừa với a là số bất kì khác 0, n là số nguyên không âm.
Hãy thiết lập thuật toán và chương trình tính luỹ thừa với a là số bất kì khác 0, n là số nguyên không âm.
Xem đáp án »
11/05/2023
283
Câu 6:
Viết chương trình không đệ quy cho bài toán tìm kiếm nhị phần mở rộng trên.
Viết chương trình không đệ quy cho bài toán tìm kiếm nhị phần mở rộng trên.
Xem đáp án »
12/07/2024
276
🔥 Đề thi HOT:
-
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 Kết nối tri thức Bài 26 có đáp án
-
Bộ 4 đề thi giữa 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 Kết nối tri thức Bài 25 có đáp án
-
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 27 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
-
Bộ 4 đề thi cuối học kì 2 Tin 11 Kết nối tri thức có đáp án (Đề 3)
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận