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ải Hoạt động 2 trang 34 Chuyên đề Tin học 11 Kết nối tri thức chi tiết trong Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Chuyên đề Tin học 11. Mời các bạn đón xem:

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

Hoạt động 2 trang 34 Chuyên đề Tin học 11: 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

Lời giả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

- 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