книга заданий пайтон. книга практических заданий, pyton. Сборник упражнений Введение в язык Python с задачами и решениями Бен Стивенсон Москва, 2021 удк 004. 438Python
 Скачать 2.24 Mb.
|
8.4. упражненияФункция называется рекурсивной, если в процессе выполнения она вызывает саму себя. Подобные функции обычно включают один или более базовых случаев и один или более рекурсивных случаев. В базовых случаях функции для вычисления результата не требуется обращаться к самой себе повторно, тогда как в рекурсивных планируемый расчет возможен только с попутным обращением к копии этой же функции – зачастую с использованием уменьшенной или упрощенной версии определения. Все упражнения из данного раздела должны быть выполнены при помощи написания одной или нескольких рекурсивных функций. Каждая из этих функций должна вызывать саму себя и может использовать все техники, ранее описанные в этой книге. Упражнение 173. Сумма значений(Решено. 29 строк) Напишите программу, которая будет складывать числа, введенные пользователем. Сигналом к окончанию ввода должна служить пустая строка. Отобразите на экране сумму значений (или 0.0, если пользователь сразу же пропустил ввод). Решите эту задачу с использованием рекурсии. В вашей программе не должны присутствовать циклы. Подсказка. В теле вашей рекурсивной функции должен производиться запрос одного числа у пользователя, после чего должно быть принято решение о том, производить ли еще один рекурсивный вызов. Ваша функция не должна принимать аргументов, а возвращать будет числовое значение. Упражнение 174. Наибольший общий делитель(24 строки) Евклид был греческим математиком, жившим около 2300 лет назад. Именно ему приписывается авторство эффективного рекурсивного алгоритма нахождения наибольшего общего делителя двух положительных чисел a и b. Этот алгоритм описывается так: Если b = 0, тогда Возвращаем a Иначе c = остаток от деления a на b Возвращаем наибольший общий делитель чисел b и c Напишите программу, реализующую алгоритм Евклида для определения наибольшего общего делителя двух положительных чисел, введенных пользователем. Проверьте программу на работоспособность с очень большими числами. Результат должен высчитываться очень быстро даже для огромных входных значений, состоящих из сотен чисел. Причина заключается в очень высокой эффективности данного алгоритма. Упражнение 175. Рекурсивный перевод числа из десятичного в двоичное(34 строки) В упражнении 82 мы уже писали программу, которая посредством цикла переводила значение из десятичной системы счисления в двоичную. Здесь вам придется реализовать этот алгоритм при помощи рекурсии. Напишите рекурсивную функцию, переводящую неотрицательное целое число в двоичную систему. Воспринимайте 0 и 1 как базовые случаи с возвратом соответствующего строкового значения. Для остальных положительных чисел n вам необходимо вычислить следующую цифру при помощи оператора взятия остатка от деления и затем осуществить рекурсивный вызов с вычислением цифр для n // 2. Наконец, вам нужно сцепить строковый результат рекурсивного вызова со следующей цифрой, которую заранее надо преобразовать в строку, и вернуть полученную строку в качестве результата функции. Напишите основную программу, которая будет использовать рекурсивную функцию для преобразования неотрицательного числа, введенного пользователем, из десятичной системы счисления в двоичную. Если будет введено отрицательное значение, программа должна вывести соответствующее сообщение об ошибке. Упражнение 176. Фонетический алфавит НАТО(33 строки) Фонетический алфавит представляет собой таблицу обозначений букв, каждой из которых соответствует то или иное слово. Широкое распространение такие алфавиты приобретают в условиях повышенной зашумленности каналов передачи информации, когда собеседник может просто не расслышать конкретную букву. В таких случаях вместо букв используются целые слова. Один из наиболее распространенных фонетических алфавитов был разработан в военном блоке НАТО. Соответствие букв и слов в нем приведено в табл. 8.1. Напишите программу, которая будет запрашивать слово у пользователя и отображать его на экране в виде шифра из соответствующих слов, обозначающих буквы исходного текста. Например, если пользователь введет слово Hello, на экране должна быть отображена следующая последовательность слов: Hotel Echo Lima Lima Oscar. Для решения этой задачи вам предстоит использовать рекурсивную функцию, а не циклы. При этом все небуквенные символы, введенные пользователем, можно игнорировать. Таблица 8.1. Фонетический алфавит НАТО
|