Зачастую в 27 номере мы сталкиваемся с трудностями в оптимизации, и, хотя мы прекрасно знаем, какие методы нужно применять из прошлой статьи, все равно непонятно, как именно можно воспользоваться оптимизацией. В этой статье мы разберем базовые методы оптимизации и их применение на конкретных примерах.
Рассмотрим стандартную задачу №27 на поиск пар.
Звучит она так:
Дан набор из N целых положительных чисел. Из этих чисел формируются все возможные пары (парой считаются два элемента, которые находятся на разных местах в наборе, порядок чисел в паре не учитывается), в каждой паре вычисляется сумма элементов. Необходимо определить количество пар, для которых полученная сумма делится на 7.
Начинаем разбираться. Очевидно, что можно сделать полный пересчет всевозможных пар, для этого нужно понять, как эти самые пары будут стыковаться.
Первое число нашей последовательности – это 3. Оно будет образовывать пары со всеми числами, идущими после себя. То есть {3,5};{3,8};{3,1}…{3,7} Следующее число – это 5. По логике число 5 будет образовывать пару с первым числом 3. Но ведь такая пара уже посчитана для числа 3, и, по факту, мы просто поменяем порядок элементов в паре, но никакую новую не получим, поэтому ее считать мы не будем. Также число 5 не может образовать пару с самим собой, потому что оно всего лишь одно. Получается, что первое число, подходящее в пару к пятерке, – это число 8, которое является следующим для пяти. Аналогично и для 8: пары {8,3} и {8,5} уже посчитаны, а пары {8,8} быть не может т.к. восьмерка всего одна. Значит, получаем простую закономерность:
Для i-того числа в пару подходят любые числа, начиная с i+1.
Значит, для неэффективного решения нам всего-то потребуется посчитать весь массив чисел из файла в какой-нибудь массив/список, и потом пройтись по нему вложенным циклом. Проверяя сумму каждой пары на кратность 7. Легче легкого, однако из предыдущего урока мы помним, что такой алгоритм имеет сложность O(N2), что дает нам неэффективность по времени, тем более, запоминая все числа в массиве, мы еще получаем неэффективность по памяти. Однако для файла А, в котором чисел не так много, данный алгоритм подойдет идеально, и с помощью него мы получим 1 из 2 баллов.
Примечание
Не забывайте, что раз в нашем цикле существует элемент с индекс i+1, то первый цикл должен приходить до N-1, потому что для элемента с индексом N не существует последующего, и мы можем получить ошибку «list index out of range», что переводится как выход за границу массива.
Теперь настала пора подумать, как же оптимизировать нашу программу для гигантского файла B, для которого наш примитивный алгоритм будет работать непростительно долго?
Шаг 1. Эффективность по времени.
Сперва вспомним, что задачи 27 направлены на ваше критическое мышление, эрудицию и знания математики и логики, а не на банальное знания языка программирования, поэтому нам придется обратиться к теории чисел. Обозначим первое число в паре – A, второе – B. Знак «%» будет обозначать остаток от деления (как в языке Python).
Так вот дилемма: когда же A + B кратно 7? Правило очень простое: когда сумма остатков от деления на 7 у чисел A и B равна 7 или 0. В общем виде правило звучит так:
Когда сумма A + B кратна N?
Когда (A%N) + (B%N) = N или 0
Таким образом, чтобы узнать количество пар с суммой кратной 7, нам достаточно узнать количество чисел со всеми возможными остатками от деления на 7:
0, 1, 2, 3, 4, 5, 6.
А после комбинаторно их перемножить, ведь любое число с остатком 1 дает пару с любым числом с остатком 6 (потому что 1+6 = 7). Аналогично 2 и 5 и тд. Единственный возникающий казус произойдет с числами кратными 7 – у них остаток равен 0. Они будут компоноваться в пары друг с дружкой, поэтому их просто перемножить не получится. Но на помощь к нам снова приходит комбинаторика. У нас имеется набор чисел; сколькими способами можно выбрать 2 из них?
Cn2=n!n-2!2!= nn-1(n-2)!n-2!2=n(n-1)2
Можете использовать эту формулу сразу (числа, образовывающие пары сами с собой считаются по формуле n(n-1)/2 вот и все).
Шаг 2. Эффективность по памяти.
Раз мы получили возможность сохранять всего лишь 7 чисел (массив остатков), то и необходимости записывать все вводимые числа у нас отпадает, а значит, используемая память не зависит от количества введенных чисел, и мы достигли просвещения, ведь наша программа теперь не содержит вложенных циклов и эффективна по памяти.
Итак, в этой статье мы разобрали как решать задачу №27. Теперь вы сможете получить баллы, желаю успехов на экзамене!