Проект Эйлера (26 задача) потребует лишь знания математики начальных классов. Однако всегда есть возможность ускорить работу программы
Узнать больше в телеграм-канале: ProjectEuler++
Единичная дробь имеет 1 в числителе. Десятичные представления единичных дробей со знаменателями от 2 до 10 даны ниже:
1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 = 0.125 1/9 = 0.(1) 1/10 = 0.1 Где 0.1(6) значит 0.166666…, и имеет повторяющуюся последовательность из одной цифры. Заметим, что 1/7 имеет повторяющуюся последовательность из 6 цифр.
Найдите значение d < 1000, для которого 1/d в десятичном виде содержит самую длинную повторяющуюся последовательность цифр.
Поясню суть алгоритма, использованного в программе на примере.
Делим 1 на 6 в столбик, как на школьных уроках:
В итоге из данного примера видно, что как только мы получили остаток от деления – цикл замкнулся. Вычисления будут вновь и вновь повторяться и потому цифры дробной части тоже.
Из сути алгоритма следует, что длина повторяющейся последовательности не может быть больше знаменателя дроби. Так происходит, потому что при остаток при делении всегда меньше делителя.
Например, для дроби number / 7, остаток от деления number % 7 может быть 0, 1, 2, 3, 4, 5 и 6, т.е. в итоге будет возможно лишь семь вариантов. Потому через семь итераций либо будет найдена искомая повторяющаяся последовательность, либо дробная часть закончится.
Потому эффективней перебирать делители дроби не с начала (с 2), а конца (от 1000). Кроме того, как только максимальная длина повторяющейся последовательности (для уже перебранных делителей) превысит значение очередного делителя, поиск уже можно прекратить. Потому что дальнейшие (еще меньшие) делители будут давать последовательности еще меньшей длины (смотрите скриншот выше).
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Функция работает на вышеописанном алгоритме:
Работа цикла while останавливается, если на одной из итераций остаток от деления становится равен нулю. Это будет означать, что дробная часть закончилась.
Также цикл остановится, когда встретится остаток от деления, который ранее уже был. В таком случае – обнаружена повторяющаяся последовательность.
Как сохранять вычисленные остатки?
В данной функции используются два массива.
В одном (res_cash[]) значения будут сохраняться по их индексу.
В итоге это позволяет, как легко сохранять значения остатков, так и проверять, не вычислялся ли такой остаток ранее.
Во второй массив (res_arr[]) значения остатков охраняются по порядку, в котором они вычисляются. Необходимость этого будет подробно объяснено ниже.
Помимо сохранения чисел по их индексу, в программе применены динамические массивы. Сделано так потому, что иначе (при использовании массивов фиксированной длины) будет перерасход памяти и лишние операции при обработке излишне длинных массивов. Нет необходимости при обработке дроби 1 / 8 использовать 1000-значный массив.
Поскольку мой компилятор не поддерживает массивы переменной длины типа:
… потому воспользовался функциями calloc() и free():
Функция принимает массив (с занесенными в него остатками), число и ищет в нем индекс первой ячейки с искомым значением.
Зачем это нужно? Поясню на примере.
Если вычислять значение дроби 1/6, то мы в итоге получим значение 0.166666... Мы видим, что цифра 6 в дробной части бесконечно повторяется. Однако при этом видно, что повторяющийся цикл не начинается с первого же знака после запятой.
Вычисления останавливаются, когда остаток совпал с ранее уже вычисленным. Потому, чтобы вычислить искомую длину цикла нам и понадобится индекс этого (ранее вычисленного) остатка. Длина цикла в итоге будет равна разности между их индексами.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
