Алгоритмы для массивов: максимум, подсчет, поиск, среднее
Четыре классические задачи с массивами
- Большинство работы с массивами сводится к одному из четырех сканирований: найти максимум, подсчитать совпадения, найти значение или вычислить среднее.
- Каждое из них — это одиночный
forцикл по массиву с переменной, запоминающей результат. - Как только вы освоите эти четыре подхода, большинство задач с массивами решаются небольшим изменением одного из них.
Поиск максимума
- Начните с предположения, что первый элемент самый большой:
int best = a[0];. - Затем посмотрите на остальные. Если элемент больше
best, он становится новымbest. - Это работает и для отрицательных чисел, потому что вы начинаете с реального элемента, а не с
0.
Подсчет с условием
- Счетчик начинается со
0и прибавляет1каждый раз, когда элемент проходит проверку. - Например, подсчет четных чисел с помощью проверки
a[i] % 2 == 0внутри цикла. - Конечное значение счетчика является вашим ответом.
Линейный поиск
- Для поиска пройдите массив и сравните каждый элемент с целевым.
- Верните индекс сразу после нахождения совпадения. Если цикл завершился без совпадений, верните
-1. -1— частый сигнал "не найдено", поскольку он никогда не бывает допустимым индексом.
Среднее без ошибок целочисленного деления
- Сложите все элементы в общую сумму типа
int, затем разделите наn. - Деление двух
intотбрасывает дробную часть, поэтому сделайте явное преобразование:(double)total / n. - Верните результат типа
double, чтобы вызывающий код получил точное среднее.
Распространенные ошибки
- Начните поиск максимума или минимума с первого элемента, затем сравнивайте остальные.
- Не выходите за пределы массива.
Теперь попробуйте сами
- Передавайте массив и его длину
n, и выбирайте правильную переменную-счетчик для каждой задачи. - Не пишите
main— проверяющая система предоставит его.
Сканирование массива
Один проход поддерживает накопительный результат (максимум, сумма, счетчик) по всему массиву.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Заполните int max(const int a[], int n) так, чтобы он возвращал наибольший элемент (предположите, что n >= 1). Начните с a[0], чтобы корректно работать с отрицательными числами. Не пишите main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Заполните int count_even(const int a[], int n) так, чтобы он возвращал количество четных элементов. Используйте % 2. Не пишите main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Заполните int index_of(const int a[], int n, int target) так, чтобы он возвращал индекс первого ⟨target⟩, или -1, если его нет. Не пишите ни main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Заполните double average(const int a[], int n) так, чтобы он возвращал среднее значение элементов (предположите, что n >= 1). Приведите тип для избежания целочисленного деления. Не пишите main.
Нажмите Запустить, чтобы увидеть результат здесь.