Проект Эйлера (33 задача). Задача легко решается банальным перебором. Однако нет предела совершенствованию.
Узнать больше в телеграм-канале: ProjectEuler++
Дробь 49/98 является любопытной, поскольку неопытный математик, пытаясь сократить ее, будет ошибочно полагать, что 49/98 = 4/8, являющееся истиной, получено вычеркиванием девяток.
Дроби вида 30/50 = 3/5 будем считать тривиальными примерами.
Существует ровно 4 нетривиальных примера дробей подобного типа, которые меньше единицы и содержат двухзначные числа как в числителе, так и в знаменателе.
Пусть произведение этих четырех дробей дано в виде несократимой дроби (числитель и знаменатель дроби не имеют общих сомножителей). Найдите знаменатель этой дроби.
Измеряем время работы программы
Поскольку функция main() получилась довольно-таки объемной, потому решил не “мельчить” и разбить ее аж на три скриншота.
Вариант с простым перебором чисел и их последующей проверке условиям задания подробно рассматривать не будем.
Потому что главная его проблема – в количестве этих чисел. Поскольку речь идет о двузначных числах (от 10 до 99) в числителе и знаменателе (ab/cd), потому речь может идти переборе около 10000 вариантов их сочетаний.
Не так много, однако их нужно еще раскладывать на множители, выявлять из них имеющие одинаковые цифры в диагонали т.п. В любом случае можно в итоге сделать эффективней.
Более перспективным является перебор не всех чисел, а только имеющих одинаковые цифры на диагонали дроби.
Т.е. для дроби вида:
Поскольку цифра B одинакова в числителе и знаменателе, потому перебирать нужно будет не два двузначных числа, а три числа от 1 до 9. Что в итоге может дать менее 1000 комбинаций и потому сократить количество вычислений сразу на порядок.
Поскольку не хотелось бы загромождать программу кучей переменных, потому создадим структуру данных fraction (дробь). В ней будут храниться значения числителя и знаменателя дроби, а также значения их старших и младших регистров.
Далее все просто:
Поскольку у дроби вида ab/cd может быть две диагонали с одинаковыми цифрами:
… потому понадобится еще раз перебирать множители в цикле для второго варианта расположения диагонали.
Их можно было бы расположить в один цикл, однако есть один нюанс, описанный в задании.
Числитель дроби не должен быть больше знаменателя. Потому для дроби вида aB/Bc необходимо ограничивать значение числа (a) в числителе:
И потому же для дроби Ab/cA ограничиваем число (c) в знаменателе:
Поскольку часть циклов будет ограничена вышеизложенными соображениями, потому это еще сильнее сократит количество вычислений.
Также согласно заданию необходимо получить в вид в виде несократимой дроби. Потому в конце всех вычислений дробь сокращаем с помощью специальной функции simplify().
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Поскольку при создании структуры ее поля заполнены случайными значениями, потому необходима функция для внесения в нее первоначальных значений.
Так же при каждой новой итерации циклов, получается новая дробь и ее значения необходимо менять.
Функция принимает отдельные цифры дроби, вычисляет значения числителя и знаменателя и в итоге заносит данные в структуру.
Данная функция перебирает делители и ищет тот, который нацело делит как числитель, так и знаменатель. При этом, поскольку из задания известно, что числитель меньше знаменателя, потому в качестве делителя принимается ряд чисел вплоть до числителя.
Как только делитель найден, перебор останавливается и оба члена дроби сокращаются на него. Поскольку перебор идет от большего числа к меньшему, потому найденный в итоге делитель (если он есть) является максимальным и дальнейший поиск не нужен.
Функция принимает как саму проверяемую дробь, так и два числа, перебором которых она образована (уже без повторяющейся цифры). Потому нет необходимости вычитать из дроби повторяющиеся цифры отдельной операцией.
Далее обе дроби по возможности сокращаются функцией simplify().
Равенство числителей и знаменателей сокращенных дробей означает, что условие задания в итоге выполнено.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
