Cho dãy số A, cần tìm phần tử mốt (mode) của A. Phần tử mốt là phần tử có số lần xuất hiện

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

Vận dụng 1 trang 47 Chuyên đề Tin học 11:Cho dãy số A, cần tìm phần tử mốt (mode) của A. Phần tử mốt là phần tử có số lần xuất hiện nhiều nhất trong A. Nếu tồn tại nhiều thì chỉ yêu cầu tìm ra một phần tử mốt. Yêu cầu sử dụng kĩ thuật chia để trị.

Lời giải:

Để tìm phần tử xuất hiện nhiều lần nhất trong dãy, ta có thể sử dụng phương pháp chia để trị (divide and conquer) bằng cách chia dãy thành hai phần và tìm phần tử xuất hiện nhiều lần nhất trong mỗi phần, sau đó so sánh và lấy phần tử xuất hiện nhiều lần nhất trong cả hai phần.

Ví dụ:

Kết quả: “Phần tử xuất hiện nhiều nhất là 5, số lần xuất hiện là 3”