книга заданий пайтон. книга практических заданий, pyton. Сборник упражнений Введение в язык Python с задачами и решениями Бен Стивенсон Москва, 2021 удк 004. 438Python

• Название: Сборник упражнений Введение в язык Python с задачами и решениями Бен Стивенсон Москва, 2021 удк 004. 438Python
• Анкор: книга заданий пайтон
• Дата: 02.10.2022
• Размер: 2.24 Mb.
• Имя файла: книга практических заданий, pyton.docx
• Тип: Сборник упражнений; #709959
• страница: 44 из 69

Упражнение 172. Слова с шестью гласными в ряд

(56 строк) Существует как минимум одно слово в английском языке, содержащее все гласные буквы в том порядке, в котором они расположены в алфавите, а именно A, E, I, O, U и Y. Напишите программу, которая будет просматривать текстовый файл на предмет поиска и отображения таких слов. Имя исходного файла должно быть запрошено у пользователя. Если имя файла окажется неверным или возникнут иные ошибки при чтении файла, выведите соответствующее сообщение об ошибке.

Глава 8

Рекурсия

В главе 4 мы познакомились с функциями и сказали, что они, в свою очередь, также могут вызывать другие функции. Но мы ни разу не обмолвились о том, может ли функция вызывать саму себя. Сейчас пришло время ответить на этот вопрос, и ответить утвердительно, ведь эта специфическая техника помогает решать целый ряд серьезных задач.

Определение, включающее описание чего-то в терминах самого себя, называется рекурсивным (recursive). А чтобы быть полезным, рекурсивное определение должно описывать это что-то в контексте другой, обычно уменьшенной или упрощенной версии себя самого. При использовании той же версии рекурсивное определение не принесло бы пользу, поскольку оказалось бы циклически замкнутым. Для нормального функционирования рекурсия должна постепенно продвигаться к версии задачи с известным решением.

Любая функция, вызывающая саму себя, называется рекурсивной по определению, поскольку в ее описании присутствует указание на саму себя. Чтобы прийти к итоговому решению, рекурсивная функция должна реализовывать как минимум один способ достижения результата без вызова самой себя. Такой способ именуется базовым случаем (base case). Варианты, при которых функция обращается к себе самой, называются рекурсивными случаями (recursive case). В данной главе мы рассмотрим тему рекурсии на трех примерах.

8.1. суммирование целыХ чисел

Предположим, нам необходимо получить сумму всех целых чисел от нуля до заданного n. Это можно сделать при помощи цикла или формулы. Но данную задачу можно решить и при помощи рекурсии. Простейший случай задачи – при n, равном нулю. Ответом, разумеется, будет ноль, и он может быть получен без использования другой версии определения. Так что здесь мы имеем дело с базовым случаем рекурсии.

В целом же задача поиска суммы из 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. Первая из них ожидает возвращения результата запуска второй, а вторая – третьей. Несмотря на то что эти три функции называются одинаково, каждая отдельная копия никак не связана с остальными.

При вызове функции sum_to с аргументом 0 возникает базовый случай, и обратно возвращается 0. Это позволит копии функции с аргументом 1 продвинуться вперед, сложив единицу с нулем, возвращенным рекурсивным вызовом. В результате функция возвращает единицу, и управление передается в первую копию функции с аргументом 2. В ней n, равное двум, прибавляется к единице, полученной из рекурсивного вызова, и итоговый ответ 3 сохраняется в переменной total. После этого значение переменной выводится на экран, и программа завершает свою работу.