Алгоритм поиска наибольшего значения
💻 Информатика · 6 класс
Задача поиска наибольшего значения
Часто нужно найти самое большое число в наборе данных: наибольшую оценку, самый высокий рост, максимальную температуру за неделю. Для этого составляют алгоритм поиска наибольшего значения. Это последовательность шагов, которая гарантированно находит максимум, просматривая все числа по одному. Человек может просто «увидеть» наибольшее число, но исполнителю нужно описать чёткий порядок действий.
Идея алгоритма
Заведём переменную, в которой будем хранить наибольшее из уже просмотренных чисел. Сначала запишем в неё первое число набора. Затем сравним с ней каждое следующее число: если оно больше, обновим значение переменной. После просмотра всех чисел в переменной останется максимум всего набора.
- взять первое число как текущий максимум;
- сравнить с текущим максимумом очередное число;
- если оно больше — запомнить его как новый максимум;
- если не больше — оставить максимум прежним;
- повторять, пока не закончатся числа.
Трассировка примера
Найдём максимум в наборе 3, 7, 2, 9, 5. Будем по шагам заполнять таблицу: в столбце «макс» записываем текущий наибольший после каждого сравнения.
| Шаг | Число | Больше макс? | Макс |
|---|---|---|---|
| 1 | 3 | начало | 3 |
| 2 | 7 | да | 7 |
| 3 | 2 | нет | 7 |
| 4 | 9 | да | 9 |
| 5 | 5 | нет | 9 |
После просмотра всех чисел переменная «макс» равна 9 — это и есть ответ. Такую пошаговую проверку алгоритма называют трассировкой.
макс := первое число
для каждого следующего: если число > макс, то макс := числоПохожие задачи
Точно так же строят алгоритм поиска наименьшего числа: достаточно заменить условие «больше» на «меньше». А если в условии запоминать ещё и номер числа, то алгоритм найдёт не только сам максимум, но и его место в наборе. Этот же приём применяют, чтобы найти самого высокого ученика, самый тёплый день или самую дорогую покупку.
Заметим, что алгоритм просматривает каждое число ровно один раз. Поэтому он работает быстро даже для длинного набора: чтобы найти максимум среди ста чисел, достаточно ста сравнений. Не нужно сравнивать каждое число с каждым — хватает одного прохода по списку.
Запись для исполнителя
Чтобы алгоритм выполнил компьютер, его записывают в виде чётких команд: завести переменную, присвоить ей первое число, в цикле сравнивать и обновлять. Здесь работают сразу несколько знакомых приёмов — переменная для хранения результата, цикл для повторения и ветвление для сравнения. Поэтому поиск наибольшего значения часто разбирают как пример, в котором соединяются основные конструкции алгоритма.
Частая ошибка: начинать поиск с нуля вместо первого числа набора. Если все числа отрицательные, ноль окажется больше любого из них, и алгоритм даст неверный ответ. Поэтому за начальный максимум берут именно первый элемент набора.
Кратко о главном
- Алгоритм находит наибольшее число, просматривая все элементы по одному.
- За начальный максимум берут первый элемент набора.
- Каждое следующее число сравнивают с текущим максимумом и при необходимости обновляют его.
- После просмотра всех чисел в переменной остаётся ответ.