Задача 26
В текстовом файле записан набор натуральных чисел, не превышающих 10⁹. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар. Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.
В ответе запишите два целых числа: сначала количество пар, затем наибольшее среднее арифметическое.
Как видно из первой строчки, файл содержит N = 5000, что довольно много. Значит любая "дорогая" операция сильно затормозит программу.
В нашей программе требуется исследовать пары чисел. А это значит, что каждому из N элементов файла нужно сопоставить остальные N - 1 элементов файла. Но если мы так пройдем до конца, то все пары чисел пройдут по 2 раза. То есть количество проверок нужно разделить на 2. Итак, у нас ориентировочно Count = N * (N - 1) / 2 сравнений. Помните формулу количества ребер полного графа? Вот это именно тот случай.
Получается, что для N элементов мы имеем квадратичную сложность выбора пар. Если мы попытаемся сделать два вложенных цикла считывания из файла, то столкнемся с большими проблемами:
1. Легко запутаться, так как нужно будет запоминать позиции считывания в файле;
2. Операции обращения к файлу, лежащему в постоянной памяти, очень дорогие по времени. Поэтому даже правильно написанная программу будет работать очень долго. Думаю, что это даже не будет особо зависеть от того HDD у вас или SSD;
Каким тогда может быть решение?
Можно попробовать считать все элементы файла в массив. Да, массив будет большой, но зато мы будем иметь быстрый доступ к нему из RAM. Здесь может показаться, что достаточно записать в массив только четные элементы, ведь пары должны состоять из четных элементов. Однако, это не так. Даже если у нас есть два четных числа, то среднее арифметическое может быть нечетным. Пример: a = 2, b = 20, сред. арифм. = (2 + 20)/2 = 11 - нечетное. Получается, что мы должны записывать все числа из файла: как четные, так и нечетные. Считывание можно организовать следующим образом:
![Считывание из текстового файла '26.txt' все 5000 элементов в массив x[]](https://avatars.dzeninfra.ru/get-zen_doc/4488311/pub_60a391ef79be7e21744d61e2_60a44c6ad00cb53fcbebb03a/scale_1200)
Что делать, если мы имеем все элементы файла в массиве?
Останется перебрать все файлы без повтора (это учитывается во внутреннем цикле for), а при нахождении подходящей пары, запускать цикл проверки по всем элементам, чтобы полным перебором определить, а есть ли среднее арифметическое подходящей пары в массиве. Ну и по ходу делать обновлять максимальное значение среднего арифметического.
Сделать это можно так:
И, казалось бы, всё хорошо и логично, но тогда и не было бы смысла писать об этом заметку. Да, такая программа выдаст вам правильный результат, но займет кучу времени на подсчет.
Как определить время выполнение программы в Pascal
В языке Pascal, как и в других ЯП, можно определить время выполнения с помощью встроенной в модуль Utils функции Milliseconds, которая возвращает текущее время в миллисекундах с момента запуска процесса текущей программы.
Чтобы определить время выполнения конкретного участка кода, можно засечь таймер перед проблемным участком, скорость которого нужно проверить, а затем зафиксировать момент сразу после выполнения этого участка. Разница этих двух переменных будет составлять время выполнения нужного нам участка кода.
Теперь приведу полную реализацию первого наивного решения вместе со временем выполнения:
Время выполнения такого решения получается 62 минуты 49 секунд. В общем, нужна большая уверенность в правильности программы, чтобы дождаться до её завершения. Мне это было интересно, поэтому я просто поставил на выполнение и пошел пить чай :) Но я понимаю, что на реальном экзамене человек не может позволить себе ждать так долго результат.
Что делать, чтобы ускорить ?
Вот тут начинаются мысли об оптимизации. Что ж, с методом подбора пар мы не сделаем ничего. Здесь придется оставить полный перебор. Но вот можно ли сделать что-то с поиском числа в массиве? Да, на самом деле можно. Мы можем подготовить наши данные для того, чтобы использовать бинарный поиск (иногда называют двоичный поиск).
К сожалению, практика работы с учениками, показала, что во многих школах, даже в физ-мат лицеях, учителя информатики ничего не рассказывают про двоичный поиск, хотя в таких вот задачах ЕГЭ он может понадобиться.
Чтобы использовать этот поиск, нужно отсортировать данные. Я предлагаю отсортировать по возрастанию, хотя сути алгоритма это не меняет. Мы всё равно не будем выводить отсортированный массив из 5000 элементов.
Бинарный поиск (двоичный поиск) – алгоритм поиска в упорядоченном множестве чисел, использующий метод деления области поиска пополам и имеющий логарифмическую сложность. Здесь логарифмическая сложность является той оптимизацией, которая нам поможет ускорить программу.
Для начала попробуем самый простой метод пузырьковой сортировки. Сразу же посмотрим сколько времени он занимает на N = 5000. Для этого напишу отдельную программу, где будет только сортировка для рандомно генерирующегося массива:
Сортировка 5000 элементов занимает 11 секунд. Несколько запусков программы показывают одно и то же число. То есть сортировка не является узким местом будущей оптимизации. Я имею в виду, что дополнительные 11 секунд можно подождать по сравнению 62 минутами.
Бинарный поиск для массива можно реализовать следующим образом:
Теперь давайте объединим всё это в программу и посмотрим что нам даст такая оптимизация:
После данной оптимизации мы имеем время выполнения программы: 7 минут 29 секунд. Из которых 11 секунд уходит на сортировку массива
Такие преобразования ускоряют наш код примерно в 9 раз.
Стоит ли переписывать функцию сортировки? На мой взгляд, это не имеет смысла делать на ЕГЭ. Да, быстрая сортировка будет работать быстрее. Но в силу более сложного алгоритма, который вдобавок ко всему связан с рекурсией, вы можете допустить там ошибку и потерять время на её исправление. Допустим сортировка стала быстрее и выполняется 1-2 секунды. Вы всё равно будете ждать 7 минут, потому что основной код перебора всех пар уже никак не оптимизировать, потому что мы не знаем заранее где в файле находятся четные пары.
Вот такая вот интересная задача, время которой очень сильно зависит от выбора способа решения. То есть на больших файлах можно использовать именно этот способ: сначала сортируем, потом ищем бинарным поиском.
Весь код и файлы в telegram канале IT mentor
Понравился разбор задачи? Проявите активность: лайк, репост, комментарий.
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram