Шаг 95.
Рекурсия на Python.
Линейная рекурсия II: хвостовая рекурсия. Примеры задач
На этом шаге мы рассмотрим несколько заданий и приведем их решения.
Приведем несколько примеров решения задач.
Задание 1.
Пусть а - сортированный (в порядке возрастания) список различных целых чисел. Цель этой задачи - эффективный поиск элемента,
значение которого совпадает с его позицией (индексом) в списке. Иными словами, нужно найти элемент i, для которого аi = i.
Например, если а = [-3, -1, 2, 5, 6, 7, 9], то результатом будет 2, так как а2 = 2. Отметим, что первый элемент списка расположен в
позиции 0. Для простоты считайте, что в а не более одного элемента, удовлетворяющего условию аi = i. Если в списке нет такого
элемента, функция должна вернуть значение -1.
Раскрыть/скрыть решение и комментарии.
Помимо самого списка в функцию будем отправлять концы проверяемого промежутка. Пусть middle - его середина. Если окажется, что
middle < a[middle], то сдвигаем влево (к началу списка) верхнюю границу; если middle > a[middle] - сдвигаем вправо (к концу списка) нижнюю
границу. Так мы сужаем список, в котором производим поиск.
Условие выхода из рекурсии - (а) совпадение номера позиции и значения среднего элемента или (б) номера позиции и значения на краях проверяемого промежутка.
Значение -1 вернем тогда, когда позиции нижней и верхней границ промежутка совпадут или будут различаться на 1.
Вот текст программы:
Задание 1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def f5_7(a, lower, upper):
if a[lower] == lower:
return lower
elif a[upper] == upper:
return upper
elif lower == upper or lower + 1 == upper:
return -1
else:
middle = (lower + upper) // 2
if middle == a[middle]:
return middle
if middle < a[middle]:
upper = middle
return f5_7(a, lower, upper)
if middle > a[middle]:
lower = middle
return f5_7(a, lower, upper)
|
Архив с файлом можно взять
здесь.
Задание 2.
Определите и реализуйте хвостовую рекурсивную логическую функцию, определяющую, содержит ли неотрицательное целое число n нечётную цифру.
Раскрыть/скрыть решение и комментарии.
Тут все достаточно просто:
- (а) если n = 0, то возвращается False, так как эта цифра четная;
- (б) проверяем цифру, стоящую в младшем разряде числа: если она нечетная, то возвращаем True, иначе снова вызываем функцию, передавая ей число без последней цифры.
Текст программы:
Задание 2.
1 2 3 4 5 6 7 |
def is_odd(n):
if n == 0:
return False
if (n % 10) % 2 == 1:
return True
else:
return is_odd(n // 10)
|
Архив с файлом можно взять
здесь.
Задание 3.
Алгоритм "сортировки подсчётом" - это метод сортировки списка из n целых чисел в диапазоне [0, k], где k достаточно малое. Метод
работает за время Ο(n + k), откуда следует, что он работает за время Ο(n) при k ∈ Ο(n).
Для заданного списка a метод создаёт новый список b, который содержит количество вхождений каждого целого числа в а, как
показано на рисунке 1 (шаг 1).
![](images/ris95_1.jpg)
Рис.1. Шаги алгоритма сортировки подсчётом
Например, b2 = 4, так как целое число 2 появляется в а четыре раза. Реализуйте хвостовую рекурсивную процедуру, которая
получает списки а и b (изначально нулевой) и заполняет список b количествами вхождений целых чисел в a.
Кроме того, реализуйте линейно-рекурсивную функцию, которая получает список b с количествами вхождений и возвращает новый список c -
отсортированную версию а, как показано на рисунке 1 (шаг 2).
Раскрыть/скрыть решение и комментарии.
Приведем сначала тексты функций.
Задание 3.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
def f(a, b):
if len(a) == 0:
return b
else:
b[a[0]] += 1
return f(a[1:], b)
def beg_f(a):
b = [0] * (max(a) + 1)
return f(a, b)
def f_2(b, ind):
if len(b) == 0:
return []
else:
return [ind] * b[0] + f_2(b[1:], ind + 1)
def beg_f2(b):
index = 0
return f_2(b, index)
|
Архив с файлом можно взять
здесь.
Прокомментируем приведенный текст.
Функция f(), решающая первую задачу, имеет функцию-обертку beg_f(), в которой производится создание нулевого списка b,
количеством элементов, равным k + 1. На рисунке 1 максимальный элемент в списке a равен 4, поэтому количество элементов в списке b
равно 5. Здесь же вызывается функция f().
Реализация этой функции достаточно проста: берем первый элемент из a и увеличиваем на 1 значение из списка b, находящееся на позиции, определяемой этим первым элементом из списка a.
Снова вызываем эту же функцию, предварительно отбросив первый элемент из списка a.
Когда список a станет пустым, нужно вернуть сформированный список b.
Функция f_2(), решающая вторую задачу, имеет функцию-обертку beg_f2(), где определяется номер обрабатываемого элемента в списке b. Так как
каждый раз будет отбрасываться первый элемент из списка b, нужно значение, которое будет хранить общий индекс элемента в списке b (переменная index, равная 0).
Рекурсивное соотношение простое: повторяем значение ind столько раз, сколько указано в первом элементе списка b, после чего его отбрасываем и снова
вызываем функцию f_2() с увеличенным на 1 номером позиции.
Когда список b стал пустым, возвращаем пустой список.
Со следующего шага мы начнем рассматривать множественную рекурсию.
Предыдущий шаг
Содержание
Следующий шаг