Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n và một số nguyên m. Nhiệm vụ của chúng ta là Tìm giá trị trung bình của các phương tiện của mảng con trong một mảng nhất định.
Mô tả mã - Ở đây, chúng ta cần tìm giá trị trung bình của mảng là giá trị trung bình của mảng con có kích thước m.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {2, 5, 3, 6, 1}, m = 3 Đầu ra
3.78
Giải thích
All subarrays of size m are {2, 5, 3}, {5, 3, 6}, {3, 6, 1}
Means of means of subarray of size m, $$ (\ left (\ frac {2 + 5 + 3} {3} \ right) + \ left (\ frac {5 + 3 + 6} {3} \ right) + \ left (\ frac {3 + 6 +1} {3} \ right)) / 3 =\ left (\ frac {10} {3} \ right) + \ left (\ frac {14} {3} \ right) + \ left (\ frac {10 } {3} \ right) /3=34/3/3=3.78$$
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm tất cả các mảng con có kích thước m và tìm phương tiện của chúng. Sau đó, cộng tất cả các phương tiện này và chia nó cho số lượng các phân nhóm con. Và trả về kết quả.
Một cách tiếp cận khác hiệu quả hơn là sử dụng thuật toán cửa sổ trượt, chúng ta sẽ tìm một kết quả có kích thước m bắt đầu từ chỉ số 0. Đối với mỗi cửa sổ, hãy tìm trung bình và tổng. Và ở cuối chia tổng cho số cửa sổ và trả lại giá trị.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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 = 0; 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<<"The mean of subarray means is "<<calcMeanOfSubarrayMeans(arr, n, m);
return 0;
} Đầu ra
The mean of subarray means is 8.06667