Trung bình của phạm vi trong mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng gồm n số nguyên và một số truy vấn m. Nhiệm vụ của chúng tôi là tạo một chương trình tính toán giá trị tích phân (làm tròn xuống) của giá trị trung bình của các phạm vi được cung cấp bởi các truy vấn.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào -

array = {5, 7, 8, 9, 10}
m = 2; [0, 3], [2, 4]

Đầu ra -

7
9

Để giải quyết vấn đề này, chúng tôi có hai phương pháp, một là trực tiếp và phương pháp kia là sử dụng tiền tố sum.

Trong cách tiếp cận trực tiếp, đối với mỗi truy vấn, chúng ta sẽ lặp lại từ chỉ mục đầu đến chỉ mục cuối của phạm vi. Và cộng tất cả các số nguyên của mảng và chia cho số lượng. Cách tiếp cận này hoạt động tốt và in ra kết quả nhưng không phải là cách hiệu quả.

Sử dụng prefixSum

Trong cách tiếp cận này, chúng ta sẽ tính toán mảng tổng tiền tố sẽ lưu trữ tổng của tất cả các phần tử của mảng cho đến chỉ mục thứ i, tức là prefixSum (4) là tổng của tất cả các phần tử cho đến chỉ mục 4.

Bây giờ, bằng cách sử dụng mảng prefixSum này, chúng tôi sẽ tính giá trị trung bình cho mỗi truy vấn bằng công thức,

Mean = prefixSum[upper] - prefixSum(lower-1) / upper-lower+1

Trên và dưới là các chỉ mục được đưa ra trong truy vấn. Nếu thấp hơn =0, prefixSum (low-1) =0.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#include <iostream>
#define MAX 100
using namespace std;
int prefixSum[MAX];
void initialisePrefixSum(int arr[], int n) {
   prefixSum[0] = arr[0];
   for (int i = 1; i < n; i++)
   prefixSum[i] = prefixSum[i - 1] + arr[i];
}
int queryMean(int l, int r) {
   int mean;
   if (l == 0)
      mean =(prefixSum[r]/(r+1));
   else
      mean =((prefixSum[r] - prefixSum[l - 1]) / (r - l + 1));
      return mean;
}
int main() {
   int arr[] = {5, 7, 8, 9, 10 };
   int n = sizeof(arr) / sizeof(arr[0]);
   initialisePrefixSum(arr, n);
   cout<<"Mean in 1st query: "<<queryMean(1, 4)<<endl;
   cout<<"Mean in 2st query: "<<queryMean(2, 4)<<endl;
   return 0;
}

Đầu ra

Mean in 1st query: 8
Mean in 2st query: 9