Задания для самостоятельного выполнения
- Сложность:
- Rare
- Напишите две функции для решения задач своего варианта - с использованием рекурсии и без.
- Оформите отчёт в
README.md
. Отчёт должен содержать:- Условия задач
- Описание проделанной работы
- Скриншоты результатов
- Ссылки на используемые материалы
- Сложность:
- Medium
- Напишите для своих функций тесты с помощью pytest
- Сложность:
- Well-done
- Повысьте производительность своих функций минимум в 2 раза относительно исходных вариатов решения
Требования и ограничения
Ни используйте глобальные переменные и прочие средства хранения состояния между вызовами.
Для справки
- Recursion in Programming - Full Course - freeCodeCamp.org
- 🐍 Самоучитель по Python для начинающих. Часть 13: Рекурсивные функции - proglib.io
- Как работает рекурсия – объяснение в блок-схемах и видео - Хабр
Варианты заданий
- Функция для подсчёта числа элементов в списках, включая вложенные списки:
>>> count([]) 0 >>> count([1, 2, 3]) 3 >>> count(["x", "y", ["z"]]) 4 >>> count([1, 2, [3, 4, [5]]]) 7
- Функция для расчёта \( x_i = \frac{(i-1)x_{i-1}}{3} + \frac{(i-2)x_{i-2}}{4} \). \( x_1 = 1, x_2 = -\frac{1}{8} \).
- Функция для расчёта суммы вложенных списков.
>>> sum_nested([1, [2, [3, 4, [5]]]]) 15
- Функция для расчёта \( a_k = \frac{1}{2} (\sqrt{b_{k-1}} + \frac{1}{2}\sqrt{a_{k-1}}) \). \( a_1 = b_1 = 1 \).
- Функция для распаковки списка, содержащего другие объекты (
int
,str
,list
,tuple
,dict
,set
) произвольной вложенности.
>>> unpack([None, [1, ({2, 3}, {'foo': 'bar'})]]) [None, 1, 2, 3, 'foo', 'bar']
- Функция для расчёта \( w_i = w_{i-1} w_{i-2} \frac{(i-1)^2}{(i+1)^3} \). \( w_1 = 0.3, w_2 = -1.5 \).
- Функция для распаковки списка, содержащего другие объекты (
- Функция для преобразования вложенных списков в строку:
>>> to_str([1, [2, [3, [4, [5]]]]]) '1 -> 2 -> 3 -> 4 -> 5 -> None'
- Функция для расчёта \( a_i = a_{i-2} + \frac{a_{i-1}}{2^{i-1}} \). \( a_0 = a_1 = 1 \).
- Функция, которая разделяет список на n частей.
>>> split([1,2,3,4,5], 2) [[1, 3, 5], [2, 4]] >>> split([1,2,3,4,5], 3) [[1, 4], [2, 5], [3]]
- Функция для расчёта \( v_i = \frac{i + 1}{i^2 + 1} v_{i-1} - v_{i-2}v_{i-3} \). \( v_1 = v_2 = 0, v_3 = 1.5 \).
- Функция для нахождения пересечения двух списков.
>>> intersect([1, 2, 3, 4], [2, 3, 4, 6, 8]) [2, 4] >>> intersect([5, 8, 2], [2, 9, 1]) [2] >>> intersect([5, 8, 2], [7, 4]) []
- Функция для расчёта \( x_n = \sqrt{ 3 + \sqrt{ 3 + \sqrt{ 3 + \sqrt{… + \sqrt{3}} } } } \). ( \(n\) корней).
- Функция для создания \(n\)-мерных массивов.
>>> create_n_dim_array(2, 3) [ ['level 2', 'level 2', 'level 2'], ['level 2', 'level 2', 'level 2'], ['level 2', 'level 2', 'level 2'] ] >>> create_n_dim_array(3, 2) [ [ ['level 3', 'level 3'], ['level 3', 'level 3'], ], [ ['level 3', 'level 3'], ['level 3', 'level 3'], ] ]
- Функция для расчёта \( y_k = b_k y_{k - 1} \). \( y_0 = 1, b_k = b_{k-1}x^2, b_0 = \frac{1}{2x}, x \neq 0 \).
- Функция для линеаризации вложенных списков
>>> linearize([1, 2, [3, 4, [5, [6, []]]]]) [1, 2, 3, 4, 5, 6]
- Функция для расчёта \( a_k = 2 b_{k-1} + a_{k-1}; b_k = 2 a_{k-1} +b_{k-1} \). \( a_1 = b_1 = 1 \).
- Функция, определяющая, является ли последовательностть палиндромом.
>>> is_palindrome([1, 2, 3, 2, 1]) True >>> is_palindrome('spam') False
- Функция для вычисления \( x_i = x_{i-1} + x_{i-3} \), \( x_1 = x_2 = x_3 = 1 \).
- Функция для поиска значения в сложном объекте
>>> find([1, 2, [3, 4, [5, [6, []]]]], 4) 3 >>> find([1, 2, [3, 4, [5, [6, []]]]], 'spam']) None
- Функция для расчёта \( a_k = 2 b_{k-1} + a_{k-1}, b_k = 2 b_{k-1}^2 + b_{k-1} \). \( a_1 = u, b_1 = v \).
- Функция, возвращающая все возможные результаты спортивных матчей с разницей в \( k \).
>>> get_matches_results(1) [['0:0', '1:0'], ['0:0', '0:1']] >>> get_matches_results(2) [['0:0', '1:0', '2:0'], ['0:0', '1:0', '1:1', '2:1'], ['0:0', '1:0', '1:1', '1:2'], ['0:0', '0:1', '1:1', '2:1'], ['0:0', '0:1', '1:1', '1:2'], ['0:0', '0:1', '0:2']]
- Функция для вычисления \( x_i = \frac{x_{i-1} + 1}{x_{i-1} + 2} \), \( x_0 = 1 \).
- Функция для вычисления всех перестановок списка длиной \( k \).
>>> k_permutaions([1, 2, 3], 2) [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
- Функция для вычисления \( x_i = i x_{i-1} + \frac{1}{i} \), \( x_0 = 0 \).