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

Giải Chuyên đề Tin 11 Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị - Kết nối tri thức

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:

Lời giải bài tập Chuyên đề Tin 11 Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị hay, chi tiết khác:

• Khởi động trang 33 Chuyên đề Tin học 11: Trong bài học này em sẽ thiết kế lời giải cho hai bài toán ....

• Hoạt động 1 trang 33 Chuyên đề Tin học 11: Hãy thiết lập thuật toán và chương trình tính luỹ thừa ....

• Câu hỏi 1 trang 34 Chuyên đề Tin học 11: Mô tả các bước tính bằng tay phép tính luỹ thừa ....

• 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? ....

• Câu hỏi 1 trang 36 Chuyên đề Tin học 11: Hãy giải thích kĩ hơn chương trình 2 ....

• Câu hỏi 2 trang 36 Chuyên đề Tin học 11: Nêu những điểm khác biệt của chương trình trên ....

• Luyện tập 1 trang 36 Chuyên đề Tin học 11: Viết chương trình không đệ quy cho bài toán ....

• Luyện tập 1 trang 36 Chuyên đề Tin học 11: Viết chương trình đo thời gian thực chạy để ....

• Vận dụng 1 trang 36 Chuyên đề Tin học 11: Tìm cách thiết lập thuật toán tính ....

• 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 ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 11 Kết nối tri thức hay, chi tiết khác:

• Chuyên đề Tin học 11 Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 9: Sắp xếp trộn

• Chuyên đề Tin học 11 Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 11: Bài toán tìm kiếm theo kĩ thuật duyệt

• Chuyên đề Tin học 11 Bài 12: Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

Xem thêm các tài liệu học tốt lớp 11 hay khác:

• Giải Chuyên đề Tin học 11 Kết nối tri thức
• Giải Chuyên đề Tin học 11 Chân trời sáng tạo
• Giải Chuyên đề Tin học 11 Cánh diều
• Giải lớp 11 Kết nối tri thức (các môn học)
• Giải lớp 11 Chân trời sáng tạo (các môn học)
• Giải lớp 11 Cánh diều (các môn học)

Săn SALE shopee Tết:

• Mỹ phẩm SACE LADY giảm tới 200k
• SRM Simple tặng tẩy trang 50k
• Combo Dầu Gội, Dầu Xả TRESEMME 80k

---