Задачи на программирование · поиск двух наибольших

Второй максимум

Источник: informatics.msk.ru, задача №3070. Условие пересказано своими словами. На 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 07
Твоя программа на Python
Разбор

Идея. Храним два числа: самое большое first и второе second. Новое число больше максимума — старый максимум «спускается» на второе место. Иначе, если оно больше второго, — занимает второе место.

Ловушка: когда меняется максимум, нельзя забыть сдвинуть старый на второе место. Иначе на тесте 1 2 0 ответ будет 0 вместо 1.

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

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

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

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