Tìm trung bình của các trung bình con mảng trong C++

Mô tả vấn đề

Cho mảng arr[] kích thước n và số nguyên m. Nhiệm vụ là tìm trung bình của các trung bình của tất cả các con mảng (subarray) kích thước m.

Ví dụ minh họa

Đầu vào:

arr[] = {2, 5, 3, 6, 1}, m = 3

Đầu ra:

3.78

Giải thích:

Các con mảng kích thước 3:
{2,5,3} → mean = 10/3
{5,3,6} → mean = 14/3
{3,6,1} → mean = 10/3
Trung bình của các mean = (10/3 + 14/3 + 10/3) / 3 = 34/9 ≈ 3.78

Phương pháp giải quyết

Cách 1 (Đơn giản): Tìm tất cả con mảng kích thước m, tính mean từng cái, cộng dồn và chia cho số con mảng.

Cách 2 (Hiệu quả - Sliding Window): Tính tổng cửa sổ đầu tiên kích thước m. Sau đó trượt cửa sổ: trừ phần tử ra khỏi cửa sổ, thêm phần tử mới vào. Tính mean cho mỗi cửa sổ và cộng dồn. Cuối cùng chia tổng mean cho số cửa sổ (n - m + 1).

Chương trình minh họa

#include <iostream>
using namespace std;

float calcMeanOfSubarrayMeans(int arr[], int n, int m) {
    float meanSum = 0, windowSum = 0;
    for (int i = 0; i < m; i++)
        windowSum += arr[i];
    meanSum += (windowSum / m);
    for (int i = m; i < n; i++) {
        windowSum = windowSum - arr[i - m] + arr[i];
        meanSum += (windowSum / m);
    }
    int windowCount = n - m + 1;
    return (meanSum / windowCount);
}

int main() {
    int arr[] = {4, 1, 7, 9, 2, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 3;
    cout << "Trung bình của các trung bình con mảng là " << calcMeanOfSubarrayMeans(arr, n, m);
    return 0;
}

Kết quả đầu ra

Trung bình của các trung bình con mảng là 8.06667