Часть своего свободного времени я уделяю обучению на платформах для дистанционного обучения и прохожу разные курсы. Больше всего мне нравится Stepik.org.
На этом ресурсе можно найти много курсов для "чайников", где понятным языком объясняются разные аспекты IT (и не только).
После освоения основ язык программирования Python, я пошел дальше и поступил на курс "Алгоритмы и структуры данных" от Computer Science Center (Сейчас разделен на два: Алгоритмы: теория и практика. Методы и Алгоритмы: теория и практика. Структуры данных).
Трудности настигли на первом же уроке - "Числа Фибоначчи".
Для справки:
Числа Фибоначчи - это последовательность, в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Числа Фибоначчи на OEIS.
Последняя задача урока - задача на программирование повышенной сложности:
Даны целые числа n и m (1 <= n <= 1018, 2 <= m <= 105), необходимо найти остаток от деления n-го числа Фибоначчи на m.
Memory Limit - 256 Mb
Time Limit - 5 seconds.
Как можно догадаться, ограничения по памяти и времени не позволят наивному алгоритму пройти решение.
Немного погуглив, я наткнулся на обсуждение такого термина как "период Пизано".
Оказывается, что если составить последовательность из остатков деления чисел Фибоначчи на какое-ибо число, то остатки будут чередоваться с определенной периодичностью.
Возьмем первые тринадцать чисел - 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 - и найдем остатки деления на 4 - 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1.
Остатки чередуются с периодичностью каждые 6 членов, таким образом период Пизано для делителя 4, равен 6.
Для решения задачи, описанной ранее, прежде всего необходимо определить тот самый период, с указанным делителем.
Для этого в отдельный массив записываем остатки от деления чисел Фибоначчи на m до тех пор, пока не получим две единички идущие подряд.
Далее, для удобства, удаляем два последних числа массива.
После этого нужно найти x - остаток от деления n на период Пизано.
Ну и наконец, программа должны вывести число из массива с остатками с номером x.
Это и будет ответом задачи.
Еще информации на Вики и в OEIS.
На этом все )
На этом ресурсе можно найти много курсов для "чайников", где понятным языком объясняются разные аспекты IT (и не только).
После освоения основ язык программирования Python, я пошел дальше и поступил на курс "Алгоритмы и структуры данных" от Computer Science Center (Сейчас разделен на два: Алгоритмы: теория и практика. Методы и Алгоритмы: теория и практика. Структуры данных).
Трудности настигли на первом же уроке - "Числа Фибоначчи".
Для справки:
Числа Фибоначчи - это последовательность, в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Числа Фибоначчи на OEIS.
Последняя задача урока - задача на программирование повышенной сложности:
Даны целые числа n и m (1 <= n <= 1018, 2 <= m <= 105), необходимо найти остаток от деления n-го числа Фибоначчи на m.
Memory Limit - 256 Mb
Time Limit - 5 seconds.
Как можно догадаться, ограничения по памяти и времени не позволят наивному алгоритму пройти решение.
Немного погуглив, я наткнулся на обсуждение такого термина как "период Пизано".
Оказывается, что если составить последовательность из остатков деления чисел Фибоначчи на какое-ибо число, то остатки будут чередоваться с определенной периодичностью.
Возьмем первые тринадцать чисел - 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 - и найдем остатки деления на 4 - 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1.
Остатки чередуются с периодичностью каждые 6 членов, таким образом период Пизано для делителя 4, равен 6.
Для решения задачи, описанной ранее, прежде всего необходимо определить тот самый период, с указанным делителем.
Для этого в отдельный массив записываем остатки от деления чисел Фибоначчи на m до тех пор, пока не получим две единички идущие подряд.
Далее, для удобства, удаляем два последних числа массива.
После этого нужно найти x - остаток от деления n на период Пизано.
Ну и наконец, программа должны вывести число из массива с остатками с номером x.
Это и будет ответом задачи.
Еще информации на Вики и в OEIS.
На этом все )
