На этом шаге мы рассмотрим несколько заданий и приведем их решения.

Приведем несколько примеров решения задач.

Задание 1. Реализуйте функцию, вычисляющую количество узлов в двоичном дереве поиска. Считайте, что дерево представлено в виде списка четырехкомпонентных элементов, как описано на 85 шаге.

Раскрыть/скрыть решение и комментарии.

Задание 2. Реализуйте функцию, которая для заданного входного списка a из n элементов определяет самый длинный непрерывный его подсписок одинаковых элементов. Например, для a = [1, 3, 5, 5, 4, 4, 4, 5, 5, 6] результатом будет подсписок [4, 4, 4]. Разбейте задачу так же, как в примере 7.6, и примените вспомогательную рекурсивную функцию, определяющую одинаковость всех элементов подсписка. Кроме того, реализуйте рекурсивную функцию, которая не вызывает вспомогательный метод, как в примере 7.7.

Раскрыть/скрыть решение и комментарии.

За основу возьмем указанные в задании примеры. Сначала реализуем ркурсивную функцию, определяющую одинаковость всех элементов списка. Будем проверять на равенство два первых элемента и рекурсивно вызывать эту же функцию, передавая в нее исходный список без первого элемента. Таким образом, у нас будут сравниваться элементы 0-й и 1-й, 1-й и 2-й и т.д. Процесс прекратится, когда останется только один элемент:

Задание 2. Функция, определяющая одинаковость всех элементов списка

1
2
3
4
5
6

def is_equal(a):
    n = len(a)
    if n <= 1:
        return True
    else:
        return (a[0] == a[1]) and is_equal(a[1:n])

Текст основной функции практически ничем не отличается от функции, приведенной в примере 7.6:

Задание 2. Функция, вызывающая вспомогательный метод

1
2
3
4
5
6
7
8
9
10
11
12

def longest_equal(a):
    n = len(a)
    if is_equal(a):
        return a
    else:
        a_aux_1 = longest_equal(a[1:n])
        a_aux_2 = longest_equal(a[0:n - 1])      
        if len(a_aux_1) > len(a_aux_2):
            return a_aux_1
        else:
            return a_aux_2

И, наконец, рекурсивная функция, которая не вызывает вспомогательный метод:

Задание 2. Рекурсивная функция, не вызывающая вспомогательный метод

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def longest_equal_alt(a):
    n = len(a)
    if n <= 1:
        return a
    else: 
        a_aux_1 = longest_equal_alt(a[1:n])
        if len(a_aux_1) == 2 and a[0] == a[1]:
            return a
        else:
            a_aux_2 = longest_equal(a[1:n])
            a_aux_3 = longest_equal(a[0:n - 1])    
            if len(a_aux_2) > len(a_aux_3):
                return a_aux_2
            else:
                return a_aux_3

Архив с файлом можно взять здесь.

Задание 3. Реализуйте функцию из (3.2), вычисляющую биномиальный коэффициент.

Раскрыть/скрыть решение и комментарии.

Со следующего шага мы начнем рассматривать задачи подсчета.

Предыдущий шаг Содержание Следующий шаг