Python. Лабораторная работа №3

Задания для самостоятельного выполнения

Сложность:

Rare

1. Напишите две функции для решения задач своего варианта - с использованием рекурсии и без.
2. Оформите отчёт в README.md. Отчёт должен содержать:
   • Условия задач
   • Описание проделанной работы
   • Скриншоты результатов
   • Ссылки на используемые материалы

Сложность:

Medium

• Напишите для своих функций тесты с помощью pytest

Сложность:

Well-done

• Повысьте производительность своих функций минимум в 2 раза относительно исходных вариатов решения

Требования и ограничения

Ни используйте глобальные переменные и прочие средства хранения состояния между вызовами.

Для справки

1. Recursion in Programming - Full Course - freeCodeCamp.org
2. 🐍 Самоучитель по Python для начинающих. Часть 13: Рекурсивные функции - proglib.io
3. Как работает рекурсия – объяснение в блок-схемах и видео - Хабр

Варианты заданий

1. • Функция для подсчёта числа элементов в списках, включая вложенные списки:

   >>> 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} \).
2. • Функция для расчёта суммы вложенных списков.

   >>> sum_nested([1, [2, [3, 4, [5]]]])
   15
   

   • Функции для расчёта \( a_k = \frac{1}{2} (\sqrt{b_{k-1}} + \frac{1}{2}\sqrt{a_{k-1}}), b_k = \frac{3}{2} \sqrt{b_{k-1}} + \frac{1}{2}a_{k-1}^2, a_1 = b_1 = 1 \).
3. • Функция для распаковки списка, содержащего другие объекты (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 \).
4. • Функция для преобразования вложенных списков в строку:

   >>> 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 \).
5. • Функция, которая разделяет список на 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 \).
6. • Функция для нахождения пересечения двух списков.

   >>> intersect([1, 2, 3, 4], [2, 3, 4, 6, 8])
   [2, 3, 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\) корней).
7. • Функция для создания \(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 \).
8. • Функция для линеаризации вложенных списков

   >>> 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 \).
9. • Функция, определяющая, является ли последовательностть палиндромом.

   >>> 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 \).
10. • Функция для поиска значения в сложном объекте

    >>> 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 \).
11. • Функция, возвращающая все возможные результаты спортивных матчей со счётом вплоть до \( k \) - т.е. до тех пор, пока один из игроков не наберёт \( 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 \).
12. • Функция для вычисления всех перестановок списка длиной \( 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 \).