Algorytmika i Programowanie w Python dla Początkujących

Systemy liczbowe i metoda połowienia

System dwójkowy używa tylko cyfr 0 i 1 do zapisu liczb. Żeby zamienić liczbę z systemu dziesiętnego na dwójkowy, dzielimy ją przez 2 aż do uzyskania 0, zapisując reszty z dzielenia od dołu do góry. Na przykład 29₁₀ = 11101₂.

Odwrotna konwersja (z dwójkowego na dziesiętny) jest równie prosta. Każda pozycja w liczbie dwójkowej odpowiada kolejnym potęgom liczby 2. Na przykład 10001001₂ = 128 + 8 + 1 = 137₁₀.

Metoda połowienia to algorytm służący do znajdowania miejsca zerowego funkcji w określonym przedziale (a,b). Polega na dzieleniu przedziału na połowy i sprawdzaniu, w której części znajduje się miejsce zerowe. Algorytm powtarzamy, aż osiągniemy żądaną dokładność E.

💡 Wskazówka: Metodę połowienia możesz wykorzystać nie tylko do znajdowania miejsc zerowych, ale również do obliczania pierwiastków liczb!

Fraktale i programowanie żółwia

Fraktale to fascynujące obiekty matematyczne, które powstają przez nieskończone powtarzanie tej samej operacji. Ich charakterystyczną cechą jest samopodobieństwo – mały fragment ma taki sam kształt jak całość. Popularne przykłady to trójkąt Sierpińskiego, krzywa Kocha czy smok Heighwaya.

Do rysowania fraktali świetnie nadaje się moduł turtle w Pythonie. Podstawowe komendy to: fd(n) (do przodu), bk(n) (do tyłu), rt(alfa) (skręt w prawo), lt(alfa) (skręt w lewo), pu() (podniesienie pisaka) i pd() (opuszczenie pisaka).

Rekurencja to potężna technika programowania, polegająca na wywoływaniu funkcji przez samą siebie. Rozwiązujemy problem dzieląc go na mniejsze, podobne problemy, aż dojdziemy do przypadku podstawowego. Rekurencja daje zwięzły kod, ale może być nieefektywna czasowo i pamięciowo.

⚠️ Uważaj: Przy pisaniu funkcji rekurencyjnych zawsze pamiętaj o warunku końcowym, który zatrzyma wywoływanie - w przeciwnym razie twój program nigdy się nie zakończy!

Rekurencja w praktyce

Rekurencja świetnie sprawdza się przy obliczaniu silni. Na przykład 4! możemy rozłożyć na 4·3!, a 3! na 3·2! itd., aż dojdziemy do przypadku podstawowego 0! = 1. Następnie obliczamy wszystkie wartości wstecz.

Podobnie działa rekurencyjne obliczanie potęg. Na przykład 2⁴ = 2³·2, a 2³ = 2²·2 itd., aż do 2⁰ = 1. Ten schemat pozwala na łatwe zaimplementowanie funkcji potęgującej.

Ciąg Fibonacciego to klasyczny przykład wykorzystania rekurencji. Definiujemy go jako:

• F(1) = 1, F(2) = 1 (przypadki podstawowe)
• F$n$ = F$n-1$ + F$n-2$ dla n > 2

🔍 Ciekawostka: Ciąg Fibonacciego występuje w naturze w wielu miejscach - od układu liści na łodydze po spirale w muszlach czy układ nasion słonecznika!

Implementacje algorytmów w Pythonie

Funkcja konwertująca liczbę z systemu dwójkowego na dziesiętny mnoży każdą cyfrę przez odpowiednią potęgę dwójki i sumuje wyniki:

def na10(dana):
    pom = 0
    for i in range(len(dana)):
        x = int(dana[-i-1])
        pom = pom + x * 2**i
    return pom

Konwersja z systemu dziesiętnego na dwójkowy wykorzystuje dzielenie z resztą:

def na2(liczba):
    if liczba == 0:
        return 0
    pom = ""
    while liczba > 0:
        pom = str(liczba % 2) + pom
        liczba = liczba // 2
    return pom

Do rysowania drzewa binarnego używamy rekurencji i modułu turtle. Funkcja rysuje drzewo o określonej wysokości i liczbie poziomów:

💻 Praktyka czyni mistrza: Spróbuj zmodyfikować kod drzewa binarnego, zmieniając kąty rozgałęzień lub dodając kolory - otrzymasz zupełnie nowe wzory!

Krzywa Kocha i zastosowania praktyczne

Krzywa Kocha to popularny fraktal, który możemy narysować rekurencyjnie:

def koch(bok, n):
    if n == 0:
        fd(bok)
        return
    koch(bok/3, n-1)
    lt(60)
    koch(bok/3, n-1)
    rt(120)
    koch(bok/3, n-1)
    lt(60)
    koch(bok/3, n-1)

Z krzywej Kocha możemy stworzyć płatek Kocha, rysując trzy krzywe Kocha połączone pod kątem 120 stopni:

def platek(n):
    bok = 300
    lt(60)
    for i in range(3):
        koch(bok, n)
        rt(120)
    rt(60)

Praktycznym zastosowaniem metody połowienia jest funkcja znajdująca miejsce zerowe funkcji z zadaną dokładnością:

def miejsce_zerowe(eps):
    a = 0
    b = 100
    while abs(b-a) > eps:
        c = (a+b)/2
        if f(c) > 0:
            b = c
        else:
            a = c
    return c

🎯 Zastosowanie: Metoda połowienia, chociaż nie jest najszybsza, jest bardzo stabilna i niezawodna - dlatego używa się jej w wielu praktycznych sytuacjach, od znajdowania pierwiastków po optymalizację parametrów.