bulgakov

35. Сумма и другие вычисления по массиву

Почти любая задача на массив — это цикл по индексам и небольшая переменная рядом. В ней накапливается сумма, счётчик или лучшее значение. Здесь разберём самый простой случай — сумму — и по тому же образцу решим шесть задач. Приём накопления вам знаком по циклам с накопителями и поиску максимума.

Что пригодится из прошлого: массивы, накопители, поиск максимума, ввод scanf. Если эти темы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Ввод массива с клавиатуры

Чтобы прочитать элементы, вызываем scanf для каждого. Нужен адрес элемента: &arr[i]. Запись arr[i] — значение, а &arr[i] — место, куда scanf положит прочитанное. Подробно, почему scanf требует &, мы разберём в главе про указатели в функциях.

Сумма элементов

Прочитаем пять чисел и сложим их. Полная программа:

C
#include <stdio.h>

int main(void)
{
    int arr[5];
    for (int i = 0; i < 5; i++) {
        if (scanf("%d", &arr[i]) != 1) {
            printf("Input error\n");
            return 1;
        }
    }

    int sumOfArray = 0;
    for (int i = 0; i < 5; i++) {
        sumOfArray += arr[i];
    }
    printf("%d\n", sumOfArray);
    return 0;
}

Ввод:

4 8 15 16 23

Вывод:

66

Программа состоит из трёх частей. Первый цикл вводит элементы: на шаге i читается число и записывается в arr[i]. Затем создаётся накопитель sumOfArray, который перед суммированием обязательно обнуляется. Второй цикл на каждом шаге прибавляет очередной элемент: sumOfArray += arr[i];.

Посмотрим, как растёт накопитель при вводе 4 8 15 16 23:

Шаг i Прибавляем arr[i] sumOfArray после шага
до цикла — 0
0 4 0 + 4 = 4
1 8 4 + 8 = 12
2 15 12 + 15 = 27
3 16 27 + 16 = 43
4 23 43 + 23 = 66

Те же шаги в картинках. Стрелка ▼ показывает текущий элемент arr[i], а под рядом записан накопитель:

i = 0
        ▼
      ┌────┬────┬────┬────┬────┐
arr:  │ 4  │ 8  │ 15 │ 16 │ 23 │
      └────┴────┴────┴────┴────┘
sumOfArray = 4   (4)

i = 1
             ▼
      ┌────┬────┬────┬────┬────┐
arr:  │ 4  │ 8  │ 15 │ 16 │ 23 │
      └────┴────┴────┴────┴────┘
sumOfArray = 12   (4 + 8)

... (шаги i = 2 и i = 3 такие же)

i = 4
                            ▼
      ┌────┬────┬────┬────┬────┐
arr:  │ 4  │ 8  │ 15 │ 16 │ 23 │
      └────┴────┴────┴────┴────┘
sumOfArray = 66   (4 + 8 + 15 + 16 + 23)

После шага i в накопителе лежит сумма элементов с 0 по i.

Следите за числом в условии. У нас в массиве 5 элементов, поэтому условие цикла i < 5. Если написать имя, которого в программе нет (например i < n без объявления n), программа не скомпилируется. Если написать число больше 5, цикл прочитает память за массивом (см. урок про массивы).

Шесть задач на обход

Ниже шесть задач. Каждая решается тем же циклом for (int i = 0; i < n; i++), где n — число элементов массива, различается только действие внутри. Попробуйте решить сами, затем откройте решение. Чтобы программы были короткими и повторяемыми, массивы в решениях заданы сразу в коде; ввод с клавиатуры делается как выше.

Задача 1. Вычислить сумму элементов массива. Её решение — программа с суммой выше: накопитель стартует с 0, в цикле sumOfArray += arr[i].

Задача 2. Вычислить произведение элементов массива.

Произведение: накопитель начинается с единицы
C
#include <stdio.h>

int main(void)
{
    int arr[5] = {2, 3, 4, 5, 1};
    int product = 1;

    for (int i = 0; i < 5; i++) {
        product *= arr[i];
    }
    printf("%d\n", product);
    return 0;
}

Вывод: 120, потому что 2 · 3 · 4 · 5 · 1 = 120.

Накопитель произведения начинают с 1, а не с 0: единица — нейтральный элемент умножения. Если начать с нуля, любое произведение останется нулём. Для суммы нейтральный элемент — ноль.

У произведения есть опасность: оно растёт быстро. Десять чисел порядка 100 дадут 10^20, что не помещается в int. Такое переполнение мы разбирали в уроке про преобразования. Для больших данных нужен более широкий тип.

