Продолжаю серию статей про задачи №27 ЕГЭ по информатике. Для тех, кто только что присоединился, первая часть — здесь. Сегодня речь пойдет об одном из способов использования массивов для хранения данных программы. Иногда говорят, что если решать задачу на полный балл, то массивы использовать нельзя. Но на самом деле массивы — очень удобный инструмент для хранения некоторых данных, для которых необходимо также сохранять и какое-то их свойство. В этой статье поговорим о том, как такое можно реализовать. Начнем с простого подсчета.
Задача 1
Для последовательности из n целых неотрицательных чисел, меньших 1000, необходимо определить наиболее часто встречающуюся сумму цифр.
В этой задаче, кажется, все понятно: для каждого числа определяем сумму его цифр, запоминаем, что такая сумма цифр была, затем по количеству запомненных сумм определяем ту, которая встречается чаще всего. Но как запоминать, что чисел с суммой цифр, например, 2, было 7 штук, а чисел с суммой цифр 5 — 10?
Вспомним математику
Для начала определимся, какой может быть сумма цифр, если известно, что оно не больше 1000? Очевидно, что в этом случае число имеет не более 3 цифр. Чем больше цифры в числе, тем больше их сумма. Самая большая цифра в десятичной системе — 9, значит, для указанных в условии чисел сумма цифр не может быть больше 9+9+9=27.
Массив фиксированного размера
Сделанный в предыдущем пункте вывод помогает нам понять, что достаточно хранить 28 значений (от 0 до 27 включительно). Каждое значение — количество чисел с определенной суммой цифр. Вместо введения переменных вида count0, count1, count2, …, count27 для таких целей удобно использовать массив фиксированного размера 28, у которого индекс — сумма цифр, а значение — количество элементов последовательности с такой суммой цифр. Длина такого массива не увеличится при увеличении количества чисел в последовательности, а значит, это не приведет к снижению оценки за задачу.
Когда все основные моменты поняты, можно переходить к итоговому оформлению задачи: считыванию входных данных, определению максимального количества чисел с определенной суммой и выводу на экран выходных данных.
Код этой задачи доступен на GitHub: https://github.com/kormanowsky/ege-27/blob/master/2_useful_index.py
Теперь давайте посмотрим, как эта идея может применяться при подсчете числа пар элементов последовательности.
Задача 2
Для последовательности из n целых неотрицательных чисел необходимо посчитать число пар, сумма чисел в которых делится на 9.
Снова вспомним математику
Сумма каких двух чисел делится на 9? Напомню, что сумма чисел a и b делится на c тогда, когда сумма остатков от деления a и b на c делится на c. Доказать это несложно. Пусть a = c*k + r1, b = c*t + r2, где k, t, r1, r2 — целые числа, r1 и r2 < c. тогда a+b=c*k+c*t+(r1+r2). В последнем равенстве все слагаемые, кроме r1+r2, делятся на c, а значит, вся сумма будет делиться на c, если r1+r2 делится на c.
Назовем остатки r1 и r2 парными, если r1+r2 делится на 9. Пусть значение r1 известно, а r2 нам требуется найти. r1 и r2 < 9, значит, их сумма < 2*9=18 и если сумма остатков делится на 9, то она равна либо 0, либо 9, поэтому парный остаток найдем вычитанием из 9 известного остатка.
Получили, что для 0 парный остаток — 9, но остаток по определению должен быть меньше 9. Исправим это, взяв остаток от деления на 9 после вычитания:
Остаток — индекс, количество — значение
Разобравшись с математикой, переходим к применению идеи в задаче. Индексом массива удобно выбрать остаток от деления на 9, значением — количество элементов, которые в последовательности идут до текущего и имеют некоторый остаток от деления на 9. Таким образом, потребуется массив длины 9, с индексами от 0 до 8. Отдельно будем хранить общее число подходящих пар.
Для каждого элемента определим его собственный остаток от деления на 9 и парный остаток. Сначала увеличим общее число пар на число элементов, идущих до текущего и имеющих парный остаток, затем увеличим на 1 значение элемента массива, индекс которого равен остатку текущего элемента. Делать это нужно именно таком порядке, чтобы избежать попадания в общее число пар вида a[i] + a[i], за что оценка за задачу снижается.
Как и в предыдущей задаче, до полного текста программы остается оформить считывание входных данных и вывод на экран ответа — общего количества подходящих пар.
Код задачи на GitHub: https://github.com/kormanowsky/ege-27/blob/master/2_userful_index_pairs.py