Parę implementacji matematycznych w Python #1.

Posted in 14 marca, 2020 by

Categories: Matematyka Programowanie Python

Tags: , , , ,

Reading Time: 4 minutes

W tym artykule chciałbym przedstawić parę zagadnień matematycznych które można zaimplementować w języku Python. Są to najprostsze i najbardziej powszechne problemy matematyczne takie jak dodawanie dwóch obiektów do siebie czy znajdowanie sumy liczb ciągu Fibonacciego.

Ciąg Fibonacciego w Python.

Ciągi w matematyce występują w paru postaciach. Mamy ciąg arytmetyczny którego elementy mają stałą różnicę oraz ciąg geometryczny którego elementy mają stały mnożnik. Są to ciągi stałe, przewidywalne, trochę nudne w porównaniu z ciągiem Fibonacciego.

Ciąg ten charakteryzuje się tym że każda kolejna cyfra tego ciągu jest wynikiem sumy dwóch poprzednich elementów. Co ciekawe i najbardziej charakterystyczne w tym ciągu jest to że możemy zaobserwować jego występowanie w przyrodzie a także muzyce czy architekturze. Patrząc na budowę ananasa czy szyszki, obserwując budowę muszli możemy dostrzec ciąg Fibonacciego. Niektórzy badacze dopatrują się występowania tego ciągu w budowie utworów muzycznych.

Teraz zaimplementujemy w języku Python funkcję obliczającą n-ty wyraz tego ciągu.

def fibonacci_n(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci_n(n - 2) + fibonacci_n(n - 1)

print(fibonacci_n(10))

Funkcja dla n=10, czyli dla 10 wyrazu ciągu Fibonacciego zwraca liczbę 55 co jest poprawne: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Czyli 21+34 = 55.

Teraz zaimplementujemy w języku Python sumę n-tych wyrazów ciągu Fibonacciego. Użyjemy do tego poprzedniej funkcji fibonacci_n.

def fibonacci_sum(n):
    suma = 0
    for i in range(n):
        suma += fibonacci_n(i)
    return suma

print(fibonacci_sum(6))

Ta funkcja dla n=6 daje nam sumę równą 12. Czyli 0 + 1 + 1 + 2 + 3 + 5 = 12.

Oczywiście nie sprawdzamy czy n nie jest ujemne, jednak jest to zmiana bardziej kosmetyczna.

Liczba pierwsza w Python.

W tym podrozdziale zaimplementujemy funkcję mówiącą nam czy dana liczba jest liczbą pierwszą. Liczba pierwsza to taka która ma tylko dwa dzielniki, 1 oraz samą siebie.

def is_prime(n):
    prime = True
    for i in range(n):
        if i == 0 or i == 1:
            continue
        if n % i == 0:
            prime = False
    return prime

print(is_prime(149))
print(is_prime(337))
print(is_prime(120))
print(is_prime(1024))

Funkcja dla liczb pierwszych 149 oraz 337 zwróci wartość True natomiast dla liczb 120 oraz 1024 zwraca wartość False, gdyż 120 oraz 1024 ma także inne dzielniki jak np. 2.

Możemy udoskonalić naszą funkcję zmniejszając ilość porównań dzielenia modulo o połowę. Wiemy że jeśli np. liczba 13 nie dzieli się przez 2, 3, 4, 5, oraz 6 dalsze sprawdzanie nie ma sensu gdyż większy dzielnik pomnożony przez 2 da nam liczbę większą od sprawdzanej liczby, np. 7 * 2 = 14. Ulepszona funkcja wyglądała by tak:

def is_prime(n):
    prime = True
    for i in range(int(n/2)):
        if i == 0 or i == 1:
            continue
    if n % i == 0:
            prime = False
    return prime

Liczbę n musimy konwertować na typ int gdyż jeśli tego nie zrobimy to kompilator zgłosi nam TypeError mówiący o tym że nie możemy iterować po typie float. Dla liczby 337 podzielonej przez 2 otrzymamy 168.5. Natomiast jeśli castujemy liczbę 337/2 na typ int otrzymamy liczbę 168.

Ostatnie ulepszenie tej funkcji polega na jeszcze większym zmniejszeniu złożoności obliczeniowej poprzez zastosowanie pierwiastkowania. Wiemy że żeby obalić tezę że liczba jest liczbą pierwszą wystarczy znaleźć tylko 1 taką liczbę która która da nam wynik z porównania modulo równy 0.

Na przykład wyciągając pierwiastek z liczby 16 wynikiem będzie 4 i wiemy że 4 razy 4 da nam liczbę 16 zatem dalsze sprawdzanie nie będzie miało już sensu. Sprawdzenie do liczby 4, czyli pierwiastka z liczby 16 będzie optymalnym rozwiązaniem.

Poprawiona funkcja będzie teraz wyglądała w ten sposób:

import math

def is_prime(n):
    prime = True
    for i in range(int(math.sqrt(n))):
        if i == 0 or i == 1:
            continue
        if n % i == 0:
            prime = False
    return prime

Dodawanie dwóch punktów do siebie w Python.

Teraz stworzymy klasę która będzie reprezentacją punktu, a potem dodamy do siebie dla obiekty czyli punkty i przedstawimy wynik:

Klasa Point wygląda w ten sposób:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __repr__(self):
        return f"Point: {self.x}, {self.y}"

    def __add__(self, other):
        x = self.x + other.x
        y = self.y + other.y
        return Point(x, y)

Korzystamy tutaj z metody magicznej (specjalnej) __add__ która wywołuje się wtedy kiedy wykonujemy operację dodawania oraz z metody __repr__ która wywoła się gdy wyświetlamy obiekt za pomocą metody print. Teraz dodamy do siebie dwa stworzone obiekty, czyli punkty:

point_1 = Point(15, 15)
point_2 = Point(35, 20)
point_3 = point_1 + point_2
print(f'__add__: \t {point_3}')

Wynik przedstawiony jest na poniższym screenshocie:

Zostały do siebie dodane pola x oraz y obu obiektów tworząc nowy obiekt z nowymi wartościami x oraz y.

Podsumowanie.

W tym artykule przybliżyłem pewne implementacje zagadnień matematycznych w Python. Podejrzewam że tego typu artykułów pojawi się więcej na moim blogu.

Jeśli spodobał ci się ten artykuł podziel się swoją opinią w komentarzu. Bardzo chcętnie przeczytam co masz do dodania. Możesz też sharować ten artykuł na social media jeśli uważasz że warto to zrobić.

Polecam też dwa bardzo fajne blogi o języku Python które obecnie czytam. Blog programisty Mateusza Mazurek oraz blog programisty Rafała Kraik. Jest tam bardzo dużo materiałów o języku Python. Zachęcam do czytania.

Serdecznie pozdrawiam.


One thought on “Parę implementacji matematycznych w Python #1.”

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

7 + 13 =