Решение 26 задачи проекта Эйлера: Обратные циклы

В программе используется длинная арифметика и алгоритм поиска "образа" в массиве со "смещением"

Условия задачи

Единичная дробь имеет 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 в десятичном виде содержит самую длинную повторяющуюся последовательность цифр.

Описание работы программы

Программа для решения задачи Эйлера #26

Для хранения результатов деления создаём массив arr[] достаточной длины, чтобы выявить повторявшуюся последовательность. Забегая вперёд, после нескольких вычислений принял массив длиной 2000 ячеек, т.к. найденная самая длинная повторяющаяся последовательность будет длиной почти тысячу цифр.

В самой программе будут перебираться делители до 1000, результаты деления заноситься в массив arr[], после чего в нем будет определяться самая длинная повторяющаяся последовательность.

Работа функции get_div_arr()

Получение результатов деления - задача Эйлера #26

По сути функция делит “столбиком”, как в начальных классах. Целочисленные результаты деления заносит в массив, остаток от деления умножает на десять и повторно делит. Если не делится, то ещё раз умножает и заносит при этом ноль в массив. Вычисление останавливается при окончании массива или если остаток от деления разделился нацело.

Функция возвращает количество занесённых в массив элементов. Это нужно, чтобы не “обнулять” массив каждый раз, просто часть данных перезаписывается в массиве. Также это позволяет в дальнейшем не прогонять проверки до конца массива, если значащие цифры вычислений закончились ранее.

Работа функции get_max_series()

Получение длины максимальной повторяющейся последовательности цифр в массиве - задача Эйлера #26

Поиск повторяющийся последовательности самый бесхитростный. В двух циклах for по массиву перемещаются два указателя i_ptr и j_ptr. Как только они указывают на одинаковое значение в массиве, то они синхронно начинают смещаться вправо, попутно считая совпадения счетчиком cnt. Длина максимальной повторяющейся последовательности сохраняется в max_cnt.

• Для уменьшения количества итераций после нахождения очередной повторяющейся последовательности указатель смещается сразу на ее длину по массиву.
• Также в случае, если конец первой проверяемой последовательности (с указателем i_ptr) достиг начала второй последовательности (указатель j_ptr), то поиск прекращается, искомая последовательность найдена.

Ответ на задачу:

P.S. Изначальная цель блога - получить "фидбек" в комментариях, чтобы более опытные "кодеры" указывали мне на ошибки, советовали и всячески помогали в саморазвитии.

Также приглашаю всех на мой сайт)

На нем Вы можете посмотреть ответ на задачу Эйлера 26 (когда необходима лишь небольшая подсказка) и последний, самый быстрый вариант решения.

А Вы уже подписались на канал?)

В общем, добро пожаловать на канал))