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

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.

Trả lời

- Để 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

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 (ảnh 1)

- 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

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 (ảnh 2)

Câu hỏi cùng chủ đề

Xem tất cả