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

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

    Задание 1. Применив подход "разделяй и властвуй", реализуйте алгоритм, определяющий наличие в списке элемента X.

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

def is_elem(a, el):
    n = len(a)
    if n == 0:
        return False
    elif n == 1:
        return el == a[0]
    else:
        return (is_elem(a[0:n // 2], el) or    
                is_elem(a[n // 2:n], el))

    Задание 2. Пусть a - список из n неотрицательных целых чисел. Опираясь на подход "разделяй и властвуй", напишите функцию, возвращающую множество цифр, входящих во все значения элементов а. Например, для а = [2348, 1349, 7523, 3215] результатом будет {3}. Функция должна вызывать другую функцию, которая возвращает множество цифр неотрицательного целого числа. Реализуйте и её тоже.

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

def mnog(x):
    if x == 0:
        return set(0)
    rez = set()
    while x != 0:
        rez.add(x % 10)
        x = x // 10
    return rez


def mnog_elem(a):
    n = len(a)
    if len(a) == 0:
        return set()
    elif len(a) == 1:
         return mnog(a[0])
    else:
        return (mnog_elem(a[0:n // 2]) &    
                mnog_elem(a[n // 2:n]))

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

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