Рекурсивні алгоритми

2.1 Обхід дерева файлів.

Давай розглянемо рекурсивний алгоритм для обходу дерева файлів. Алгоритм буде обходити каталог і всі його підкаталоги, виводячи список усіх файлів та папок.

import os

def list_files_recursive(directory, indent=0):
    # Отримуємо список усіх файлів та папок в поточному каталозі
    items = os.listdir(directory)
                
    for item in items:
        # Створюємо повний шлях до файлу або папки
        path = os.path.join(directory, item)
                    
    # Виводимо з відступом для кращого сприйняття структури
    print(' ' * indent + item)
                    
    # Якщо це папка, рекурсивно обходимо її вміст
    if os.path.isdir(path):
        list_files_recursive(path, indent + 4)
            
# Приклад використання
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

        

Як це працює?

1. Функція list_files_recursive(directory, indent=0):
   • directory — поточний каталог, вміст якого ми хочемо вивести.
   • indent — поточний рівень відступу, щоб показати вкладеність файлів та папок.
2. Отримуємо список усіх файлів та папок у поточному каталозі за допомогою os.listdir(directory).
3. Проходимося по кожному елементу у списку items.
4. Створюємо повний шлях до елементу за допомогою os.path.join(directory, item).
5. Виводимо ім'я елементу з відступом, який збільшується на 4 пробіли для кожного рівня вкладеності.
6. Перевіряємо, чи є елемент папкою за допомогою os.path.isdir(path). Якщо так, рекурсивно викликаємо list_files_recursive(path, indent + 4) для обходу її вмісту.

Приклад виводу:

Припустимо, у нас є наступна структура каталогів:

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

При виконанні функції list_files_recursive(root_directory) ми отримаємо наступний вивід:

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

Цей алгоритм рекурсивно обходить дерево каталогів, виводячи всі файли та папки з урахуванням їх вкладеності.

2.2 Ханойські вежі

Задача «Ханойські вежі»

Ханойські вежі — це класична рекурсивна задача, яка включає переміщення дисків з одного стрижня на інший за допомогою допоміжного стрижня.

Правила:

1. Можна переміщати лише один диск за раз.
2. Диск можна помістити лише на порожній стрижень або на диск більшого розміру.
3. Потрібно перемістити всі диски з одного стрижня на інший, використовуючи допоміжний стрижень.

Ось рекурсивний алгоритм для вирішення цієї задачі:

Алгоритм Ханойських веж вирішує задачу наступним чином:

1. Перемістити n - 1 дисків з початкового стрижня на допоміжний, використовуючи цільовий стрижень.
2. Перемістити залишений диск з початкового стрижня на цільовий.
3. Перемістити n - 1 дисків з допоміжного стрижня на цільовий, використовуючи початковий стрижень.

Приклад на Python

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Перемістити диск 1 з {source} на {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Перемістити диск {n} з {source} на {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Приклад використання:
n = 3  # Кількість дисків
hanoi_tower(n, 'A', 'C', 'B')
        
        

Як це працює?

Базовий випадок:

Якщо є лише один диск (n == 1), то його можна просто перемістити з початкового стрижня на цільовий.

if n == 1:
    print(f"Перемістити диск 1 з {source} на {target}")
    return
        

Рекурсивний випадок:

Крок 1. Перемістити n-1 дисків з початкового стрижня на допоміжний, використовуючи цільовий стрижень.

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

Крок 2. Перемістити диск n з початкового стрижня на цільовий.

print(f"Перемістити диск {n} з {source} на {target}")
        

Крок 3. Перемістити n - 1 дисків з допоміжного стрижня на цільовий, використовуючи початковий стрижень.

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

Приклад виводу:

Для трьох дисків (n = 3) на стрижнях A, B і C, програма виведе:

Перемістити диск 1 з A на C
Перемістити диск 2 з A на B
Перемістити диск 1 з C на B
Перемістити диск 3 з A на C
Перемістити диск 1 з B на A
Перемістити диск 2 з B на C
Перемістити диск 1 з A на C
        

2.3 Сніжинка Коха.

Малювання сніжинки з використанням рекурсії — це цікава задача, яка часто застосовується для вивчення фракталів. Один з простих способів намалювати сніжинку — це використати криву Коха, яка являє собою фрактальну криву.

Алгоритм для малювання сніжинки Коха

Крива Коха будується наступним чином:

• Починаємо з прямої лінії.
• Ділимо кожен відрізок на три частини та замінюємо центральну частину невеликою кривою, що нагадує «кутик».
• Повторюємо цей процес рекурсивно для кожного відрізка.

Покрокова інструкція

• Початок: Намалюйте початковий відрізок.
• Розділення: Розділіть кожен відрізок на три частини.
• Замініть центральну частину: На центральній частині намалюйте «кутик», що складається з двох ліній, які утворюють кут 60 градусів.
• Повторіть процес: Продовжуйте цей процес для кожного відрізка.

Приклад на Python з використанням бібліотеки 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)
            
# Налаштування екрану
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Налаштування черепашки
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Малюємо сніжинку
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Завершення малювання
turtle.hideturtle()
turtle.done()
            
        

Як це працює?

1. Функція draw_koch_curve(t, length, depth):

• t: черепашка, яка малює.
• length: довжина відрізка.
• depth: глибина рекурсії, що визначає рівень деталізації.

2. Базовий випадок:

Якщо depth дорівнює 0, черепашка малює прямий відрізок.

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

3. Рекурсивний випадок:

Розділіть відрізок на три частини, і застосуйте draw_koch_curve рекурсивно до кожної частини, додаючи повороти.

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. Функція draw_snowflake(t, length, depth):

Малює три криві Коха, з'єднані в одну сніжинку.

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

        

Як запустити код?

• Переконайтеся, що у вас встановлена бібліотека Turtle (pip install PythonTurtle).
• Скопіюйте і вставте код у файл .py і запустіть його. Ви побачите малювання сніжинки на екрані.

Цей алгоритм дозволяє візуалізувати фрактальну структуру сніжинки з використанням простих принципів рекурсії та геометричних побудов.