Наибольший общий делитель двух чисел Фибоначчи

Задача

Найти последнюю цифру наибольшего общего делителя двух чисел Фибоначчи.

Решение

Сразу отклоняем вычисление чисел Фибоначчи и нахождение их НОД, так как числа могу быть очень большие.

Воспользуемся свойством чисел Фибоначчи:

Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов.

\(НОД(F_n, F_m) = F_{НОД(n, m)}\)

Учитвая это вычисляем индекс числа Фибоначчи который одновременно является и нужным НОД, а затем находим его последнее число при помощи периода Пизано.

Сложность

Сложность алгоритма равна сложности нахождения наибольшего общего делителя. Так как вычисления периода Пизано при заданном модуле ограничено сверху, то его можно взять за константу.

Код

На вход подаются два индекса чисел Фибоначчи.

Exercism.io

На сайте exercism.io организовано обучение языкам программирования. Лучше всего сайт подойдёт тем кто уже знает один ЯП и хочет изучить новый. Для обучения доступно 52 языка, наибольшее количество задач по C#, Python и JavaScript.

Exercism бесплатный, работает благодаря сообществу. Пользователи делятся на учеников и наставников. Ученики выполняют задачи, а наставники проводят code review и дают советы. Комментарии от наставников полезные и продуманные, примеры я приложил ниже.

Выполнение задач

После выбора трека, устанавливаем консольное приложение. Запускаем команду, указанную в описании задачи на сайте, и приложение формирует каталог, файл с шаблоном для выполнения задачи и файл с тестами.

Выполняем задание, проверяем что решение проходит тесты. Выполнять задачи и проходить тесты можно в любой IDE, система на неё не завязана.

Выполняем ещё одну консольную команду и задача отправляется на проверку. Длительность проверки зависит от загруженности проверяющих на выбранном языковом треке. На треке Python я ждал проверки от дня до 3х недель. Первый комментарий от наставника:

Наставники уделяют особое внимание стилю и адекватности применяемых конструкций:

Бывают и более сложные замечания:

После исправления замечаний, решение снова отправляется на проверку. И так пока наставник не одобрит решение. Затем открывается следующая задача.

Такой принцип применяется к задачам из основного трека по языку. Кроме них есть ещё дополнительные задачи. Code review от наставника в них не обязателен, зато можно посмотреть решения других участников. В треке Python 18 основных задач и около 100 дополнительных.

Python. Сортировка

Python содержит несколько различных способов сортировки данных. Встроенный метод списков list.sort() изменяет вызвавший его список. Встроенная функция sorted() создаёт новый сортированный список из итерируемого объекта.

Простая сортировка

Чтобы отсортировать список по возрастанию вызовите функцию sorted(). Функция вернёт новый сортированный список:

Метод list.sort() сортирует список у которого вызван и возвращает None. Если исходный список больше не нужен это может быть немного эффективнее:

Метод list.sort() определён только для списков. В отличи от него, функция sorted() работает с любыми перечисляемыми объектами:

Читать далее Python. Сортировка

Встроенные функции Python для ввода и вывода (print, input)

print(*objects, sep=' ', end='\n', file=sys.stdout, flush=False)

Печатает объекты в текстовый поток.

Именованный параметр sep задаёт разделитель между элементами. Если параметр не установлен или равен None используется пробел.

Именованный параметр end задаёт текст печатаемый к конце. Если параметр не установлен или равен None используется перевод строки.

Все не именованные аргументы преобразуются в строки функцией str():

print() без аргументов печатает end — перевод строки.

Аргумент file должен быть объектом с методом write(string). Если аргумент не задан или равен None то используется sys.stdout.

Обычно выходной поток, указанный в file, буферизуется. Если аргумент flush установлен в True, то после каждой записи данные записываются принудительно.

input([prompt])

Если задан аргумент prompt, он будет выведен в стандартный поток вывода без перевода на новую строку. Затем функция читает строку из входного потока, преобразовывает её в строку, удаляет завершающий перевод строки и возвращает результат. Если достигнут конц потока (EOF) выбрасывается исключение EOFError.

