Cho trước dãy số A đã sắp xếp theo thứ tự tăng dần, cho trước hằng số C

Giải Chuyên đề Tin 11 Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị - Kết nối tri thức

Vận dụng 3 trang 39 Chuyên đề Tin học 11: Cho trước dãy số A đã sắp xếp theo thứ tự tăng dần, cho trước hằng số C. Cần thiết lập hai hàm sau bằng kĩ thuật chia để trị:

– Hàm firstInd(A, left, right, C) sẽ tìm chỉ số của phần tử đầu tiên của dãy A có giá

trị bằng C. Nếu không sẽ trả về -1.

– Hàm lastInd(A, left, right, C) sẽ tìm chỉ số của phần tử cuối cùng của dãy A có giá trị bằng C. Nếu không thấy sẽ trả về – 1.

Từ hai hàm đã thiết kế trên, đưa ra một cách giải khác cho bài toán trong nhiệm vụ 1. Lời giải này có độ phức tạp O(logn).

Lời giải:

Để thiết lập hai hàm firstInd và lastInd bằng kĩ thuật chia để trị, ta có thể áp dụng phương pháp tương tự như khi tìm kiếm số lần xuất hiện của một phần tử trong dãy số bằng kĩ thuật chia để trị. Cụ thể, ta sẽ chia dãy số thành hai nửa và tìm kiếm đệ quy trên từng nửa đó.

Ví dụ:

Kết quả trả về:

- Ta có thể sử dụng hàm firstInd và lastInd đã thiết kế để giải quyết bài toán tìm số lần xuất hiện của một số trong một dãy số.

Giả sử ta cần tìm số lần xuất hiện của số C trong dãy A đã sắp xếp tăng dần. Đầu tiên, ta sử dụng hàm firstInd để tìm chỉ số của phần tử đầu tiên có giá trị bằng C, sau đó sử dụng hàm lastInd để tìm chỉ số của phần tử cuối cùng có giá trị bằng C. Nếu cả hai hàm đều trả về giá trị khác -1, số lần xuất hiện của C trong dãy A sẽ là hiệu của chỉ số của phần tử cuối cùng và phần tử đầu tiên cộng thêm 1.

Vì mỗi lần gọi hàm firstInd và lastInd đều có độ phức tạp O(logn), nên độ phức tạp của giải pháp này sẽ là O(logn).

Lời giải bài tập Chuyên đề Tin 11 Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị hay, chi tiết khác:

• Khởi động trang 37 Chuyên đề Tin học 11: Cho một dãy số A bất kì. Để xác định một số C ....

• Luyện tập trang 39 Chuyên đề Tin học 11: Chỉnh sửa nâng cấp chương trình của nhiệm vụ thực hành để đưa ra kết quả ....

• Vận dụng 1 trang 39 Chuyên đề Tin học 11: Cho một dãy số bất kì (chưa được sắp xếp) và một số K ....

• Vận dụng 2 trang 39 Chuyên đề Tin học 11: Cho một dãy số nguyên được sắp xếp theo thứ tự tăng dần ....

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

• Chuyên đề Tin học 11 Bài 13: Kĩ thuật duyệt quay lui

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

---