Задача 3. Вычислить количество положительных элементов массива.

Счётчик с условием
C
#include <stdio.h>

int main(void)
{
    int arr[8] = {3, -2, 7, 0, 5, -1, 4, -8};
    int count = 0;

    for (int i = 0; i < 8; i++) {
        if (arr[i] > 0) {
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

Вывод: 4. Положительные числа в массиве 3, -2, 7, 0, 5, -1, 4, -8 — это 3, 7, 5, 4.

Счётчик count увеличивается только при выполнении условия arr[i] > 0. Ноль не положителен, поэтому 0 не засчитан. Отличие от суммы: count++ прибавляет единицу, а не значение элемента.

Задача 4. Вычислить количество элементов массива, значение которых больше значения последнего элемента.

Сравнение с последним элементом
C
#include <stdio.h>

int main(void)
{
    int arr[6] = {5, 1, 9, 3, 7, 5};
    int last = arr[5];
    int count = 0;

    for (int i = 0; i < 6; i++) {
        if (arr[i] > last) {
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}

Вывод: 2. Последний элемент массива 5, 1, 9, 3, 7, 5 равен 5. Строго больше пяти только 9 и 7.

Значение последнего элемента запоминаем до цикла в переменную last. Индекс последнего элемента — 5, то есть число элементов минус один. Сам последний элемент пятёрку не превосходит, и первая пятёрка тоже: условие строгое, >.

Задача 5. Вычислить самый большой элемент массива.

Максимум: начинаем с первого элемента
C
#include <stdio.h>

int main(void)
{
    int arr[6] = {-7, -3, -9, -3, -12, -5};
    int max = arr[0];

    for (int i = 1; i < 6; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    printf("%d\n", max);
    return 0;
}

Вывод: -3. Все числа массива -7, -3, -9, -3, -12, -5 отрицательны.

Переменную max нельзя начинать с 0: в этом массиве нет положительных, и ответ 0 был бы неверным, потому что такого элемента в массиве нет. Правильное начальное значение — первый элемент. Цикл начинается с i = 1, потому что arr[0] уже взят. На каждом шаге, если встретился элемент больше текущего максимума, он становится новым максимумом.

Задача 6. Вычислить второй по величине элемент массива.

Условие допускает два толкования. Если в массиве есть повторы, «второй по величине» может означать второе по величине различное значение или элемент на втором месте после сортировки по убыванию. Для массива 4, 9, 2, 9, 7, 1 первое толкование даёт 7, второе — 9. Выберем первое: второе по величине среди различных значений. Это стоит оговорить заранее, а в вашей задаче уточнить у преподавателя.

Второй по величине: два прохода
C
#include <stdio.h>

int main(void)
{
    int arr[6] = {4, 9, 2, 9, 7, 1};

    int max = arr[0];
    for (int i = 1; i < 6; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    int found = 0;
    int second = 0;
    for (int i = 0; i < 6; i++) {
        if (arr[i] < max && (!found || arr[i] > second)) {
            second = arr[i];
            found = 1;
        }
    }

    if (found) {
        printf("%d\n", second);
    } else {
        printf("No second value\n");
    }
    return 0;
}

Вывод: 7.

Первым проходом находим максимум: 9. Вторым проходом ищем наибольший из элементов, которые строго меньше максимума. Обе девятки в расчёт не идут. Флаг found отмечает, что кандидат уже есть. Вот как меняются значения на втором проходе:

i   arr[i]   меньше 9?   found   second
0     4        да          1       4
1     9        нет         1       4
2     2        да          1       4
3     9        нет         1       4
4     7        да          1       7
5     1        да          1       7

Условие arr[i] < max && (!found || arr[i] > second) собрано из знакомых операций (составные условия): ! — «не», && — «и», || — «или». Читается так: «элемент меньше максимума, и (кандидата ещё нет — то есть found равно нулю — или этот элемент лучше кандидата)». Это нужно, потому что начальное значение second может быть любым числом, а искать надо среди элементов. Если все элементы равны, строго меньших максимума нет, и программа сообщит No second value.

Что запомнить

  • Обход массива — цикл for (int i = 0; i < n; i++).
  • Накопитель задаётся до цикла. Нейтральное начальное значение: 0 для суммы, 1 для произведения.
  • Для максимума стартовое значение — первый элемент, а не ноль.
  • Условие задачи нужно читать внимательно: «больше» и «не меньше», «различные» и «любые» — разные задачи.
ПрактикаЗагружаем тест…