Меньше среднего. C++

Дан массив A из N элементов. Требуется найти и вывести количество элементов,
значение которых меньше среднего арифметического значения элементов массива.
Input
Со стандартного устройства ввода в первой строке вводится целое число
N (1 <= N <=1000) — количество элементов массива. Во второй строке через пробел
вводятся N целых чисел - элементы массива A (-1000 <= A i <= 1000).
Output
Требуется вывести целое число - количество искомых элементов. Выводить в конце
строки пробел не нужно.
Sample Input
5
2 4 6 10 8
Sample Output
2
Примечание
Среднее арифметическое значение элементов массива =
(Сумма значений всех элементов массива) / (Количество элементов в массиве).
В примере среднее арифметическое значение = (2 + 4 + 6 + 10 + 8) / 5 = 6.

Решение задачи «Меньше среднего» на C++

Условие: Дан массив A из N элементов. Необходимо найти и вывести количество элементов массива, значения которых меньше среднего арифметического всех элементов массива.

Решение на C++

#include 
#include 
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long double> a(n);
    long double sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    long double avg = sum / n;
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] < avg) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Объяснение решения

Для решения задачи необходимо выполнить несколько действий:

1. Считать количество элементов N. Сначала вводим число n, которое определяет размер массива.

2. Заполнить массив и найти сумму элементов. В цикле считываем элементы массива и одновременно добавляем каждый элемент к переменной sum.

3. Вычислить среднее арифметическое. Для этого сумму всех элементов делим на их количество:

   \[ avg = \frac{a_1+a_2+\ldots+a_n}{n} \]

4. Подсчитать количество элементов меньше среднего. Проходим по массиву ещё раз. Если текущий элемент меньше avg, увеличиваем счётчик count на единицу.

5. Вывести результат. После завершения цикла выводим значение count.

Пример работы программы

Входные данные:

Среднее арифметическое:

Сравниваем элементы со средним значением:

• 2 < 6 — подходит.

• 4 < 6 — подходит.

• 6 = 6 — не подходит.

• 8 > 6 — не подходит.

• 10 > 6 — не подходит.

Таким образом, всего 2 элемента меньше среднего арифметического.

Выходные данные:

Сложность алгоритма

Временная сложность — O(N).

Программа дважды проходит по массиву: первый раз для нахождения суммы, второй — для подсчёта подходящих элементов. Поэтому время работы линейно зависит от количества элементов.

Пространственная сложность — O(N).

Для хранения массива используется дополнительная память, пропорциональная количеству элементов.

Важные моменты

• Используется тип long double, чтобы корректно работать как с целыми, так и с дробными числами и уменьшить погрешность вычисления среднего.

• Условие a[i] < avg использует строгое сравнение. Если элемент равен среднему арифметическому, он не учитывается.

• Если массив состоит из одного элемента (N = 1), программа выведет 0, поскольку единственный элемент равен среднему арифметическому.

Итог: задача решается с помощью двух циклов: в первом вычисляем сумму и среднее арифметическое, во втором подсчитываем количество элементов, которые строго меньше полученного среднего.