Python | Way23

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

Задача

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

Решение

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

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

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

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

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

Сложность

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

Код

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

def fib_mod(n, m):
    seq_pisano = find_pisano(m)
    return seq_pisano[n % len(seq_pisano)]

def find_pisano(m):
    pisano = [0, 1]
    n0 = 0
    n1 = 1

    for _ in range(m * 6):
        n0, n1 = n1, (n0 + n1) % m
        pisano.append(n1)

        if pisano[-1] == 1 and pisano[-2] == 0:
            break

    return pisano[:-2]

def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

n, m = (int(x) for x in input().split())
f = gcd(n, m)
r = fib_mod(f, 10)
print(r)

def fib_mod(n, m):

seq_pisano = find_pisano(m)

return seq_pisano[n % len(seq_pisano)]

def find_pisano(m):

pisano = [0, 1]

n0 = 0

n1 = 1

for _ in range(m * 6):

n0, n1 = n1, (n0 + n1) % m

pisano.append(n1)

if pisano[-1] == 1 and pisano[-2] == 0:

break

return pisano[:-2]

def gcd(a, b):

while a != 0:

a, b = b % a, a

return b

n, m = (int(x) for x in input().split())

f = gcd(n, m)

r = fib_mod(f, 10)

print(r)

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(). Функция вернёт новый сортированный список:

>>>
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

>>>

>>> sorted([5, 2, 3, 1, 4])

[1, 2, 3, 4, 5]

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

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
>>> a
[1, 2, 3, 4, 5]

>>> a = [5, 2, 3, 1, 4]

>>> a.sort()

>>> a

[1, 2, 3, 4, 5]

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

>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'})
[1, 2, 3, 4, 5]

