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
Lời giải Hoạt động 2 trang 34 Chuyên đề Tin học 11 sách Chuyên đề học tập Tin học lớp 11 Kết nối tri thức hay nhất, chi tiết sẽ giúp học sinh dễ dàng trả lời các câu hỏi & làm bài tập.
Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị
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.
- 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:
Xem thêm các bài giải Chuyên đề Tin học 11 sách Kết nối tri thức hay, chi tiết khác:
Câu hỏi 2 trang 34 Chuyên đề Tin học 11: Phép tính a^21 sẽ cần dùng bao nhiêu phép nhân?
Vận dụng 2 trang 36 Chuyên đề Tin học 11: Bài toán tìm vùng chỉ số của dãy đã sắp xếp
Xem thêm các bài giải Chuyên đề Tin học 11 sách Kết nối tri thức hay, chi tiết khác:
Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị
Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị
Xem thêm các chương trình khác:
- Soạn văn lớp 11 Kết nối tri thức - hay nhất
- Văn mẫu lớp 11 - Kết nối tri thức
- Tóm tắt tác phẩm Ngữ văn 11 – Kết nối tri thức
- Tác giả tác phẩm Ngữ văn 11 - Kết nối tri thức
- Giải SBT Ngữ văn 11 – Kết nối tri thức
- Bố cục tác phẩm Ngữ văn 11 – Kết nối tri thức
- Giải Chuyên đề học tập Ngữ văn 11 – Kết nối tri thức
- Nội dung chính tác phẩm Ngữ văn lớp 11 – Kết nối tri thức
- Soạn văn 11 Kết nối tri thức (ngắn nhất)
- Giải sgk Toán 11 – Kết nối tri thức
- Giải Chuyên đề học tập Toán 11 – Kết nối tri thức
- Lý thuyết Toán 11 - Kết nối tri thức
- Giải sbt Toán 11 – Kết nối tri thức
- Bài tập Tiếng Anh 11 Global success theo Unit có đáp án
- Giải sgk Tiếng Anh 11 – Global success
- Giải sbt Tiếng Anh 11 - Global Success
- Trọn bộ Từ vựng Tiếng Anh 11 Global success đầy đủ nhất
- Ngữ pháp Tiếng Anh 11 Global success
- Giải sgk Vật lí 11 – Kết nối tri thức
- Lý thuyết Vật lí 11 – Kết nối tri thức
- Giải sbt Vật lí 11 – Kết nối tri thức
- Giải Chuyên đề học tập Vật lí 11 – Kết nối tri thức
- Chuyên đề dạy thêm Vật lí 11 cả 3 sách (2024 có đáp án)
- Giải sgk Hóa học 11 – Kết nối tri thức
- Giải Chuyên đề học tập Hóa học 11 – Kết nối tri thức
- Lý thuyết Hóa 11 - Kết nối tri thức
- Giải sbt Hóa học 11 – Kết nối tri thức
- Chuyên đề dạy thêm Hóa 11 cả 3 sách (2024 có đáp án)
- Giải sgk Sinh học 11 – Kết nối tri thức
- Lý thuyết Sinh học 11 – Kết nối tri thức
- Giải Chuyên đề học tập Sinh học 11 – Kết nối tri thức
- Giải sbt Sinh học 11 – Kết nối tri thức
- Giải sgk Giáo dục Kinh tế và Pháp luật 11 – Kết nối tri thức
- Giải Chuyên đề học tập Kinh tế pháp luật 11 – Kết nối tri thức
- Lý thuyết Kinh tế pháp luật 11 – Kết nối tri thức
- Giải sbt Kinh tế pháp luật 11 – Kết nối tri thức
- Giải sgk Lịch sử 11 – Kết nối tri thức
- Giải Chuyên đề học tập Lịch sử 11 – Kết nối tri thức
- Lý thuyết Lịch sử 11 - Kết nối tri thức
- Giải sbt Lịch sử 11 – Kết nối tri thức
- Giải sgk Địa lí 11 – Kết nối tri thức
- Giải Chuyên đề học tập Địa lí 11 – Kết nối tri thức
- Lý thuyết Địa lí 11 - Kết nối tri thức
- Giải sbt Địa lí 11 – Kết nối tri thức
- Giải sgk Công nghệ 11 – Kết nối tri thức
- Lý thuyết Công nghệ 11 - Kết nối tri thức
- Giải sbt Công nghệ 11 – Kết nối tri thức
- Giải sgk Giáo dục quốc phòng an ninh 11 – Kết nối tri thức
- Lý thuyết Giáo dục quốc phòng 11 – Kết nối tri thức
- Giải sbt Giáo dục quốc phòng 11 – Kết nối tri thức
- Giải sgk Hoạt động trải nghiệm 11 – Kết nối tri thức