Сегодня разберем одну из типовых задач, в которых требуется исследовать текстовый файл и извлечь из него какую-то информацию. Часто эти задачи связаны с большими числами и большим количеством чисел. В большинстве случаев в таких заданиях присутствует математическая хитрость, на которой построен поиск результата. Итак, приступаем...
Задача
Файл содержит последовательность неотрицательных целых чисел, не превышающих 10 000. Назовём тройкой три идущих подряд элемента последовательности. Определите количество троек чисел таких, которые могут являться сторонами остроугольного треугольника. В ответе запишите два числа: сначала количество найденных троек, а затем — максимальную сумму элементов таких троек. Если таких троек не найдётся — следует вывести 0 0.
Файл к задаче (скачать через яндекс.диск)
Решение:
Для начала посмотрим на реальный файл из ЕГЭ и подумаем как лучше с ним работать. Устно и на черновике (руками) результат работы программы на таком файле не проверить. Это проблема. Как её будем решать?
Что конкретно от нас хотят в условии? Здесь может [ложно] показаться, что нам необходимо найти просто тройки чисел, которые могут образовывать треугольник. Условие для этого: никакая сторона не превосходит суммы двух других сторон. Однако, если еще раз внимательно прочитать условие задачи, то нужно, чтобы тройка чисел образовывала стороны именно остроугольного треугольника. Для этого можно вспомнить теорему косинусов и сделать геометрический рисунок, из которого сразу будет видно нужно нам условие (квадрат наибольшей стороны должен быть меньше суммы квадратов двух других сторон).
Изначально к заданию дается большой файл с большими числами. Какова вероятность того, что вы с первого раза напишите правильный алгоритм без гугления и подсказок? Поэтому я предлагаю вам всегда проводить тесты на более маленьких файлах. Результат работы вашей программа на таких файлах вы сможете проверить быстро и устно.
Теперь перейдем к решению. Можно решать стандратно, а можно воспользоваться всеми прелестями (синтаксическим сахаром) языка Python. (Документация Python)
Первый способ
Используем построчные итерации по файлу, считывая три строки по отдельности, затем переводим их в числа и находим большую, среднюю и меньшую стороны. А после исследуем их в цикле. Цикл выполняется до тех пор, пока нам удается считать последнюю строку и она не оказывается пустой (чтобы получалась полноценная тройка). Далее используем наше геометрическое условие и находим новые числа. Закрываем файл и выводим результат.
Второй способ
Он короче (длинным он кажется только из-за комментариев). Здесь мы начинаем использовать списки. Сначала создаем список, затем добавляем туда все строки из файла (по ходу дела конвертируем строки в числа). Затем интерируемся по созданному списку и создаем отсортированный список из каждой текущей тройки элементов. Проверяем условие на остроугольный треугольник и выводим результат. Также добавим немного реалистичности кода в виде отлавливания исключений (проблем, которые могут нам попасться во время написания программы).
Третий способ
Для тех, кому нравится короткий код больше, чем подробности. Постараемся сохранить смысл, но укоротим код с помощью генератора списка и использования функции max еще разок (чтобы избавиться от if-конструкций).
Все три варианта дают одинаковый результат. Когда мы отлаживаем алгоритм на маленьком файле, то потом можем переключить программу на большой файл.
Результат работы программы
Количество подходящих троек: 1175
Максимальная сумма элементов троек: 29451
Еще задачи по информатике
7 задач по информатике и программированию из ЕГЭ: подробный разбор
Неочевидная математика банковской системы
Разбор 12 задания из ЕГЭ по информатике
Как перенести названия всех файлов текущей директории в текстовый файл .txt в Python?
Как ускорить выполнение цикла? Алгоритм оптимизации циклов
Задача 15 из ЕГЭ по информатике
Задача 27 из ЕГЭ по информатике: полный разбор
Как оптимизировать программы | Разбор задачи из ЕГЭ по информатике
Метод прогонки: решение СЛАУ с трехдиагональной матрицей
8 хороших задач для начинающих: программируем на Python
Метод Якоби: решение СЛАУ методом итерации
Разбираем циклы в Python на простых примерах. Какой цикл быстрее?
Численные методы: составление обратной зависимости x(y) для сложных зависимостей y(x)
Шифр Цезаря — один из самых первых способов шифрования
Как обратить последовательность чисел, не используя массивов и динамических структур
7 задачек по информатике для тех, кто начинает изучать Python
Нужна ли математика для начинающего программиста?
Время работы алгоритма простого поиска элемента в массиве. Время работы кода на C++
Что делать, если программирование кажется сложным, но очень хочется разобраться в нем? #1
Задача, с которой можно начать изучение массивов [ C/C++ ] Подробный разбор
Оптимизация поиска количества делителей | Ускоряем программу в 58 раз | Разбор ЕГЭ по информатике
Какая строка получится? Разбор 12 задачи из ЕГЭ по информатике
Понравилась статья? Поставьте лайк, подпишитесь на канал! Вам не сложно, а мне очень приятно :)
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в telegram
