Продолжаем тему об остатках, начатую в предыдущей статье. В прошлый раз необходимо было найти количество пар, сумма которых делится на определенное число, а сегодня будем искать некоторую пару, удовлетворяющую заданному условию.
Задача 1
В последовательности натуральных чисел, состоящей из n членов, найти пару элементов, сумма элементов в паре делится на m = 80 и минимальна. Если в последовательности несколько пар с одинаковой минимальной суммой, вывести любую. Если пар, удовлетворяющих условию задачи, в последовательности нет, вывести два нуля.
Парные остатки
Здесь будем использовать те же названия, что и в прошлый раз. Напомню: парными называем остатки, при сложении дающие 0 или делитель. Например, остатки 4 и 6, считаются парными, если делим на 10. Сумма чисел в паре будет делиться на m, если числа будут иметь те самые парные остатки от деления на m.
Минимальная сумма
В каком случае сумма двух чисел будет минимальной? Очевидно, что если сами числа минимальны, то и их сумма будет минимальной. На этом этапе рассуждений логичным будет предположение о том, что нужно найти два минимальных элемента, имеющих парные остатки, и тогда они образуют пару, удовлетворяющую условию задачи.
Полезный индекс
Эта идея пригодится для решения этой задачи. Мы снова можем использовать остаток от деления на m = 80 в качестве индекса, а минимальный элемент с таким остатком — в качестве значения. Но m = 80 — число четное, поэтому возможен вариант, что требуемую пару образуют два числа, остаток которых равен 40. Нам придется запоминать два числа с таким остатком от деления.
Разбиваем массив
Самое простое решение, как указанные выше числа сохранить, — использовать массив на m+2 элемента (m-1 остатков от 1 до m-1, 2 элемента с остатком 0, 2 элемента с остатком m/2). Такой метод хранения вызывает неудобство, так как номера индексов «сбиваются», что может привести к ошибкам в написании кода, вычисляющего индекс элемента с тем или иным остатком от деления.
Поэтому предлагаю не хранить все минимальные элементы в одном массиве, а разбить этот массив на две половины, по m/2+1 элемент каждая. Первая ( «левая») половина будет хранить элементы с индексами 0, 1, 2, …, m / 2, а вторая («правая») — с индексами 0, m — 1, m — 2, …, m / 2. Также договоримся, для остатков 0 и m / 2 первая половина будет хранить самый маленький элемент, а вторая — второй по величине.
Удобство именно такого способа сохранения нужных элементов еще и в том, что пару очень легко получить и проверить, минимальна ли сумма? Для этого достаточно написать, например, left_half[0] + right_half[0], где left_half и right_half — массивы, содержащие «левую» и «правую» половины.
Проверка и запись элементов при использовании двух массивов тоже упрощаются. Для принятия решения о записи элемента необходимо:
- Взять остаток от деления элемента на m, обозначим r.
- Если r = 0 или r = m / 2, сравнить сначала с left_half[r], если проврка удачна, записать туда, если нет, проделать то же самое с right_half[r].
- Если 1 ≤ r ≤ m / 2 — 1, сравнивать с left_half[r].
- Если m / 2 + 1 ≤ r ≤ m — 1, m — r (без взятия остатка от деления) будет равно парному индексу, а заодно и индексу в правой половине, так как r ≠ 0. В этом случае сравнивать с right_half[m-r].
В конце программы необходимо будет пройти циклом от 0 до m / 2 включительно и среди запомненных пар найти лучшую.
Код задачи на GitHub: https://github.com/kormanowsky/ege-27/blob/master/3_two_arrays_sum.py
Задача 2
В последовательности натуральных чисел, состоящей из n членов, найти пару элементов, разность элементов в паре делится на m = 80 и максимлаьна. Если в последовательности несколько пар с одинаковой максимлаьной суммой, вывести любую. Если пар, удовлетворяющих условию задачи, в последовательности нет, вывести два нуля.
Такая же задача?
Эта задача очень сильно похожа на предыдущую (честно говоря, я просто скопировал текст предыдущей задачи и поменял в нем некоторые слова), но условие «годности» пары здесь другое — на m должна делиться не сумма, а разность элементов последовательности.
Еще раз вспомним математику
Пусть в последовательности есть два элемента a = m*x + t и b = m*y+s, где a, b, x, t, y, s — натуральные числа либо нули. Тогда разность этих элементов будет равна a — b = m*(x — y) + (t — s). Первое слагаемое в этом выражении делится на m, поэтому очевидно, что второе тоже толжно делиться на m, и тогда вся сумма поделится на m. По правилам математики, 0 ≤ t , s < m, значит, значение выражения t — s никак не может быть больше или равно m. Поэтому t — s делится на m только тогда, когда t — s = 0, то есть t = s.
Два массива
Здесь можно заметить, что мы ищем два элемента последовтельности с одинаковым остатком от деления. Удобно будет снова использовать идею «Полезный индекс», но хранить элементы в двух массивах: в первом будем сохранять первый максимум с определенным остатков, во втором — второй максимум. Тогда разность сохраненных в первом и во втором массивах элементов будет делиться на m, а сумма их будет максимальна.
В остальном идея задачи повторяет идею задачи 1, поэтому комментировать больше ничего не буду, а оставлю ссылку на код задачи: https://github.com/kormanowsky/ege-27/blob/master/3_two_arrays_diff.py