1 2	>>> sorted({1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'}) [1, 2, 3, 4, 5]

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

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

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

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

print(1, 'hi', True)
# 1 hi True

1 2	print(1, 'hi', True) # 1 hi True

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

print(1, 2, 3, sep=', ')
# 1, 2, 3

1 2	print(1, 2, 3, sep=', ') # 1, 2, 3

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

print(1, 2, 3, sep=', ', end=';\n')
# 1, 2, 3;

1 2	print(1, 2, 3, sep=', ', end=';\n') # 1, 2, 3;

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

class MyNumber():
    def __init__(self, num):
        self.num = num

    def __str__(self):
        return 'even' if self.num % 2 == 0 else 'odd'

x = MyNumber(10)
print(x)  # even

class MyNumber():

def __init__(self, num):

self.num = num

def __str__(self):

return 'even' if self.num % 2 == 0 else 'odd'

x = MyNumber(10)

print(x) # even

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

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

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

input([prompt])

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

>>>
>>> s = input('--> ')  
--> Monty Python's Flying Circus
>>> s  
"Monty Python's Flying Circus"

>>>

>>> s = input('--> ')

--> Monty Python's Flying Circus

>>> s

"Monty Python's Flying Circus"

Ссылки

Built-in Functions

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

sorted()

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

print(sorted([5, 6, 2, 0])) # [0, 2, 5, 6]

1	print(sorted([5, 6, 2, 0])) # [0, 2, 5, 6]

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

def neg(n):
    return -n

print(sorted([5, 6, 2, 0], key = neg)) # [6, 5, 2, 0]

def neg(n):

return -n

print(sorted([5, 6, 2, 0], key = neg)) # [6, 5, 2, 0]

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

print(sorted([5, 6, 2, 0], reverse = True)) # [6, 5, 2, 0]

1	print(sorted([5, 6, 2, 0], reverse = True)) # [6, 5, 2, 0]

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

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

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

max

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

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

print(max([3, 5, 8, 2])) # 8
print(max(3, 5, 8, 2)) # 8

1 2	print(max([3, 5, 8, 2])) # 8 print(max(3, 5, 8, 2)) # 8

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

print(max([], )) # ValueError

1	print(max([], )) # ValueError

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

print(max([], default=0)) # 0
print(max([2, 3], default=5)) # 3

1 2	print(max([], default=0)) # 0 print(max([2, 3], default=5)) # 3

def neg(n):
    return -n

print(max([3, 5, 8, 2], key=neg))  # 2

def neg(n):

return -n

print(max([3, 5, 8, 2], key=neg)) # 2

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

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

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

abs(x)

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

a = -1
b = -2.4
c = 5
print(abs(a)) # 1
print(abs(b)) # 2.4
print(abs(c)) # 5

a = -1

b = -2.4

c = 5

print(abs(a)) # 1

print(abs(b)) # 2.4

print(abs(c)) # 5

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

c = complex(3, 4)
print(abs(c)) ## 5.0

1 2	c = complex(3, 4) print(abs(c)) ## 5.0

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

class MyNumber():
    def __init__(self, num):
        self.num = num

    def __abs__(self):
        return -abs(self.num)

x = MyNumber(10)
print(abs(x)) # -10

class MyNumber():

def __init__(self, num):

self.num = num

def __abs__(self):

return -abs(self.num)

x = MyNumber(10)

print(abs(x)) # -10

pow(base, exp[, mod])

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

print(pow(2, 10)) # 1024
print(2 ** 10)    # 1024

1 2	print(pow(2, 10)) # 1024 print(2 ** 10) # 1024

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

print(pow(2, -2)) # 0.25
print(pow(64, 0.5)) # 8.0

1 2	print(pow(2, -2)) # 0.25 print(pow(64, 0.5)) # 8.0

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

print(pow(2, 10, 100))  # 24
print(pow(2, 10) % 100) # 24

1 2	print(pow(2, 10, 100)) # 24 print(pow(2, 10) % 100) # 24

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

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

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

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

class Account:
    """base class for representing user accounts"""
    num_accounts = 0

    def __init__(self, name, balance):
        self.name = name
        self.balance = balance
        Account.num_accounts += 1

    def del_account(self):
        Account.num_accounts -= 1

    def __getattr__(self, name):
        """handle attribute reference for non-existent attribute"""
        return "Hey I dont see any attribute called {}".format(name)

    def deposit(self, amt):
        self.balance = self.balance + amt

    def withdraw(self, amt):
        self.balance = self.balance - amt

    def inquiry(self):
        return "Name={}, balance={}".format(self.name, self.balance)

class SavingsAccount(Account):

    def __init__(self, name, balance, rate):
        super().__init__(name, balance)
        self.rate = rate

    def __repr__(self):
        return "SavingsAccount({}, {}, {})".format(self.name, self.balance, self.rate)

class Account:

"""base class for representing user accounts"""

num_accounts = 0

def __init__(self, name, balance):

self.name = name

self.balance = balance

Account.num_accounts += 1

def del_account(self):

Account.num_accounts -= 1

def __getattr__(self, name):

"""handle attribute reference for non-existent attribute"""

return "Hey I dont see any attribute called {}".format(name)

def deposit(self, amt):

self.balance = self.balance + amt

def withdraw(self, amt):

self.balance = self.balance - amt

def inquiry(self):

return "Name={}, balance={}".format(self.name, self.balance)

class SavingsAccount(Account):

def __init__(self, name, balance, rate):

super().__init__(name, balance)

self.rate = rate

def __repr__(self):

return "SavingsAccount({}, {}, {})".format(self.name, self.balance, self.rate)

>>>acct = SavingsAccount("Obi", 10, 1)
>>>repr(acct)
SavingsAccount(Obi, 10, 1)

>>>acct = SavingsAccount("Obi", 10, 1)

>>>repr(acct)

SavingsAccount(Obi, 10, 1)

Читать далее 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.

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

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

class Account(object):
    num_accounts = 0

    def __init__(self, name, balance):
        self.name = name
        self.balance = balance
        Account.num_accounts += 1

    def del_account(self):
        Account.num_accounts -= 1

    def deposit(self, amt):
        self.balance = self.balance + amt

    def withdraw(self, amt):
        self.balance = self.balance - amt

    def inquiry(self):
        return "Name={}, balance={}".format(self.name, self.balance)

    @staticmethod
    def static_test_method():
        return "Current Account"

class Account(object):