Лабораторная работа №11. Функции и рекурсия

Цель: Приобретение практических навыков по работе с Функциями и рекурсиями:

– Функции

– Локальные и глобальные переменные

– Рекурсия

Задание. Напишите программу, согласно варианту.

Содержание отчета:

– Постановка задание

– Описание входных/выходных данных

– Алгоритм работы программы

– Код программы с комментариями

– Файл с кодом программы на языке Python 

Варианты заданий

Во всех задачах считывайте входные данные через input() и выводите ответ через print().

№	Задание
1.	Даны четыре действительных числа: x1, y1, x2, y2. Напишите функцию distance(x1, y1, x2, y2), вычисляющая расстояние между точкой (x1,y1) и (x2,y2). Считайте четыре действительных числа и выведите результат работы этой функции.   Если вы не знаете, как решить эту задачу, то вы, возможно, не изучали в школе теорему Пифагора. Попробуйте прочитать о ней на Википедии.
2.	Дано действительное положительное число a и целоe число n. Вычислите a^n. Решение оформите в виде функции power(a, n). Стандартной функцией возведения в степень пользоваться нельзя.
3.	Напишите функцию capitalize(), которая принимает слово из маленьких латинских букв и возвращает его же, меняя первую букву на большую. Например, print(capitalize('word')) должно печатать слово Word. На вход подаётся строка, состоящая из слов, разделённых одним пробелом. Слова состоят из маленьких латинских букв. Напечатайте исходную строку, сделав так, чтобы каждое слово начиналось с большой буквы. При этом используйте вашу функцию capitalize(). Напомним, что в Питоне есть функция ord(), которая по символу возвращает его код в таблице ASCII, и функция chr(), которая по коду символа возвращает сам символ. Например, ord('a') == 97, chr(97) == 'a'.
4.	Дано действительное положительное число a и целое неотрицательное число n. Вычислите a^n не используя циклы, возведение в степень через ** и функцию math.pow(), а используя рекуррентное соотношение a^n=a ⋅a^n-1. Решение оформите в виде функции power(a, n).
5.	Дана последовательность целых чисел, заканчивающаяся числом 0. Выведите эту последовательность в обратном порядке. При решении этой задачи нельзя пользоваться массивами и прочими динамическими структурами данных. Рекурсия вам поможет.
6.	Напишите функцию fib(n), которая по данному целому неотрицательному n возвращает n -e число Фибоначчи. В этой задаче нельзя использовать циклы — используйте рекурсию.

 

Методические указания

Функции

Напомним, что в математике факториал числа n определяется как n! = 1 ⋅ 2 ⋅... ⋅ n. Например, 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120. Ясно, что факториал можно легко посчитать, воспользовавшись циклом for. Представим, что нам нужно в нашей программе вычислять факториал разных чисел несколько раз (или в разных местах кода). Конечно, можно написать вычисление факториала один раз, а затем используя Copy-Paste вставить его везде, где это будет нужно.   

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

Функции — это такие участки кода, которые изолированы от остальный программы и выполняются только тогда, когда вызываются. Вы уже встречались с функциями sqrt(), len() и print(). Они все обладают общим свойством: они могут принимать параметры (ноль, один или несколько), и они могут возвращать значение (хотя могут и не возвращать). Например, функция sqrt() принимает один параметр и возвращает значение (корень числа). Функция print() принимает переменное число параметров и ничего не возвращает.

Покажем, как написать функцию factorial(), которая принимает один параметр — число, и возвращает значение – факториал этого числа.

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

Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной res. Функция завершается инструкцией return res, которая завершает работу функции и возвращает значение переменной res.

Инструкция return может встречаться в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова. Если функция не возвращает значения, то инструкция return используется без возвращаемого значения. В функциях, которым не нужно возвращать значения, инструкция return может отсутствовать.

Приведём ещё один пример. Напишем функцию max(), которая принимает два числа и возвращает максимальное из них (на самом деле, такая функция уже встроена в Питон).

Теперь можно написать функцию max3(), которая принимает три числа и возвращает максимальное их них.

Встроенная функция max() в Питоне может принимать переменное число аргументов и возвращать максимум из них. Приведём пример того, как такая функция может быть написана.

Все переданные в эту функцию параметры соберутся в один кортеж с именем a, на что указывает звёздочка в строке объявления функции.