Сборник. Сборник упражнений
 Скачать 1.68 Mb.
|
|
Глава 8 Рекурсия В главе 4 мы познакомились с функциями и сказали, что они, в свою оче- редь, также могут вызывать другие функции. Но мы ни разу не обмолви- лись о том, может ли функция вызывать саму себя. Сейчас пришло время ответить на этот вопрос, и ответить утвердительно, ведь эта специфиче- ская техника помогает решать целый ряд серьезных задач. Определение, включающее описание чего-то в терминах самого себя, называется рекурсивным (recursive). А чтобы быть полезным, рекурсивное определение должно описывать это что-то в контексте другой, обычно уменьшенной или упрощенной версии себя самого. При использовании той же версии рекурсивное определение не принесло бы пользу, посколь- ку оказалось бы циклически замкнутым. Для нормального функциониро- вания рекурсия должна постепенно продвигаться к версии задачи с из- вестным решением. Любая функция, вызывающая саму себя, называется рекурсивной по определению, поскольку в ее описании присутствует указание на саму себя. Чтобы прийти к итоговому решению, рекурсивная функция долж- на реализовывать как минимум один способ достижения результата без вызова самой себя. Такой способ именуется базовым случаем (base case). Варианты, при которых функция обращается к себе самой, называются рекурсивными случаями (recursive case). В данной главе мы рассмотрим тему рекурсии на трех примерах. 8.1. с уммирование целыХ чисел Предположим, нам необходимо получить сумму всех целых чисел от нуля до заданного n. Это можно сделать при помощи цикла или формулы. Но данную задачу можно решить и при помощи рекурсии. Простейший слу- чай задачи – при n, равном нулю. Ответом, разумеется, будет ноль, и он может быть получен без использования другой версии определения. Так что здесь мы имеем дело с базовым случаем рекурсии. 146 Упражнения В целом же задача поиска суммы из n положительных чисел сводится к добавлению числа n к сумме значений от нуля до n – 1. Это определе- ние является рекурсивным, поскольку сумма n целых чисел выражена как уменьшенная версия той же самой задачи (вычисления суммы значений от нуля до n – 1) плюс дополнительная работа (добавление n к этой сумме). С каждым очередным применением рекурсивное определение стремится к базовому случаю рекурсии, когда n равно 0. По достижении базового случая рекурсия завершается, и возвращается итоговый результат. В следующем примере мы разберем рекурсивный алгоритм, описан- ный ранее. Просуммируем целые числа от нуля до значения, введенного пользователем, включительно. Условное выражение if используется для определения того, с каким случаем мы имеем дело – с базовым или ре- курсивным. В первом случае сразу возвращается 0, без запуска рекурсии. Во втором функция вызывается повторно с уменьшенным аргументом (n – 1). Возвращенное из рекурсии значение прибавляется к n. В итоге мы получим сумму всех целых чисел от нуля до n, которая и будет возвращена в виде результата функции. # Вычисляем сумму всех целых чисел от нуля до заданного n с помощью рекурсии # @param n – максимальное значение для включения в сумму # @return сумма всех целых чисел от нуля до n включительно def sum_to(n): if n <= 0 : return 0 # Базовый случай else: return n + sum_to(n – 1) # Рекурсивный случай # Вычисляем сумму всех целых чисел от нуля до заданного n num = int(input("Введите положительное целое число: ")) total = sum_to(num) print("Сумма целых чисел от нуля до", \ num, "равна", total) Представим, что произойдет, если пользователь введет 2. Для начала введенное значение будет преобразовано в число. Затем вызывается функ- ция sum_to с аргументом 2. Условное выражение if возвращает True, так что происходит повторный рекурсивный вызов функции sum_to – на этот раз с аргументом 1. При этом рекурсивный вызов должен завершиться раньше, чем вызывающая функция сможет высчитать и вернуть результат. Вызов функции sum_to с аргументом 1, в свою очередь, приведет к за- пуску еще одной ветки рекурсии с вызовом этой же функции с аргументом 0. На этом этапе у нас есть три одновременно запущенные функции sum_to с разными аргументами: 2, 1 и 0. Первая из них ожидает возвращения результата запуска второй, а вторая – третьей. Несмотря на то что эти три функции называются одинаково, каждая отдельная копия никак не связана с остальными. Рекурсия 147 При вызове функции sum_to с аргументом 0 возникает базовый случай, и обратно возвращается 0. Это позволит копии функции с аргументом 1 продвинуться вперед, сложив единицу с нулем, возвращенным рекурсив- ным вызовом. В результате функция возвращает единицу, и управление передается в первую копию функции с аргументом 2. В ней n, равное двум, прибавляется к единице, полученной из рекурсивного вызова, и итоговый ответ 3 сохраняется в переменной total. После этого значение перемен- ной выводится на экран, и программа завершает свою работу. 8.2. ч исла ф иБоначчи Числами Фибоначчи называется последовательность целых чисел, начи- нающаяся с нуля и единицы, в которой каждое последующее ее значение равно сумме двух предыдущих. Таким образом, первые десять чисел Фи- боначчи будут следующие: 0, 1, 1, 2, 3, 5, 8, 13, 21 и 34. Последовательность чисел Фибоначчи обычно обозначается как F n , где n – неотрицательное целое число, определяющее индекс элемента в последовательности (на- чиная с 0). Числа Фибоначчи, не считая первых двух, можно легко вычислить по формуле F n = F n–1 + F n–2 . Данное определение рекурсивно по своей при- роде, поскольку каждое следующее число ряда Фибоначчи вычисляется на основе предыдущих чисел из этой последовательности. Первые два числа ряда F 0 и F 1 представляют собой базовые случаи рекурсии, так как имеют постоянные значения, не рассчитываемые на основании преды- дущих элементов. Универсальная программа для рекурсивного расчета чисел Фибоначчи представлена ниже. В ней вычисляется и отображается значение F n для n, введенного пользователем. # Рассчитываем n–е число ряда Фибоначчи # @param n – индекс искомого числа Фибоначчи # @return значение n–го числа Фибоначчи def fib(n): # Базовые случаи if n == 0: return 0 if n == 1: return 1 # Рекурсивный случай return fib(n–1) + fib(n–2) # Рассчитываем число Фибоначчи, запрошенное пользователем n = int(input("Введите неотрицательное число: ")) print("fib(%d) равно %d." % (n, fib(n))) 148 Упражнения Это очень компактный рекурсивный алгоритм поиска чисел Фибоначчи, но у него есть минус – он не так быстр, особенно когда речь идет о боль- ших значениях. И если fib(30) на средненьком по мощности компью тере выполнится довольно быстро, то fib(70) потребует в разы больше време- ни. Так что большие числа Фибоначчи обычно вычисляются при помощи цикла или формулы. Из этого вы могли бы сделать вывод, что алгоритмы, включающие в себя рекурсию, обязательно будут медленными. И хотя в данном кон- кретном случае это так, в целом подобное утверждение далеко от истины. Наша предыдущая программа, суммирующая целые числа, работала быст- ро даже для больших значений, а есть и другие задачи, которые быстро и элегантно решаются при помощи рекурсивных алгоритмов. Среди таких задач – алгоритм Евклида, представляющий собой эффективный способ нахождения наибольшего общего делителя двух целых чисел. Подробнее о нем мы поговорим в упражнении 174. На рис. 8.1 схематически показано количество вызовов функций при вычислении числа Фибоначчи для n, равного 4 и 5, и аналогичное коли- чество при расчете суммы целых чисел. Сравнение алгоритмов при раз- ных n наглядно демонстрирует принципиальную разницу между ними. sum_to(4) sum_to(3) sum_to(2) sum_to(1) sum_to(0) fib(4) fib(2) fib(1) fib(2) fib(1) fib(0) fib(1) fib(0) fib(3) sum_to(4) sum_to(5) sum_to(3) sum_to(2) sum_to(1) sum_to(0) fib(4) fib(2) fib(1) fib(2) fib(2) fib(1) fib(1) fib(0) fib(1) fib(1) fib(0) fib(0) fib(3) fib(3) fib(5) Рис. 8.1 Сравнение алгоритмов функций fib и sum_to) Рекурсия 149 При увеличении аргумента, передаваемого функции sum_to, с 4 до 5 количество вызываемых функций для получения результата также воз- растает с 4 до 5. Таким образом, в общем случае увеличение аргумен- та на единицу для этой функции ведет к вызову одной дополнительной функции при вычислении результата. Здесь наблюдается линейный рост сложности алгоритма в зависимости от величины аргумента, а количест во рекурсивных вызовов функции прямо пропорционально величине ис- ходного аргумента. В то же время при увеличении аргумента, передаваемого в функцию fib, с 4 до 5 количество вызовов функций возрастет с 9 до 15. Так что прирост числа n на единицу в случае с вычислением чисел Фибоначчи практически удваивает количество рекурсивных вызовов внутри функции. Такой рост сложности алгоритма называется экспоненциальным. Эффективность алгоритмов подобного типа существенно страдает при их запуске для больших значений, поскольку требует двойного прироста времени при каждом увеличении значения аргумента на единицу. 8.3. п одсчет символов Рекурсивные алгоритмы применимы в большом количестве задач, опре- деления которых могут быть выражены через самих себя. И список подоб- ных задач не ограничивается работой с целыми числами. Представьте, что вам необходимо выяснить, сколько раз определенный символ встречается в строке. Для решения этой задачи может быть написана рекурсивная функция, принимающая на вход строку и искомый символ и возвращаю- щая количество появлений этого символа в строке. Базовый случай для этой функции возникает, если переданная в нее строка является пустой. Логично предположить, что число вхождений любого символа в пустую строку равно нулю, и именно такой результат возвращается из функции – без дополнительных рекурсивных вызовов. Если в функцию передана непустая строка, количество вхождений в нее определенного символа можно определить при помощи следующего ре- курсивного алгоритма. Для упрощения определения рекурсивного случая выделим часть переменной s с исходной строкой, но без первой буквы. Таким образом, подобной урезанной частью строки, состоящей из един- ственного символа, будет пустая строка. Если первым символом в строке s будет искомый символ из переменной ch , то количество его вхождений в строку будет равно единице плюс коли- чество вхождений этого символа в урезанную строку (без первой буквы). В противном случае число вхождений ch в строку s будет равно просто числу его вхождений в урезанную строку. Это определение будет посте- пенно стремиться к базовому случаю рекурсии (когда строка s окажется 150 Упражнения пустой), поскольку сокращенная строка всегда короче полной. Программа, в которой реализован данный алгоритм, представлена ниже. # Посчитать, сколько раз символ входит в строку # @param s – строка, в которой мы будем искать вхождения # @param ch – искомый символ # @return количество вхождений символа ch в строку s def count(s, ch): if s == "": return 0 # Базовый случай # Сокращаем строку, отсекая первый символ tail = s[1 : len(s)] # Рекурсивные случаи if ch == s[0]: return 1 + count(tail, ch) else: return count(tail, ch) # Считаем количество вхождений символа в строку s = input("Введите строку: ") ch = input("Введите искомый символ: ") print("'%s' появляется %d раз в строке '%s'" % (ch, count(s, ch), s)) 8.4. у пражнения Функция называется рекурсивной, если в процессе выполнения она вы- зывает саму себя. Подобные функции обычно включают один или более базовых случаев и один или более рекурсивных случаев. В базовых случаях функции для вычисления результата не требуется обращаться к самой себе повторно, тогда как в рекурсивных планируемый расчет возможен только с попутным обращением к копии этой же функции – зачастую с ис- пользованием уменьшенной или упрощенной версии определения. Все упражнения из данного раздела должны быть выполнены при помощи написания одной или нескольких рекурсивных функций. Каждая из этих функций должна вызывать саму себя и может использовать все техники, ранее описанные в этой книге. Упражнение 173. Сумма значений (Решено. 29 строк) Напишите программу, которая будет складывать числа, введенные поль- зователем. Сигналом к окончанию ввода должна служить пустая строка. Отобразите на экране сумму значений (или 0.0, если пользователь сразу Рекурсия 151 же пропустил ввод). Решите эту задачу с использованием рекурсии. В ва- шей программе не должны присутствовать циклы. Подсказка. В теле вашей рекурсивной функции должен производиться запрос одно- го числа у пользователя, после чего должно быть принято решение о том, произво- дить ли еще один рекурсивный вызов. Ваша функция не должна принимать аргумен- тов, а возвращать будет числовое значение. Упражнение 174. Наибольший общий делитель (24 строки) Евклид был греческим математиком, жившим около 2300 лет назад. Имен- но ему приписывается авторство эффективного рекурсивного алгоритма нахождения наибольшего общего делителя двух положительных чисел a и b. Этот алгоритм описывается так: Если b = 0, тогда Возвращаем a Иначе c = остаток от деления a на b Возвращаем наибольший общий делитель чисел b и c Напишите программу, реализующую алгоритм Евклида для определе- ния наибольшего общего делителя двух положительных чисел, введен- ных пользователем. Проверьте программу на работоспособность с очень большими числами. Результат должен высчитываться очень быстро даже для огромных входных значений, состоящих из сотен чисел. Причина за- ключается в очень высокой эффективности данного алгоритма. Упражнение 175. Рекурсивный перевод числа из десятичного в двоичное (34 строки) В упражнении 82 мы уже писали программу, которая посредством цик- ла переводила значение из десятичной системы счисления в двоичную. Здесь вам придется реализовать этот алгоритм при помощи рекурсии. Напишите рекурсивную функцию, переводящую неотрицательное целое число в двоичную систему. Воспринимайте 0 и 1 как базовые слу- чаи с возвратом соответствующего строкового значения. Для остальных положительных чисел n вам необходимо вычислить следующую цифру при помощи оператора взятия остатка от деления и затем осуществить рекурсивный вызов с вычислением цифр для n // 2. Наконец, вам нужно сцепить строковый результат рекурсивного вызова со следующей циф- 152 Упражнения рой, которую заранее надо преобразовать в строку, и вернуть полученную строку в качестве результата функции. Напишите основную программу, которая будет использовать рекурсив- ную функцию для преобразования неотрицательного числа, введенного пользователем, из десятичной системы счисления в двоичную. Если будет введено отрицательное значение, программа должна вывести соответ- ствующее сообщение об ошибке. Упражнение 176. Фонетический алфавит НАТО (33 строки) Фонетический алфавит представляет собой таблицу обозначений букв, каждой из которых соответствует то или иное слово. Широкое распростра- нение такие алфавиты приобретают в условиях повышенной зашумлен- ности каналов передачи информации, когда собеседник может просто не расслышать конкретную букву. В таких случаях вместо букв используются целые слова. Один из наиболее распространенных фонетических алфа- витов был разработан в военном блоке НАТО. Соответствие букв и слов в нем приведено в табл. 8.1. Напишите программу, которая будет запрашивать слово у пользовате- ля и отображать его на экране в виде шифра из соответствующих слов, обозначающих буквы исходного текста. Например, если пользователь введет слово Hello, на экране должна быть отображена следующая по- следовательность слов: Hotel Echo Lima Lima Oscar. Для решения этой за- дачи вам предстоит использовать рекурсивную функцию, а не циклы. При этом все небуквенные символы, введенные пользователем, можно игнорировать. Таблица 8.1. Фонетический алфавит НАТО Буква Слово Буква Слово Буква Слово A Alpha J Juliet S Sierra B Bravo K Kilo T Tango C Charlie L Lima U Uniform D Delta M Mike V Victor E Echo N November W Whiskey F Foxtrot O Oscar X Xray G Golf P Papa Y Yankee H Hotel Q Quebec Z Zulu I India R Romeo Рекурсия 153 Упражнение 177. Римские цифры (25 строк) Как ясно из названия, римские цифры появились еще в Древнем Риме. Но даже после падения Римской империи они продолжали использоваться на территории Европы вплоть до позднего Средневековья, а в определенных случаях применяются и сегодня. Римские цифры базируются на обозначениях M, D, C, L, X, V и I, со- ответствующих числам 1000, 500, 100, 50, 10, 5 и 1. В основном римские цифры в составляющих их числах располагаются в порядке убывания – от больших к меньшим. В этом случае итоговое число равно сумме всех со- ставляющих его римских цифр. Если цифры меньшего номинала пред- шествуют цифрам большего номинала, то первые вычитаются из вторых и итог прибавляется к общей сумме. В такой манере могут использоваться римские цифры C, X и I. При этом вычитание производится только из чи- сел, максимум в десять раз превосходящих вычитаемое. Таким образом, цифра I может предшествовать V или X, но не может вычитаться из L, C, D или M. А значит, число 99 должно быть написано как XCIX, а не IC. Создайте рекурсивную функцию, которая будет переводить римскую запись чисел в десятичную. Функция должна обрабатывать один или два символа в начале строки, после чего будет производиться ее рекурсивный вызов для оставшихся символов. Используйте пустую строку с возвращае- мым значением 0 в качестве базового случая. Также напишите основную программу, которая будет запрашивать у пользователя число, введенное римскими цифрами, и отображать его десятичный эквивалент. При этом можно сделать допуск о том, что пользователь всегда вводит корректное число, так что обработку ошибок вам реализовывать не нужно. Упражнение 178. Рекурсивные палиндромы (Решено. 30 строк) Определение палиндрома мы дали еще в главе 75, а в данном упражнении вам предстоит написать рекурсивную функцию, определяющую, является ли переданная ей в виде аргумента строка палиндромом. Стоит отметить, что пустая строка является палиндромом по определению, как и строка, состоящая из одного символа. Более длинные строки можно считать па- линдромами, если их первый и последний символы одинаковые, а под- строка, исключающая эти символы, также является палиндромом. Напишите основную программу, которая будет запрашивать у пользо- вателя слово и при помощи рекурсивной функции определять, является ли оно палиндромом. В результате на экране должно появиться соответ- ствующее сообщение. 154 Упражнения Упражнение 179. Рекурсивный квадратный корень (20 строк) В упражнении 74 вы узнали, как можно при помощи итераций вычислить квадратный корень из числа. В той задаче с каждой итерацией цикла увеличивалась точность приближения расчета. Здесь мы будем приме- нять похожую тактику приближения, но с использованием рекурсии, а не цикла. Напишите функцию вычисления квадратного корня с двумя входными параметрами. Первый из них – n – будет характеризовать число, из кото- рого вычисляется квадратный корень, а второй – guess – текущее прибли- жение при его вычислении. Значение параметра guess по умолчанию при- мем за 1,0. У первого параметра значения по умолчанию быть не должно. Функция вычисления корня должна быть рекурсивной. Базовый случай будет возникать тогда, когда guess 2 будет отличаться от n менее чем на 10 –12 . В этом случае функция должна возвращать guess, считая, что полу- ченное число достаточно близко к квадратному корню от заданного n. В противном случае функция должна возвращать результат рекурсивно- го вызова себя самой с n в качестве первого параметра и в качестве второго. Напишите основную программу, в которой будет демонстрироваться работа вашей функции на примере вычисления квадратного корня из нескольких чисел. При первом вызове функции в основной программе необходимо передать ей лишь один параметр, а значение второго – guess – возьмется по умолчанию. Упражнение 180. Редакционное расстояние (Решено. 43 строки) Редакционное расстояние между двумя строками представляет собой меру их схожести. Чем меньше между строками редакционное расстоя- ние, тем более похожими они могут считаться. Это означает, что одна строка может быть преобразована в другую с минимальным количеством операций вставки, удаления и замены символов. Рассмотрим слова kitten и sitting. Первое слово может быть трансфор- мировано во второе путем выполнения следующих операций: заменить k на s, заменить e на i и добавить g в конец строки. Это минимально воз- можное количество операций, необходимое для преобразования слова kitten в sitting. Таким образом, редакционное расстояние между этими строками составляет 3. Напишите рекурсивную функцию, вычисляющую редакционное рас- стояние между двумя строками по следующему алгоритму. Рекурсия 155 Имеем исходные строки s и t Если длина строки s равна нулю, тогда Возвращаем длину строки t Если длина строки t равна нулю, тогда Возвращаем длину строки s Иначе Устанавливаем переменную cost равной 0 Если последний символ в s не совпадает с последним символом в t, тогда Устанавливаем cost равной 1 Устанавливаем d1 равной редакционному расстоянию между строкой s без последнего символа и строкой t с прибавлением единицы Устанавливаем d2 равной редакционному расстоянию между строкой t без последнего символа и строкой s с прибавлением единицы Устанавливаем d3 равной редакционному расстоянию между строкой s без последнего символа и строкой t без последнего символа с прибавлением cost Возвращаем минимальное значение среди d1, d2 и d3 Используйте написанную вами рекурсивную функцию в основной про- грамме, запрашивающей у пользователя две строки и выводящей на экран редакционное расстояние между ними. Упражнение 181. Возможный размен (41 строка) Напишите программу, которая будет определять, можно ли составить конкретную сумму из определенного количества монет. Например, мож- но набрать доллар из четырех монет номиналом в 25 центов. Но при по- мощи пяти монет доллар никак не собрать. При этом из шести монет это снова возможно, если взять три монеты по 25 центов, две – по 10 и одну номиналом в 5 центов. Также возможно собрать сумму $1,25 из пяти или восьми монет, но не удастся это сделать с четырьмя, шестью или семью монетами. Ваша основная программа должна запрашивать у пользователя иско- мую сумму и количество монет. На выходе вы должны получить сообще- ние о том, можно или нет собрать введенную сумму при помощи заданно- го количества монет. Представьте, что для решения этой задачи в вашем распоряжении есть монеты номиналом 1, 5, 10 и 25 центов. Также ваша программа должна включать рекурсивный алгоритм. Циклов в ней быть не должно. Упражнение 182. Слова через химические элементы (67 строк) Каждый химический элемент из таблицы Менделеева характеризуется своим обозначением, состоящим из одного, двух или трех символов. Есть такая игра – пытаться выразить то или иное слово через химические эле- 156 Упражнения менты. Например, слово silicon может быть записано при помощи следу- ющих химических элементов: Si, Li, C, O и N. В то же время слово hydrogen не может быть составлено из названий элементов. Напишите рекурсивную функцию, способную определять, можно ли выразить переданное ей слово исключительно через обозначения хи- мических элементов. Ваша функция должна принимать два параметра: слово, которое нужно проверить, и список символов, которые можно при этом использовать. Возвращать функция должна строку, состоящую из использованных символов, если собрать искомое слово можно, и пустую строку в противном случае. При этом регистры символов учитываться не должны. В основной программе должна быть использована ваша функция для проверки всех элементов таблицы Менделеева на возможность составить их названия из обозначений химических элементов. Отобразите на экра- не названия элементов вместе с обозначениями, которые были использо- ваны для их написания. Например, одна из строчек может выглядеть так: Silver может быть представлен как SiLvEr Для решения задачи вы можете воспользоваться набором данных с хи- мическими элементами, который можно скачать на сайте автора. Этот набор включает в себя названия и обозначения всех 118 элементов пе- риодической таблицы. Упражнение 183. Последовательность химических элементов (Решено. 81 строка) Существует такая игра, в которой химические элементы выстраиваются в длинную цепочку таким образом, чтобы каждое очередное слово на- чиналось на букву, на которую заканчивается предыдущее. Например, если последовательность начинается с элемента Hydrogen, то следующий элемент должен начинаться на N, и это может быть Nickel. Следом может идти Lithium. При этом элементы в ряду не должны повторяться. При игре в одиночку целью является составление списка элементов максимально возможной длины. Если в игре принимают участие двое, то целью стано- вится назвать такой химический элемент, чтобы оппонент не смог про- должить последовательность. Напишите программу, которая будет запрашивать у пользователя химический элемент и при помощи рекурсивной функции определять максимально возможную последовательность слов. Выведите на экран полученный ряд. Удостоверьтесь, что программа выводит соответству- ющее сообщение об ошибке, если пользователь укажет несуществующий химический элемент. Рекурсия 157 Подсказка. Для некоторых элементов вашей программе может понадобиться до двух минут, чтобы найти последовательность максимально возможной длины. Так что вам лучше начать проверку своей программы с элементов Molybdenum или Mag- nesium, для которых длина последовательности составляет всего восемь слов. На выполнение этой задачи уйдет всего несколько секунд. Упражнение 184. Выравниваем список (Решено. 33 строки) Списки в языке Python могут содержать в себе вложенные списки. В то же время вложенные списки могут также состоять из списков, тем самым увеличивая глубину общей иерархии. В результате списки могут обретать структуру, похожую на следующую: [1, [2, 3], [4, [5, [6, 7]]], [[[8], 9], [10]]] Списки со множеством уровней вложенности могут пригодиться при описании сложных отношений между элементами, но при этом такая структура значительно усложняет выполнение операций над элемен- тами. Процесс выравнивания (flattening) списка заключается в избавлении от вложенной структуры и простом перечислении входящих в него элемен- тов. Допустим, для приведенного выше примера выровненный список будет выглядеть так: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Для выполнения операции выравнивания списка data можно последовать следующему ал- горитму: Если список data пуст, тогда Возвращаем пустой список Если первый элемент списка data также является списком, тогда Выравниваем первый элемент списка data и присваиваем результат переменной l1 Выравниваем все элементы первого элемента списка data, за исключением первого, и присваиваем результат переменной l2 Возвращаем результат конкатенации списков l1 и l2 Если первый элемент списка data не является списком, тогда Присваиваем переменной l1 список, состоящий из первого элемента списка data Выравниваем все элементы первого элемента списка data, за исключением первого, и присваиваем результат переменной l2 Возвращаем результат конкатенации списков l1 и l2 Напишите функцию, реализующую рекурсивный алгоритм выравнива- ния списка, описанный выше. Функция должна принимать на вход список и возвращать выровненную версию списка. В основной программе про- демонстрируйте работу функции на примере приведенного выше списка, а также нескольких других. 158 Упражнения Подсказка. В Python есть функция type, возвращающая тип данных своего един- ственного аргумента. Информацию о том, как узнать, является ли передаваемый ей аргумент списком, можно найти в интернете. Упражнение 185. Декодирование на основе длин серий (33 строки) Кодирование на основе длин серий представляет собой простую технику сжатия информации, которая демонстрирует свою эффективность при на- личии множества соседствующих друг с другом повторяющихся значений. Сжатие достигается за счет замены целой группы повторяющихся значе- ний на однократное его упоминание с отдельно хранящимся счетчиком повторов. Например, список ["A", "A", "A", "A", "A", "A", "A", "A", "A", "A", "A", "A", "B", "B", "B", "B", "A", "A", "A", "A", "A", "A", "B"] может быть закодирован в следующем виде: ["A", 12, "B", 4, "A", 6, "B", 1]. Процесс декодирования заключается в размножении каждого элемента в соответствии со счетчиком. Напишите рекурсивную функцию для декодирования списка, коди- рованного на основе длин серий. В качестве единственного аргумента функция должна принимать закодированный соответствующим образом список. На выходе должен получиться расшифрованный список элемен- тов. В основной программе продемонстрируйте работу алгоритма деко- дирования на примере представленного здесь списка. Упражнение 186. Кодирование на основе длин серий (Решено. 38 строк) Напишите рекурсивную функцию, реализующую алгоритм кодирования на основе длин серий, описанный в упражнении 185. На вход функции должен поступать список или строка, а на выходе будет закодированный список. В основной программе запросите у пользователя строку, сожми- те ее при помощи своей функции и отобразите на экране кодированный список. Подсказка. Возможно, вам придется поместить цикл внутрь тела своей рекурсивной функции. Часть II РЕШЕНИЯ |