1. Как решать задание ЕГЭ
7. Задание проверяет умение составить алгоритм обработки числовой последовательности и записать его в виде простой программы на языке программирования.
Пример задания (демоверсия \(2022\))
Рис. \(1\). Пример задания
Что нужно знать?
1. Как считать данные из файла в список.
Для работы с файлом удобно использовать конструкцию with :
with open (file) as f:
инструкции
Эта конструкция определяет для открытого файла переменную \(f\) и выполняет набор инструкций. После их выполнения файл автоматически закрывается. Метод readlines() прочитает и вернёт все строки в файле в виде списка.
Для работы с данными файла мы будем использовать следующий программный код:
with open (\(’17.txt’\)) as f:
\(a=\) [int(\(x\)) for \(x\) in f.readlines()]
2. Основные операторы для работы со списками (массивами).
В Python для того, чтобы работать с большим количеством данных, используется структура данных под названием список . Список представляет собой последовательность (набор) элементов, пронумерованных от \(0\).
Чтобы объявить список, нужно в квадратных скобках перечислить его элементы через запятую:
Элементы списка могут быть разных типов в отличие от элементов массива, но, как правило, используются списки из элементов одного типа.
Методы списков
| \(a.append (x)\) | добавляет элемент \(x\) в конец списка \(a\) |
| \(a.count (x)\) | возвращает количество элементов списка \(a\) со значением \(x\) |
| \(а.sort ()\) | сортирует список \(a\) в порядке возрастания |
| \(а.reverse ()\) | разворачивает список \(a\) в обратном порядке |
| \(a.clear ()\) | очищает список \(a\) |
Функции для работы со списками
| \(len(a)\) | возвращает длину списка \(a\) (количество элементов списка \(a\)) |
| \(min(a)\) | возвращает наименьший элемент списка \(a\) |
| \(max(a)\) | возвращает наибольший элемент списка \(a\) |
| \(sum(a)\) | возвращает сумму элементов списка \(a\) |
Решение задачи можно разбить на этапы.
1. Считать данные из текстового файла в массив (список). Важно, чтобы программа решения и текстовый файл лежали в одной папке (или необходимо указать полный путь для считывания файла).
with open (\(’17.txt’\)) as\(f\):
\(a=\) [int(\(x\)) for \(x\) in f.readlines()]
2. Необходимо в массиве найти максимальное число, кратное \(3\). Для этого инициализируем пустой массив \(b\). Затем с помощью цикла \(for\) переберём все элементы массива \(a\). Если элемент кратен \(3\), то запишем его в массив \(b\). После выполнения цикла в переменную \(m\) запишем максимальное значение массива \(b\).
\(b=[]\)
for \(i\) in range (\(0,len(a)\)):
if \(a[i]\) % \(3= =0\):
b.append\((a[i])\)
\(m=max(b)\)
3. Определим количество подходящих пар. Для этого очистим массив \(b\). Затем с помощью цикла \(for\) переберём все элементы массива \(a\). Если хотя бы один элемент пары делится на \(3\) и сумма элементов пары не больше \(m\), то запишем эту сумму в массив \(b\).
\(b=[]\)
for \(i\) in range (\(0\),\(len(a)-1\)):
if (\(a[i]\) % \(3= =0\) or \(a[i+1]\) % \(3= =0\)) and (\(a[i]+a[i+1] <=m\)):
b.append (\(a[i]+a[i+1]\))
4. Выведем на экран количество элементов массива \(b\) — оно равно количеству подходящих пар — и максимальную сумму:
print (\(len(b), max(b)\))
Получилась программа:
with open (\(’17.txt’\)) as\(f\):
\(a=\) [int(\(x\)) for \(x\) in f.readlines()]
\(b=[]\)
for \(i\) in range (\(0,len(a)\)):
if \(a[i]\) % \(3= =0\):
b.append (\(a[i]\))
\(m=max(b)\)
\(b=[]\)
for \(i\) in range (\(0,len(a)-1\)):
if (\(a[i]\) % \(3= =0\) or \(a[i+1]\) % \(3= =0\)) and (\(a[i]+a[i+1] <=m\)):
b.append (\(a[i]+a[i+1]\))
Функция open. Чтение и запись текстовых файлов в Python
Большие объемы данных хранят не в списках или словарях, а в файлах и базах данных. В этом уроке изучим особенности работы с текстовыми файлами в Python. Такие файлы рассматриваются как содержащие символы и строки.
Бывают еще байтовые (бинарные) файлы, которые рассматриваются как потоки байтов. Побайтово считываются, например, файлы изображений. Работа с бинарными файлами несколько сложнее. Нередко их обрабатывают с помощью специальных модулей Python (pickle, struct).
Функция open
Связь с файлом на жестком диске выполняется с помощью встроенной в Python функции open() . Обычно ей передают один или два аргумента. Первый – имя файла или имя с адресом, если файл находится не в том каталоге, где находится сама программа. Второй аргумент – режим, в котором открывается файл.
Обычно используются режимы чтения ( ‘r’ ) и записи ( ‘w’ ). Если файл открыт в режиме чтения, то запись в него невозможна. Можно только считывать данные. Если файл открыт в режиме записи, то в него можно только записывать данные, считывать нельзя.
Если файл открывается в режиме ‘w’ , то все данные, которые в нем были до этого, стираются. Файл становится пустым. Если не надо удалять существующие в файле данные, тогда следует использовать вместо режима записи, режим дозаписи ( ‘a’ ).
Если файл отсутствует, то открытие его в режиме ‘w’ создаст новый файл. Бывают ситуации, когда надо гарантировано создать новый файл, избежав случайной перезаписи данных существующего. В этом случае вместо режима ‘w’ используется режим ‘x’ . В нем всегда создается новый файл для записи. Если указано имя существующего файла, то будет выброшено исключение. Потери данных в уже имеющемся файле не произойдет.
Если при вызове open() второй аргумент не указан, то файл открывается в режиме чтения как текстовый файл. Чтобы открыть файл как байтовый, дополнительно к букве режима чтения/записи добавляется символ ‘b’ . Буква ‘t’ обозначает текстовый файл. Поскольку это тип файла по умолчанию, то обычно ее не указывают.
Нельзя указывать только тип файла, то есть open(«имя_файла», ‘b’) есть ошибка, даже если файл открывается на чтение. Правильно – open(«имя_файла», ‘rb’) . Только текстовые файлы мы можем открыть командой open(«имя_файла») , потому что и ‘r’ и ‘t’ подразумеваются по-умолчанию.
Функция open() возвращает объект файлового типа. Его надо либо сразу связать с переменной, чтобы не потерять, либо сразу прочитать.
Чтение файла
С помощью файлового метода read() можно прочитать файл целиком или только определенное количество байт. Пусть у нас имеется файл data.txt с таким содержимым:
one - 1 - I two - 2 - II three - 3 - III four - 4 - IV five - 5 - V
Откроем его и почитаем:
>>> f1 = open(‘data.txt’) >>> f1.read(10) ‘one — 1 — ‘ >>> f1.read() ‘I\ntwo — 2 — II\nthree — 3 — III\nfour — 4 — IV\nfive — 5 — V\n’ >>> f1.read() » >>> type(f1.read())
Сначала считываются первые десять символов. Последующий вызов read() считывает весь оставшийся текст. После этого объект файлового типа f1 становится пустым.
Заметим, что метод read() возвращает строку, и что конец строки считывается как ‘\n’ .
Для того, чтобы читать файл построчно существует метод readline() :
>>> f1 = open('data.txt') >>> f1.readline() 'one - 1 - I\n' >>> f1.readline() 'two - 2 - II\n' >>> f1.readline() 'three - 3 — III\n'
Метод readlines() считывает сразу все строки и создает список:
>>> f1 = open('data.txt') >>> f1.readlines() ['one - 1 - I\n', 'two - 2 - II\n', 'three - 3 - III\n', 'four - 4 - IV\n', 'five - 5 - V\n']
Объект файлового типа относится к итераторам. Из таких объектов происходит последовательное извлечение элементов. Элементами в данном случае являются строки-линии файла. Поэтому считывать данные из файла можно сразу в цикле без использования методов чтения:
>>> for i in open('data.txt'): . print(i) . one - 1 - I two - 2 - II three - 3 - III four - 4 - IV five - 5 - V >>>
Здесь выводятся лишние пустые строки, потому что функция print() преобразует ‘\n’ в переход на новую строку. К этому добавляет свой переход на новую строку. Создадим список строк файла без ‘\n’ :
>>> nums = [] >>> for i in open('data.txt'): . nums.append(i[:-1]) . >>> nums ['one - 1 - I', 'two - 2 - II', 'three - 3 - III', 'four - 4 - IV', 'five - 5 - V']
Переменной i присваивается очередная строка файла. Мы берем ее срез от начала до последнего символа, не включая его. Следует иметь в виду, что ‘\n’ это один символ, а не два.
Запись в файл
Запись в файл выполняется с помощью методов write() и writelines() . Во второй можно передать структуру данных:
>>> l = ['tree', 'four'] >>> f2 = open('newdata.txt', 'w') >>> f2.write('one') 3 >>> f2.write(' two') 4 >>> f2.writelines(l)
Метод write() возвращает количество записанных символов.
Закрытие файла
После того как работа с файлом закончена, важно не забывать его закрыть, чтобы освободить место в памяти. Делается это с помощью файлового метода close() . Свойство файлового объекта closed позволяет проверить закрыт ли файл.
>>> f1.close() >>> f1.closed True >>> f2.closed False
Если файл открывается в заголовке цикла ( for i in open(‘fname’) ), то видимо интерпретатор его закрывает при завершении работы цикла или через какое-то время.
Практическая работа
- Создайте файл data.txt по образцу урока. Напишите программу, которая открывает этот файл на чтение, построчно считывает из него данные и записывает строки в другой файл ( dataRu.txt ), заменяя английские числительные русскими, которые содержатся в списке ( [«один», «два», «три», «четыре», «пять»] ), определенном до открытия файлов.
- Создайте файл nums.txt , содержащий несколько чисел, записанных через пробел. Напишите программу, которая подсчитывает и выводит на экран общую сумму чисел, хранящихся в этом файле.
Примеры решения и дополнительные уроки в pdf-версии курса
X Скрыть Наверх
Python. Введение в программирование
Файлы. Работа с файлами.
В данной статье мы рассмотрим встроенные средства python для работы с файлами: открытие / закрытие, чтение и запись.
Итак, начнем. Прежде, чем работать с файлом, его надо открыть. С этим замечательно справится встроенная функция open:
f = open('text.txt', 'r')
У функции open много параметров, они указаны в статье «Встроенные функции«, нам пока важны 3 аргумента: первый, это имя файла. Путь к файлу может быть относительным или абсолютным. Второй аргумент, это режим, в котором мы будем открывать файл.
| Режим | Обозначение |
| ‘r’ | открытие на чтение (является значением по умолчанию). |
| ‘w’ | открытие на запись, содержимое файла удаляется, если файла не существует, создается новый. |
| ‘x’ | открытие на запись, если файла не существует, иначе исключение. |
| ‘a’ | открытие на дозапись, информация добавляется в конец файла. |
| ‘b’ | открытие в двоичном режиме. |
| ‘t’ | открытие в текстовом режиме (является значением по умолчанию). |
| ‘+’ | открытие на чтение и запись |
Режимы могут быть объединены, то есть, к примеру, ‘rb’ — чтение в двоичном режиме. По умолчанию режим равен ‘rt’.
И последний аргумент, encoding, нужен только в текстовом режиме чтения файла. Этот аргумент задает кодировку.
Чтение из файла
Открыли мы файл, а теперь мы хотим прочитать из него информацию. Для этого есть несколько способов, но большого интереса заслуживают лишь два из них.
Первый — метод read, читающий весь файл целиком, если был вызван без аргументов, и n символов, если был вызван с аргументом (целым числом n).
>>> f = open('text.txt') >>> f.read(1) 'H' >>> f.read() 'ello world!\nThe end.\n\n'
Ещё один способ сделать это — прочитать файл построчно, воспользовавшись циклом for:
>>> f = open('text.txt') >>> for line in f: . line . 'Hello world!\n' '\n' 'The end.\n' '\n'
Запись в файл
Теперь рассмотрим запись в файл. Попробуем записать в файл вот такой вот список:
>>> l = [str(i)+str(i-1) for i in range(20)] >>> l ['0-1', '10', '21', '32', '43', '54', '65', '76', '87', '98', '109', '1110', '1211', '1312', '1413', '1514', '1615', '1716', '1817', '1918']
Откроем файл на запись:
>>> f = open('text.txt', 'w')
Запись в файл осуществляется с помощью метода write:
>>> for index in l: . f.write(index + '\n') . 4 3 3 3 3
Для тех, кто не понял, что это за цифры, поясню: метод write возвращает число записанных символов.
После окончания работы с файлом его обязательно нужно закрыть с помощью метода close:
>>> f.close()
Теперь попробуем воссоздать этот список из получившегося файла. Откроем файл на чтение (надеюсь, вы поняли, как это сделать?), и прочитаем строки.
>>> f = open('text.txt', 'r') >>> l = [line.strip() for line in f] >>> l ['0-1', '10', '21', '32', '43', '54', '65', '76', '87', '98', '109', '1110', '1211', '1312', '1413', '1514', '1615', '1716', '1817', '1918'] >>> f.close()
Мы получили тот же список, что и был. В более сложных случаях (словарях, вложенных кортежей и т. д.) алгоритм записи придумать сложнее. Но это и не нужно. В python уже давно придумали средства, такие как pickle или json, позволяющие сохранять в файле сложные структуры.
Практика оптимального программирования. Поиск нескольких чисел в большом объеме данных
Трудно найти иголку в стоге сена? Труднее найти две. А еще труднее — найти две конкретные иголки, которые будут дополнять друг друга. Давайте поговорим, как можно решить такую задачу быстро и эффективно при помощи программирования.
Постановка проблемы. Переборное решение
Анализ больших данных — частая проблема, с которой приходится сталкиваться программистам. И дело не в том, что это сложно. Сложно сделать это быстро.
В статье «Практика оптимального программирования. Поиск делителей числа» мы уже занимались поиском подходящих чисел на достаточно больших диапазонах. Чтобы программа работала быстрее, мы находили способы сократить перебор и не считать лишние данные. Такой подход работает не всегда.
Например, на таком условии задачи: из указанного массива чисел выбрать два таких, чтобы их произведение было кратным 14 и наибольшим, а также вывести на экран это произведение.
Самое простое решение — перебор. Для каждого числа мы проверим все возможные пары, найдем из них подходящие и выберем максимальные. Пары будем рассматривать для каждого числа со всеми последующими в массиве.
Что нам понадобится для реализации такой программы?
- Сам массив с числами.
- Два цикла for, причем второй будет вложен в первый. Внешний цикл будет перебирать сами числа от первого до предпоследнего, внутренний — все последующие числа (от следующего числа до самого последнего).
- Проверка подходящей пары.
- Заранее созданная переменная, в которую мы сохраним максимальное подходящее число.
numbers = [21, 16, 4, 45, 35, 9, 88, 76, 77, 18] max_couple = 0 for first in range(len(numbers) - 1): for second in range(first + 1, len(numbers)): if ((numbers[first] * numbers[second]) % 14 == 0 and max_couple < numbers[first] * numbers[second]): max_couple = numbers[first] * numbers[second] print(max_couple) Вывод: 6776Прекрасно, все работает, и даже достаточно быстро. Но для десяти чисел можно было не писать программу, мы бы и вручную справились. Будет ли работать это решение, если чисел будет 100? 1000? 10000? И как передать такой объем данных в программу?
Чтение данных из файла
Когда данных очень много, неудобно записывать их прямо в программе. Проще хранить их в отдельном файле, и в нем же редактировать.
Для открытия файлов в Python используется следующая запись:
Разберем элементы этой записи:
- Сам файл будет записан в указанную переменную, что позволит нам работать с ним как, собственно, с переменной.
- Команда open откроет файл по указанному пути.
- Если текстовый файл лежит в одной папке с файлом вашей программы, то в качестве пути файла можно указать только его имя — программа найдет его в своей же папке.
Если же файл находится в другом месте, необходимо прописывать полный путь
- Режим доступа — дополнительный параметр. Файл можно открыть так, чтобы его можно было читать, но нельзя в него ничего записывать. Или наоборот — открыть файл на запись, но тогда он будет переписан, а прочитать его мы не сможем.
- режим “r” откроет файл только на чтение;
- режим “w” — только на запись, причем этот режим полностью очистит документ;
- режим “a” позволит дописывать информацию к имеющейся.
Если не указать этот параметр совсем, файл будет открыт по умолчанию только на чтение.
Чтобы считывать данные из файла, есть несколько способов:
- команда readline будет считывать по одной строке текстового файла;
- readlines создаст массив, в котором будут храниться сразу все строки файла;
- как строку или массив, файл можно перебирать с помощью цикла for.
Важно запомнить — читаются данные из файла именно в строковом формате. Если нужно преобразовать их к числам, делаем это с помощью команды int.
Если у нас есть текстовый документ text.txt, в котором прописаны необходимые числа — каждое в новой строке — у нас есть несколько способов создать массив, содержащий все эти числа. Для удобства, пусть в первой строке файла будет количество чисел для обработки.
В итоге результат один — в списке numbers будут находиться все числа из файла в количестве count штук.
Допишем эту часть в наш код и попробуем запустить:
file = open("text.txt") count = int(file.readline()) numbers = list(map(int, file.readlines())) max_couple = 0 for first in range(len(numbers) - 1): for second in range(first + 1, len(numbers)): if ((numbers[first] * numbers[second]) % 14 == 0 and max_couple < numbers[first] * numbers[second]): max_couple = numbers[first] * numbers[second] print(max_couple)Теперь засечем время, сколько будет работать программа для поиска пар чисел при разном количестве чисел в файле:
- 100 чисел — 0.1 секунда;
- 1000 чисел — 0.2 секунды;
- 10000 чисел — 6.5 секунды.
Давайте рассмотрим, как полученные знания могут помочь при выполнении 27 номера ЕГЭ.
Задание. Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности. Из указанного массива чисел выбрать два таких, чтобы их произведение было кратным 15 и наибольшим. Вывести на экран это произведение.
Решение.
По аналогии напишем код, о котором мы говорили выше.
file = open(«text.txt»)
count = int(file.readline())
numbers = list(map(int, file.readlines()))for first in range(len(numbers) — 1):
for second in range(first + 1, len(numbers)):
if ((numbers[first] * numbers[second]) % 15 == 0 and max_couple < numbers[first] * numbers[second]):
max_couple = numbers[first] * numbers[second]
print(max_couple)В данном случае мы рассмотрели переборное решение. Как правило, оно подходит для небольших файлов, с небольшим количеством чисел.
Станет хуже, если мы начнем искать тройки чисел. Для этого понадобится немного изменить программу — добавить третий внутренний цикл и учесть третье число в проверке произведения:
file = open("text.txt") count = int(file.readline()) numbers = list(map(int, file.readlines())) max_couple = 0 for first in range(len(numbers) - 2): for second in range(first + 1, len(numbers) - 1): for third in range(second + 1, len(numbers)): if ((numbers[first] * numbers[second] * numbers[third]) % 14 == 0 and max_couple < numbers[first] * numbers[second] * numbers[third]): max_couple = numbers[first] * numbers[second] * numbers[third] print(max_couple)И снова засекаем время:
- 100 чисел — 0.2 секунды;
- 1000 чисел — 45.5 секунды;
- 10000 чисел — за 8 часов программа так и не выполнилась.
Это явно не самый успешный результат. От перебора надо избавляться и придумывать что-то хитрее.
Но для этого нам потребуется вспомнить некоторые знания математики. Начнем с произведения множителей.
Произведение множителей
Все числа можно разложить на произведение простых множителей. Например:
4 = 2 * 2
12 = 2 * 2 * 3
22 = 2 * 11По условию задачи нам нужно произведение, которое кратно 14. Число 14 можно разложить как 2 * 7. Значит, в искомом произведении среди множителей должны найтись 2 и 7. Например:
- Если умножить 4 на 21, в разложении получится 4 * 21 = 2 * 2 * 3 * 7. Среди множителей есть 2 и 7, тогда это произведение поделится на 14.
- Если умножить 14 на 17, мы получим 14 * 17 = 2 * 7 * 17. Так как в произведении уже есть 14, оно уже будет кратно 14, какое бы второе число мы ни подставили.
- Если умножить 15 на 18, получим 15 * 18 = 3 * 5 * 2 * 3 * 3. Семерки среди множителей нет, значит, это произведение не будет кратно ни 7, ни 14.
Значит, чтобы получить произведение, кратное 14, надо чтобы один из множителей был кратен 14, либо одно из чисел кратно 2, а второе — 7. Отсортируем заранее все числа из файла по группам: кратные 14, кратные 7, кратные 2 и не кратные ничему из этого. Тогда найти необходимое произведение не составит труда.
Оптимальная программа будет состоять из следующих элементов:
- массивов, в которые мы будем распределять числа;
- дополнительного условия распределения чисел в цикле чтения данных из файла — в зависимости от кратности числа будем заносить его в соответствующую группу;
- подсчет итогового ответа.
Как мы уже выяснили раньше, подходящей парой будет та, в которой одно число будет кратно 14, а второе — вообще любое, в том числе другое кратное 14. Либо нужна пара, в которой одно число кратно 2, а второе — 7. Так как нам нужно наибольшее произведение, будем брать наибольшие множители. Нам поможет команда max и сортировка по убыванию — наибольшие элементы будут в самом начале массива, их будет удобно брать по индексам.
Далее в этой статье будем работать вот с этим файлом: text.txt.
file = open("text.txt") count = int(file.readline()) kr14 = [] kr7 = [] kr2 = [] nekr = [] for number in file: if int(number) % 14 == 0: kr14.append(int(number)) elif int(number) % 7 == 0: kr7.append(int(number)) elif int(number) % 2 == 0: kr2.append(int(number)) else: nekr.append(int(number)) kr14.sort(reverse = True) kr7.sort(reverse = True) kr2.sort(reverse = True) nekr.sort(reverse = True) ans1 = kr14[0] * max(kr14[1], kr2[0], kr7[0], nekr[0]) ans2 = kr2[0] * kr7[0] print(max(ans1, ans2)) Вывод: 99890000Выполнение программы не заняло много времени.
Давайте рассмотрим, как оптимальное программирование может помочь при выполнении 27 номера ЕГЭ. Посмотрим пример того же номера, о котором мы говорили выше.
Задание. Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности. Из указанного массива чисел выбрать два таких, чтобы их произведение было кратным 15 и наибольшим. Вывести на экран это произведение.
Решение. Чтобы получить произведение, кратное 15, надо чтобы один из множителей был кратен 15, либо одно из чисел кратно 3, а второе – 5. Для этого у нас будут массивы!
На самом деле код аналогичен тому, что мы рассмотрели, но тут важно понять, что число 15 или 14 может меняться в зависимости от условия, поэтому каждый раз необходимо подбирать делители чисел.
file = open(«text.txt»)
count = int(file.readline())for number in file:
if int(number) % 15 == 0:
kr15.append(int(number))
elif int(number) % 5 == 0:
kr5.append(int(number))
elif int(number) % 3== 0:
kr3.append(int(number))
else:
nekr.append(int(number))kr15.sort(reverse = True)
kr5.sort(reverse = True)
kr3.sort(reverse = True)
nekr.sort(reverse = True)ans1 = kr15[0] * max(kr15[1], kr5[0], kr3[0], nekr[0])
ans2 = kr5[0] * kr3[0]Умея читать большое количество данных из файла, а также умея грамотно распределять числа, давайте решим еще одну проблему — поиск не произведения, а суммы.
Остатки от деления
Теперь мы хотим найти пару чисел, сумма которой будет кратна 17. Как проверить кратность суммы?
Обратимся к математике.
Кратное 17 число можно представить как 17n, где n — натуральное число (1, 2, 3 и так далее).
Если число не кратно 17, то его можно представить как 17n + m, где m будет остатком от деления числа на 17.
Попробуем рассмотреть различные варианты суммы двух чисел:
- если сложить два числа, кратных 17, никаких проблем не будет — 17n1 + 17n2 = 17(n1 + n2), среди множителей сразу появляется 17, значит, сумма будет кратна 17;
- если числа будут с какими-то остатками от деления, то понадобится дополнительное условие: 17n1 + m1 + 17n2 + m2 = 17 * (n1 + n2) + m1 + m2. Надо вынести 17 в общий множитель, чтобы все выражение было кратно 17.
m1 и m2 не могут быть кратны 17 по отдельности, так как это остатки от деления. Значит, их сумма должна быть кратна 17, то есть m1 + m2 = 17n3. Только тогда мы сможем вынести 17 общим множителем.
Нам снова придется сортировать числа, но не по кратности, а по остаткам от деления. Остатком от деления на 17 может быть любое число от 0 до 16. Здесь мы можем создать двумерный список, про который мы говорили в статье «Работа с массивами в Python». Нам нужно 17 внутренних списков, которые будут иметь индексы от 0 до 16. В каждый мы сможем заносить числа по остаткам от деления — чтобы остаток был равен индексу.
В коде нам понадобятся:
- Заранее созданный двумерный список с 17 пустыми списками внутри.
- Сортировка чисел файла по внутренним спискам. Какой остаток от деления на 17, такой и индекс внутреннего списка;
- Сортировка внутренних списков для удобства.
- Список, в который мы будем складывать потенциальные ответы.
- Потенциальные ответы — сумма наибольших чисел внутренних массивов с индексами i и 17 — i .В сумме они должны дать ровно 17 — это и обеспечит нам необходимую сумму. Перебирать i будет достаточно до 8. При i = 8 мы проверим индексы 8 и 9, а при i = 9 — 9 и 8, то есть начнем повторяться.
- Для i = 0, чисел, кратных 17, проверка должна быть отдельной, так как мы будем брать два таких наибольших числа.
- Перед подсчетом любой суммы — поверка:
- есть числа с необходимыми остатками от деления — считаем;
- нет таких чисел — считать нечего.
Следующий код полностью выполнит все необходимые требования, и работать будет очень быстро:
file = open("text.txt") count = int(file.readline()) kr = [] for i in range(17): kr.append([]) for number in file: number = int(number) kr[number % 17].append(number) for i in range(17): kr[i].sort(reverse = True) ans = [] if len(kr[0]) >= 2: ans.append(kr[0][0] + kr[0][1]) for i in range(1, 9): if len(kr[i]) > 0 and len(kr[17 - i]) > 0: n = kr[i][0] + kr[17 - i][0] ans.append(n) print(max(ans)) Вывод: 19992
Мы рассмотрели важный аспект оптимального программирования. Этот подход включает в себя постоянное обучение и развитие, рациональный выбор инструментов, эффективную организацию кода. Оптимальное программирование – непрерывный процесс, и каждый из этих аспектов может быть улучшен и адаптирован под конкретные ситуации!
Если вы хотите узнать больше о Python, рекомендуем ознакомиться со статьей «Основы программирования на языке Python. Часть 1».Фактчек
- Для открытия файла в программе используется команда open, а для чтения данных из него — команды readline (читает одну строку) и readlines (считает сразу все).
- Произведение чисел будет кратно n, если среди множителей этого произведения можно найти такие, произведение которых будет равно n.
- Сумма чисел будет кратна n, если сумма их остатков от деления будет кратна n.
Проверь себя
Задание 1.
В каких ситуациях переборное решение не будет работать?- Во всех. Это решение бесполезно и не имеет права на существование.
- В определенных, это всегда зависит от условия задачи.
- При очень большом количестве перебираемых данных.
- Ни в каких. Это хорошее решение, которое можно использовать в любой ситуации.
Задание 2.
В файле text.txt найдите наибольшее произведение двух чисел, которое будет кратно 21.- 99880011
- 99878121
- 99922211
- Такого произведения нет
Задание 3.
В файле text.txt найдите наибольшую сумму двух чисел, которая будет кратна 11.Ответы: 1. — 3; 2. — 1; 3. — 3.