Algorytmy rekurencyjne

2.1 Przechodzenie drzewa plików

Zobaczmy rekurencyjny algorytm do przechodzenia drzewa plików. Algorytm będzie przeszukiwał katalog i wszystkie jego podkatalogi, wypisując listę wszystkich plików i folderów.

import os

def list_files_recursive(directory, indent=0):
    # Pobieramy listę wszystkich plików i folderów w bieżącym katalogu
    items = os.listdir(directory)
                
    for item in items:
        # Tworzymy pełną ścieżkę do pliku lub folderu
        path = os.path.join(directory, item)
                    
        # Wyświetlamy z wcięciem dla lepszego zrozumienia struktury
        print(' ' * indent + item)
                    
        # Jeśli to folder, rekurencyjnie przeszukujemy jego zawartość
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# Przykład użycia
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

Jak to działa?

1. Funkcja list_files_recursive(directory, indent=0):
   • directory — bieżący katalog, którego zawartość chcemy wyświetlić.
   • indent — bieżący poziom wcięcia, aby pokazać zagnieżdżenie plików i folderów.
2. Pobieramy listę wszystkich plików i folderów w bieżącym katalogu za pomocą os.listdir(directory).
3. Przechodzimy przez każdy element na liście items.
4. Tworzymy pełną ścieżkę do elementu za pomocą os.path.join(directory, item).
5. Wyświetlamy nazwę elementu z wcięciem, które zwiększa się o 4 spacje dla każdego poziomu zagnieżdżenia.
6. Sprawdzamy, czy element jest folderem za pomocą os.path.isdir(path). Jeśli tak, rekurencyjnie wywołujemy list_files_recursive(path, indent + 4) dla przeszukania jego zawartości.

Przykład wyniku:

Załóżmy, że mamy następującą strukturę katalogów:

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

Przy wykonaniu funkcji list_files_recursive(root_directory) otrzymamy następujący wynik:

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

Ten algorytm rekurencyjnie przeszukuje drzewo katalogów, wyświetlając wszystkie pliki i foldery z uwzględnieniem ich zagnieżdżenia.

2.2 Wieże Hanoi

Zadanie „Wieże Hanoi”

Wieże Hanoi to klasyczne zadanie rekurencyjne, które polega na przenoszeniu dysków z jednego pręta na drugi za pomocą pręta pomocniczego.

Zasady:

1. Można przenosić tylko jeden dysk na raz.
2. Dysk można umieścić tylko na pustym pręcie lub na dysku o większym rozmiarze.
3. Należy przenieść wszystkie dyski z jednego pręta na drugi, używając pręta pomocniczego.

Oto rekurencyjny algorytm do rozwiązania tego zadania:

Algorytm Wież Hanoi rozwiązuje zadanie w następujący sposób:

1. Przenieś n - 1 dysków z pręta początkowego na pomocniczy, używając pręta docelowego.
2. Przenieś pozostały dysk z pręta początkowego na docelowy.
3. Przenieś n - 1 dysków z pręta pomocniczego na docelowy, używając pręta początkowego.

Przykład w Pythonie

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Przenieś dysk 1 z {source} na {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Przenieś dysk {n} z {source} na {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Przykład użycia:
n = 3  # Liczba dysków
hanoi_tower(n, 'A', 'C', 'B')
        

Jak to działa?

Przypadek podstawowy:

Jeśli jest tylko jeden dysk (n == 1), można go po prostu przenieść z pręta początkowego na docelowy.

if n == 1:
    print(f"Przenieś dysk 1 z {source} na {target}")
    return

Przypadek rekurencyjny:

Krok 1. Przenieś n-1 dysków z pręta początkowego na pomocniczy, używając pręta docelowego.

hanoi_tower(n - 1, source, auxiliary, target)

Krok 2. Przenieś dysk n z pręta początkowego na docelowy.

print(f"Przenieś dysk {n} z {source} na {target}")

Krok 3. Przenieś n - 1 dysków z pręta pomocniczego na docelowy, używając pręta początkowego.

hanoi_tower(n - 1, auxiliary, target, source)

Przykład wyniku:

Dla trzech dysków (n = 3) na prętach A, B i C, program wyświetli:

Przenieś dysk 1 z A na C
Przenieś dysk 2 z A na B
Przenieś dysk 1 z C na B
Przenieś dysk 3 z A na C
Przenieś dysk 1 z B na A
Przenieś dysk 2 z B na C
Przenieś dysk 1 z A na C

2.3 Płatek śniegu Kocha

Rysowanie płatka śniegu z użyciem rekurencji to ciekawe zadanie, które często wykorzystuje się do nauki fraktali. Jednym z prostych sposobów narysowania płatka śniegu jest użycie krzywej Kocha, która jest fraktalną krzywą.

Algorytm rysowania płatka śniegu Kocha

Krzywa Kocha jest konstruowana w następujący sposób:

• Zaczynamy od prostej linii.
• Dzielimy każdy odcinek na trzy części i zastępujemy środkową część małą krzywą, przypominającą „kąt”.
• Powtarzamy ten proces rekurencyjnie dla każdego odcinka.

Instrukcja krok po kroku

• Początek: Narysuj początkowy odcinek.
• Podział: Podziel każdy odcinek na trzy części.
• Zamień środkową część: Na środkowej części narysuj „kąt”, składający się z dwóch linii, które tworzą kąt 60 stopni.
• Powtórz proces: Kontynuuj ten proces dla każdego odcinka.

Przykład w Pythonie z użyciem biblioteki Turtle

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# Konfiguracja ekranu
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Konfiguracja żółwia
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Rysujemy płatek śniegu
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Zakończenie rysowania
turtle.done()
            

Jak to działa?

1. Funkcja draw_koch_curve(t, length, depth):

• t: żółw, który rysuje.
• length: długość odcinka.
• depth: głębokość rekurencji, określająca poziom szczegółowości.

2. Przypadek podstawowy:

Jeśli depth jest równe 0, żółw rysuje prosty odcinek.

if depth == 0:
    t.forward(length)
        

3. Przypadek rekurencyjny:

Podziel odcinek na trzy części i zastosuj draw_koch_curve rekurencyjnie do każdej części, dodając obroty.

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. Funkcja draw_snowflake(t, length, depth):

Rysuje trzy krzywe Kocha, połączone w jeden płatek śniegu.

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

Jak uruchomić kod?

• Upewnij się, że masz zainstalowaną bibliotekę Turtle (pip install PythonTurtle).
• Skopiuj i wklej kod do pliku .py i uruchom go. Zobaczysz rysowanie płatka śniegu na ekranie.

Ten algorytm pozwala wizualizować fraktalną strukturę płatka śniegu za pomocą prostych zasad rekurencji i konstrukcji geometrycznych.