Числовые последовательности: соседство, условия и общий результат
Почему порядок чисел определяет группы, как переводить условия в проверки и отделять отбор от вычисления результата.
Обработка списка чисел связывает два масштаба: свойства всей последовательности и свойства небольшой группы соседних элементов. Сначала из всех данных может быть получен порог. Затем по этому порогу проверяются пары или тройки, а результаты проверок объединяются в количество, минимум или максимум. Такое разделение помогает сохранить точный смысл условия.
Порядок и соседство
Последовательность — числа, расположенные в определённом порядке. Число на отдельном месте называется её элементом. Место важно даже при повторяющихся значениях: два одинаковых числа на разных позициях могут иметь разных соседей.
Пусть длина последовательности равна N, а её элементы обозначаются a_1,a_2,\ldots,a_N. Индекс у буквы указывает позицию, начиная с единицы. Соседняя пара с началом на позиции i состоит из a_i и a_{i+1}. Для её существования нужна следующая позиция, поэтому последнее возможное начало — N-1.
Аналогично тройка заканчивается на позиции i+2, и её последнее начало равно N-2. Если длина группы равна w и элементов достаточно, всего получается N-w+1 групп. Каждое новое начало сдвигается на одну позицию; этот приём называют скользящим окном.
В настоящем фрагменте 53141,10803,77333 пары (53141,10803) и (10803,77333) различаются началами. Общее число 10803 не делает их одной парой. В задаче с перекрывающимися подходящими парами ↗ учитываются обе. Поэтому сортировка или удаление повторов меняет не только запись данных, но и сам набор проверяемых групп.
Общее свойство и проверка группы
Минимальный элемент, максимальное число с нужным окончанием и количество кратных заданному делителю относятся ко всей последовательности. Результат такого подсчёта может стать общим порогом, одинаковым для каждой группы.
Например, правило «сумма двух остатков равна минимальному элементу файла» требует сначала найти минимум всего файла. Даже если сейчас проверяется первая пара, её судьбу может определить число в самом конце. Поэтому текущий минимум прочитанной части ещё не годится для проверки.
В примере с общим минимумом ↗ порог равен 8. Для пары 53141,10803 остатки при делении на 18 равны 5 и 3, поэтому 5+3=8: группа подходит. После отбора складываются сами числа, и получается 63944. Условие отбора и величина для ответа выполняют разные функции.
Удобная организация вычисления состоит из двух проходов. Первый находит характеристику всей последовательности, второй проверяет соседние группы. Хранение чисел в списке позволяет возвращаться к ним, сохраняя исходный порядок.
Как слова задают логическое условие
Условие отбора — проверка, результат которой может быть истинным или ложным. Например, «число трёхзначное» или «сумма меньше порога». Связка «и» требует выполнения обеих проверок, а «или» допускает выполнение хотя бы одной, в том числе обеих. В Python им соответствуют and и or.
Когда правило относится к числу элементов с признаком, сначала подсчитывается, сколько элементов группы этот признак имеют. В тройке 8756,-85,-442 только одно число трёхзначное. Поэтому количество равно 1. Это самодостаточная проверка слов «ровно одно» из условия о трёхзначном элементе ↗; остальные ограничения задачи проверяются отдельно.
Полученное количество обозначается буквой c, а число из формулировки — буквой k. Тогда различие между словами становится точным:
| Формулировка | Проверка |
|---|---|
| Ровно k | c=k |
| Не менее k | c\ge k |
| Не более k | c\le k |
| Хотя бы один | c\ge1 |
Проверка any в Python отвечает только на вопрос, есть ли хотя бы один истинный признак. Она не отличает один подходящий элемент от двух. Для «ровно один» нужен счёт или равносильное ему логическое условие.
Знак, количество цифр и остаток
Знак минус не считается цифрой. Поэтому число x трёхзначное тогда и только тогда, когда 100\le|x|\le999. Здесь |x| — модуль, расстояние от числа до нуля; в Python он вычисляется как abs(x). Числа 442 и −442 оба трёхзначные, хотя при сложении дают разные вклады.
Окончание десятичной записи тоже определяется по модулю. У числа −915 последние две цифры — 15, поэтому abs(-915) % 100 равно 15. Но -915 % 100 в Python равно 85: остаток при положительном делителе неотрицателен, и -915=(-10)\cdot100+85. Последние цифры записи и остаток отрицательного числа — разные понятия.
Модуль нужен для распознавания записи, но не заменяет число при поиске минимума. Например, -915<-115, хотя 915>115. В задаче о минимальном числе с окончанием 15 ↗ среди подходящих трёхзначных элементов выбирается само число −915. Его квадрат вычисляется уже после выбора: (-915)^2=837225.
Порядок арифметических действий
Составное выражение сначала переводится буквально. Сумма остатков двух чисел может быть больше делителя, тогда как остаток их суммы всегда меньше положительного делителя. При делении на 18 у учебных чисел 17 и 9 сумма остатков равна 26, а остаток суммы — 8. Совпадение этих двух выражений для некоторых пар не делает их взаимозаменяемыми.
Так же различаются квадрат суммы и сумма квадратов. В примере с квадратом суммы тройки ↗ числа равны 325,80,-99. Их сумма — 306, поэтому квадрат суммы равен 93636. Сумма отдельных квадратов равна 121826. Первое число меньше порога 99033, второе — больше; замена выражения изменит решение о включении группы.
Для отрицательной суммы её квадрат тоже неотрицателен. Сумма обозначается буквой s, а положительный порог — буквой T. Условие s^2<T ограничивает величину суммы с обеих сторон. Одной верхней границы для s недостаточно: очень большое по модулю отрицательное число тоже нарушает условие. Непосредственное возведение суммы в квадрат сохраняет обе границы.
Как объединяются результаты проверок
Для каждой принятой группы счётчик увеличивается на единицу. Одновременно вычисляется величина, указанная в вопросе: например, сумма элементов или произведение наименьшего и наибольшего элементов группы. Среди этих значений выбирается минимум либо максимум; такие крайние значения называют экстремумами.
Первая подходящая группа задаёт начальное значение для сравнения. Это надёжнее произвольного нуля: если все допустимые суммы отрицательны, ноль не является их максимумом. Отдельное значение None позволяет различать ещё не найденный результат и настоящий нулевой результат.
Порядок отбора и последующего преобразования сохраняется. Для учебного набора сумм -100,-3,2 максимум равен 2, и его модуль тоже 2. Если сначала взять модули, наибольшим станет 100. Так объясняется различие между «модулем максимальной суммы» и «максимальным модулем суммы».
При фиксированной длине группы на каждую позицию приходится ограниченное число действий. Два прохода по последовательности вдвое длиннее требуют примерно вдвое больше работы. Поэтому такой способ называют линейным алгоритмом: объём вычислений растёт пропорционально числу элементов, несмотря на наличие двух проходов.
Как сохранить перекрывающиеся пары и отделить сумму остатков от суммы для ответа? Как меняются проверки при переходе к тройкам и отрицательным числам? Программа для настоящего файла и разбор этих условий приведены в материале «Задание №17. Соседние пары и тройки: от условия к подсчёту».