Задачи на программирование · поиск максимума

Количество элементов, равных максимуму

Источник: informatics.msk.ru, задача №3072. Условие пересказано своими словами. На informatics.msk.ru это решение можно сдать в настоящую проверяющую систему — нужна регистрация.

Как проверяет автоматическая система

  • Ответ — сама программа. Система запускает её на многих тестах: часть видна в условии, остальные скрыты.
  • На каждом тесте программа должна напечатать ровно ответ — без слов вроде «Ответ:».
  • Есть ограничение по времени: слишком медленная или зависшая программа тест не проходит.
  • Здесь так же: кнопка проверяет на всех тестах и останавливается на первой ошибке.

Перед задачей

Коротко о том, что понадобится. Знаешь тему — сразу переходи к условию.

Учебный материал: Чтение чисел до нуля

Часто количество чисел заранее неизвестно, а конец ввода отмечен нулём. Тогда for не подходит — неизвестно, сколько раз повторять. Нужен while: «пока число не 0 — обрабатываем и читаем следующее».

x = int(input())  # читаем первое число до цикла
while x != 0:  # пока не встретили 0
    print(x * 2)  # что-то делаем с числом
    x = int(input())  # читаем следующее — в конце тела цикла

Главное — новое число читается в конце цикла. Тогда проверка x != 0 сразу срабатывает на нуле, и сам 0 не обрабатывается. Забыть строку чтения внутри цикла — программа зависнет.

Учебный материал: Поиск максимума

Чтобы найти самое большое число, держим «лучшее на сейчас» и сравниваем с ним каждое новое. Начальное значение берём меньше любого возможного числа — для натуральных подойдёт 0.

best = 0  # пока максимум — ноль
x = int(input())
while x != 0:
    if x > best:  # новое число больше лучшего?
        best = x  # запоминаем его
    x = int(input())
print(best)

Вместе с максимумом можно хранить и другое: второе по величине, сколько раз он встретился. Важно не забыть, что при смене максимума эти данные тоже меняются.

Условие

поиск максимума

Вводится последовательность натуральных чисел, в конце стоит 0 — сам 0 в последовательность не входит. Нужно узнать, сколько чисел последовательности равны самому большому из них.

Входные данные. Натуральные числа, каждое в отдельной строке. Последнее число — 0.

Выходные данные. Одно число — сколько раз встречается максимум.

Входные данныеВыходные данные
1 7 9 01
1 3 3 1 02
Твоя программа на Python
Разбор

Идея. Максимум и счётчик ищем за один проход. Встретили число больше максимума — это новый максимум, и счётчик начинается заново с 1. Встретили равное — счётчик плюс один.

Ловушка: при новом максимуме счётчик надо сбросить на 1, а не прибавлять. Иначе на 1 1 5 0 ответ будет 3 вместо 1.

Решение на Python — комментарий после # объясняет строку, Python его не выполняет.

best = 0  # самое большое число, пока не нашли
count = 0  # сколько раз оно встретилось
x = int(input())  # первое число
while x != 0:  # пока не 0
    if x > best:  # нашли число больше максимума?
        best = x  # это новый максимум
        count = 1  # пока он встретился один раз
    elif x == best:  # число равно максимуму?
        count += 1  # считаем ещё одно
    x = int(input())  # следующее число
print(count)  # печатаем ответ

Что используется в решении.

  • input() читает одну строку ввода, int() превращает её в целое число.
  • while условие: — цикл «пока»: повторяется, пока условие верно. Удобен, когда заранее неизвестно, сколько будет чисел, — например, до числа 0.
  • if … elif …: — ветвление: elif («иначе если») проверяется, только если первое условие неверно.
  • if условие: — ветвление: строки с отступом под ним выполняются, только если условие верно.
  • != — «не равно».
  • > — «больше».
  • += — увеличить переменную: count += 1 — то же, что count = count + 1.
  • print() — выводит ответ. Печатаем только ответ, без лишних слов.