книга заданий пайтон. книга практических заданий, pyton. Сборник упражнений Введение в язык Python с задачами и решениями Бен Стивенсон Москва, 2021 удк 004. 438Python
 Скачать 2.24 Mb.
|
Упражнение 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, а в данном упражнении вам предстоит написать рекурсивную функцию, определяющую, является ли переданная ей в виде аргумента строка палиндромом. Стоит отметить, что пустая строка является палиндромом по определению, как и строка, состоящая из одного символа. Более длинные строки можно считать палиндромами, если их первый и последний символы одинаковые, а подстрока, исключающая эти символы, также является палиндромом. Напишите основную программу, которая будет запрашивать у пользователя слово и при помощи рекурсивной функции определять, является ли оно палиндромом. В результате на экране должно появиться соответствующее сообщение. Упражнение 179. Рекурсивный квадратный корень(20 строк) В упражнении 74 вы узнали, как можно при помощи итераций вычислить квадратный корень из числа. В той задаче с каждой итерацией цикла увеличивалась точность приближения расчета. Здесь мы будем применять похожую тактику приближения, но с использованием рекурсии, а не цикла. Напишите функцию вычисления квадратного корня с двумя входными параметрами. Первый из них – n – будет характеризовать число, из которого вычисляется квадратный корень, а второй – guess – текущее приближение при его вычислении. Значение параметра guess по умолчанию примем за 1,0. У первого параметра значения по умолчанию быть не должно. Функция вычисления корня должна быть рекурсивной. Базовый случай будет возникать тогда, когда guess2 будет отличаться от n менее чем на 10–12. В этом случае функция должна возвращать guess, считая, что полученное число достаточно близко к квадратному корню от заданного n. В противном случае функция должна возвращать результат рекурсивно-  го вызова себя самой с n в качестве первого параметра и в качестве второго. Напишите основную программу, в которой будет демонстрироваться работа вашей функции на примере вычисления квадратного корня из нескольких чисел. При первом вызове функции в основной программе необходимо передать ей лишь один параметр, а значение второго – guess – возьмется по умолчанию. Упражнение 180. Редакционное расстояние(Решено. 43 строки) Редакционное расстояние между двумя строками представляет собой меру их схожести. Чем меньше между строками редакционное расстояние, тем более похожими они могут считаться. Это означает, что одна строка может быть преобразована в другую с минимальным количеством операций вставки, удаления и замены символов. Рассмотрим слова kitten и sitting. Первое слово может быть трансформировано во второе путем выполнения следующих операций: заменить k на s, заменить e на i и добавить g в конец строки. Это минимально возможное количество операций, необходимое для преобразования слова kitten в sitting. Таким образом, редакционное расстояние между этими строками составляет 3. Напишите рекурсивную функцию, вычисляющую редакционное расстояние между двумя строками по следующему алгоритму. Имеем исходные строки 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 Используйте написанную вами рекурсивную функцию в основной программе, запрашивающей у пользователя две строки и выводящей на экран редакционное расстояние между ними. |