Решения — Урок 46 | Python Fundamentals

Решение задания 1. Сумма цифр числа

# solution_01_sum_digits.py
def sum_digits(n: int) -> int:
    """Возвращает сумму цифр неотрицательного целого числа."""
    n = abs(n)
    if n == 0:
        return 0
    return n % 10 + sum_digits(n // 10)


num = 43197
print(sum_digits(num))  # 24

Логика: на каждом шаге отрезаем последнюю цифру (% 10) и прибавляем её к сумме цифр оставшегося числа (// 10). Когда число становится равным 0, рекурсия останавливается.

Решение задания 2. Сумма вложенных чисел

# solution_02_sum_nested.py
from typing import Iterable


def sum_nested(numbers) -> int:
    """Суммирует все целые числа во вложенных списках."""
    if isinstance(numbers, int):
        return numbers
    if isinstance(numbers, Iterable) and not isinstance(numbers, (str, bytes)):
        return sum(sum_nested(item) for item in numbers)
    return 0


nested_numbers = [1, [2, 3], [4, [5, 6]], 7]
print(sum_nested(nested_numbers))  # 28

Логика: если элемент — целое число, возвращаем его. Если — итерируемая коллекция (но не строка), рекурсивно суммируем элементы. Строки исключаем, чтобы не разбивать их на символы.

Решение задания 3. Факториал с проверкой

# solution_03_factorial.py
def factorial(n: int) -> int:
    """Возвращает факториал неотрицательного целого числа."""
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(5))   # 120
print(factorial(0))   # 1
# factorial(-1)  # ValueError

Логика: guard clause сразу отклоняет отрицательные аргументы, базовый случай обрабатывает 0 и 1, рекурсивный случай сводит задачу к меньшему числу.

Решение задания 4. Бинарный поиск

# solution_04_binary_search.py
from typing import Optional


def binary_search(
    arr: list[int],
    target: int,
    left: int,
    right: int
) -> Optional[int]:
    """Ищет target в отсортированном списке arr. Возвращает индекс или None."""
    if left > right:
        return None
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    return binary_search(arr, target, left, mid - 1)


array = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(array, 5, 0, len(array) - 1))   # 2
print(binary_search(array, 13, 0, len(array) - 1))  # 6
print(binary_search(array, 8, 0, len(array) - 1))   # None

Логика: базовый случай — пустой диапазон (left > right). Иначе сравниваем target с серединой и рекурсивно ищем в нужной половине.

Решение задания 5. Переворот строки

# solution_05_reverse_string.py
def reverse_string(s: str) -> str:
    """Возвращает строку в обратном порядке."""
    if not s:
        return ""
    return s[-1] + reverse_string(s[:-1])


text = "hello"
print(reverse_string(text))  # olleh

Логика: базовый случай — пустая строка. Рекурсивный случай берёт последний символ и добавляет к перевёрнутому остатку.

Решение задания 6. Подсчёт слов

# solution_06_count_word.py
from typing import Iterable


def count_word(nested_sentences, word: str) -> int:
    """Считает вхождения слова в строках и вложенных списках строк."""
    if isinstance(nested_sentences, str):
        return nested_sentences.split().count(word)
    if isinstance(nested_sentences, Iterable) and not isinstance(nested_sentences, (str, bytes)):
        return sum(count_word(item, word) for item in nested_sentences)
    return 0


nested_sentences = [
    ["Python is great", "I love Python"],
    ["Python is powerful", ["Python is everywhere", "Learn Python"]],
    "Coding in Python is fun"
]
word = "Python"
print("Количество вхождений:", count_word(nested_sentences, word))  # 6

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

Решение задания 7. Собственный аналог deepcopy

# solution_07_deep_copy.py
def deep_copy(data):
    """Рекурсивно копирует списки, кортежи, множества и словари."""
    if isinstance(data, list):
        return [deep_copy(item) for item in data]
    if isinstance(data, dict):
        return {key: deep_copy(value) for key, value in data.items()}
    if isinstance(data, set):
        return {deep_copy(item) for item in data}
    if isinstance(data, tuple):
        return tuple(deep_copy(item) for item in data)
    return data


original_data = [
    [1, 2, 3],
    (4, [5, 6], {7, 8}),
    {"a": 9, "b": [10, 11]},
    "Hello",
    [12, (13, 14)],
    15.5,
    5
]
copied_data = deep_copy(original_data)
original_data[1][1][0] = 0

print(f"Исходный: {original_data}")
print(f"Копия:    {copied_data}")

Логика: для каждого изменяемого контейнера создаём новый объект и рекурсивно копируем содержимое. Неизменяемые скаляры (числа, строки) возвращаем как есть — их нельзя изменить, поэтому копия не нужна.

Решение задания 8. Числа Фибоначчи с мемоизацией

# solution_08_fibonacci.py
from functools import lru_cache


@lru_cache(maxsize=None)
def fibonacci(n: int) -> int:
    """Возвращает n-е число Фибоначчи с мемоизацией."""
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


print(fibonacci(10))   # 55
print(fibonacci(100))  # 354224848179261915075

Логика: наивная рекурсия для чисел Фибоначчи имеет экспоненциальную сложность. Декоратор @lru_cache запоминает уже вычисленные значения и превращает алгоритм в линейный по числу уникальных вызовов.

✅ Решения заданий

⚡ Решения в двух словах