Ссылки

Встроенные функции Python для работы с коллекциями (sorted, filter, zip, reversed, len)

sorted()

Возвращает новый сортированный список (list) из элементов iterable.

Порядок элементов изменяется аргументом key. Переданная в key функция применяется к каждому элементу. Результат функции используется для определения порядка элементов:

Логический аргумент reverse задаёт обратную сортировку:

Описание других способов сортировки.

Читать далее Встроенные функции Python для работы с коллекциями (sorted, filter, zip, reversed, len)

Встроенные функции Python для работы с коллекциями (min, max, sum, all, any, enumerate)

max

  • max(iterable, *[, key, default])
  • max(arg1, arg2, *args[, key])

Функция возвращает максимальный элемент. Две версии функции отличаются аргументами: с итерируемым объектом и со списком аргументов.

Если коллекция пустая возникнет исключение

Именованный аргумент default используется чтобы избежать исключения. Функция max возвращает default только если коллекция пустая:

Порядок элементов изменяется аргументом key. Переданная в key функция применяется к каждому элементу. Результат функции используется для определения порядка элементов:

Читать далее Встроенные функции Python для работы с коллекциями (min, max, sum, all, any, enumerate)

Встроенные математические функции Python

Стандартные функции доступные без подключения модулей.

abs(x)

Возвращает модуль числа. Аргумент x может быть целым (int) или вещественным (float) числом.

Для комплексных чисел возвращает длину вектора изображающего комплексное число:

Если x определяет метод __abs__(), то abs(x) вернёт x.__abs__().

pow(base, exp[, mod])

Возвращает base в степени exp:

Допустима отрицательная и вещественная степень:

Если указан третий аргумент mod, функция вернёт остаток по модулю:

Читать далее Встроенные математические функции Python

Python. Наследование

Перевод параграфа 6.4 Inheritance из книги Intermediate Python.

Наследование — это механизм создания новых классов. Наследники специализируют или изменяют базовые классы добавляя в них новую функциональность. Python поддерживает множественное наследование как C++. Пример одиночного наследования в Python:

Читать далее Python. Наследование

Python. Абстрактные базовые классы

Перевод параграфа 6.7 Abstract Base Classes из книги Intermediate Python.

Чтобы классы реализовывали заданный набор методов в статически типизированных языках, таких как Java, используются интерфейсы и абстрактные классы.

Простая реализация такого контракта в Python — добавить в базовый класс методы по умолчанию, выбрасывающие исключение NotImplementedError. Такое решение неполное: наследники могут не переопределить все методы базового класса, а проблема обнаружится только во время выполнения программы.

Рассмотрим другую ситуацию — использование одного объекта для замещения другого. Заместитель перехватывает все вызовы и передаёт их в скрываемый объект. Заместитель реализует все нужные методы, но проверку типа через isinstance он не проходит, так как имеет тип отличный от замещаемого объекта.

В Python такие задачи решаются через абстрактные базовые классы, реализуемые модулем abc. Этот модуль определяет мета-класс и набор декораторов. Для определения абстрактного базового класса мы устанавливаем ABCMeta как мета-класс абстрактного класса и помечаем декораторами @abstractmethod и @abstractproperty методы и свойства которые должны быть реализованы в неабстрактных потомках.

Читать далее Python. Абстрактные базовые классы

Python. Статические и классовые методы

Перевод параграфа 6.5 Static and Class Methods из книги Intermediate Python.

По умолчанию методы определённые в классе работают с экземплярами класса. Для определения статических и классовых методов применяются декораторы @staticmethod и @classmethod.

Статичные методы

Статичные методы это обычные функции внутри пространства имён класса. Ссылка на статичный метод из класса возвращает функцию вместо несвязанного метода:

Декоратор @staticmethod используется для определения статического метода. Такой метод не требует аргумента self.

Читать далее Python. Статические и классовые методы