ПрЭВМ ЛР №5 Функции

ПрЭВМ, 2 семестр, направление «Прикладная математика и информатика»

1

Лабораторная работа №5. Функции. Рекурсия, перегрузка, шаблоны

Функции

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

Параметры можно передавать по имени и по адресу. Передача по имени рекомендуется только в тех случаях, когда размер параметра меньше или равен размеру указателя соответствующего типа (например, это верно для типа char). Если параметр не должен изменяться, рекомендуется передавать его как константу независимо от того, по имени он передается или по адресу.

Вкачестве параметров в функцию можно передавать:

Стандартные типы.

Одномерные и многомерные массивы.

Строки.

Структуры и другие сложные типы (например, классы).

Имена функций.

Особенности передачи в функцию параметров разных типов см. в соответствующих лабораторных работах. Передача имен функций на практике не рассматривается, интересующиеся могут посмотреть Практикум по структурному программированию (стр. 140-142, задача 7.1-а).

Рекурсивные функции

Рекурсивной является функция, вызывающая сама себя. Такая рекурсия называется простой. Существует еще и сложная рекурсия, когда несколько функций вызывают друг друга таким образом, что вызовы оказываются «закольцованными». Далее будем рассматривать только простую рекурсию.

Рекурсивные алгоритмы, как правило, короче своих нерекурсивных аналогов и выглядят более «красивыми» с математической точки зрения. Однако довольно часто рекурсивная реализация оказывается менее эффективной с точки зрения времени работы программы или занятой памяти. Поэтому рекурсию стоит использовать очень осторожно.

Перегрузка функций

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

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

Перегрузка функций работает так. Компьютер сравнивает типы и число параметров (а не их имена!). Если он находит соответствие имени функции и сравниваемых параметров, вызывает такую функцию.

Подготовлено Латухиной Е.А., старшим преподавателем кафедры ПиВВ ИМИКТ САФУ

ПрЭВМ, 2 семестр, направление «Прикладная математика и информатика»

2

Шаблоны функций

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

Шаблон функции определяет типонезависимую функцию, причем таких типов может быть несколько. С помощью шаблона компилятор определяет конкретные функции с требуемыми типами.

Задания для всех

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

За каждую задачу из этого раздела можно получить не более одного балла (если не сказано иначе).

1.Написать программу, организующую рекурсивное вычисление числа Фибоначчи с номером n. Считать, что Fib(0) = 0, Fib(1) = 1.

2.Написать программу, которая рекурсивно вычисляет факториал числа. Известно,

что 1! = 1, 0! = 1.

3.Написать программу, реализующую рекурсивный алгоритм быстрой сортировки одномерного массива.

4.Написать программу, которая для списка книг библиотеки (см. Л.Р.№4) выдает по запросу список книг либо выпущенных раньше заданного года, либо взятых на определенный срок. Для решения использовать перегрузку функций поиска.

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

Индивидуальные задания

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

Решите следующие задачи:

1.(2 балла) Решите следующую задачу c использованием рекурсии:

Вариант 1: написать программу вычисления двойного факториала для введенного n (n!!). Двойной факториал рассчитывается как произведение как всех натуральных чисел в отрезке [1,n], имеющих ту же чётность что и n:

(2k)!! = 2*4*…*2k для четных n.

(2k + 1)!! = 1*3*…*(2k+1) для нечетных n.

Вариант 2: написать программу, которая переводит введенное число в двоичную систему счисления (использовать рекурсию).

Вариант 3: написать программу, находящую значение n-й степени числа x с использованием рекурсии (x >= 0 – вещественное число, n – целое отрицательное число).

Вариант 4: Вычислить число π по формуле

Для вычисления суммы использовать рекурсию. Вариант 5: Вычислить число π по формуле

Подготовлено Латухиной Е.А., старшим преподавателем кафедры ПиВВ ИМИКТ САФУ

ПрЭВМ, 2 семестр, направление «Прикладная математика и информатика»

3

Для вычисления суммы использовать рекурсию.

Вариант 6: для введенного с клавиатуры числа, состоящего из 2*n цифр, выяснить, является ли оно счастливым (сумма первых n цифр числа равна сумме оставшихся).

Вариант 7: написать рекурсивную функцию C(m,n) целого типа, находящую число сочетаний из n элементов по m, используя формулу:

C(0,n) = C(n,n) = 1,

C(m,n) = C(m,n–1) + C(m–1,n–1) при 0 < m < n (m и n — целые; 0 <= m <= n).

Вариант 8: написать программу, находящую значение n-й степени числа x с использованием рекурсии (x >= 0 – вещественное число, n – целое неотрицательное число). Вариант 9: Дано число n, десятичная запись которого не содержит нулей. Получите число, записанное теми же цифрами, но в противоположном порядке.

Вариант 10: Для введенных с клавиатуры n и m вычислить число K nm по рекуррентной

формуле

Вариант 11: написать программу, которая будет вычислять для заданных целых m и n

функцию Аккермана:
Вариант 12: Вычислить n-е приближение	для заданного x, используя рекур-
рентное соотношение
.

Вариант 13: выяснить, является ли введенная строка палиндромом.

Вариант 14: для натурального n вывести количество разных цифр, участвовавших в его записи.

Вариант 15: написать программу, проверяющую, является ли палиндромом строка S (использовать рекурсию).

Вариант 16: Вычислить n-е значение x 3 a для заданного а, используя рекуррентное соотношение

.

Вариант 17: написать программу, которая будет вычислять для заданных натуральных x, y, z функцию Кадью:

Вариант 18: написать программу, находящую приближенное значение корня k-й степени из вещественного неотрицательного числа x по формуле:

с использованием рекурсии. n – число приближений, вводится с клавиатуры.

Подготовлено Латухиной Е.А., старшим преподавателем кафедры ПиВВ ИМИКТ САФУ

ПрЭВМ, 2 семестр, направление «Прикладная математика и информатика»	4
Вариант 19: написать программу, которая будет вычислять для	заданного целого n

функцию Маккарти:

Вариант 20: Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите значение второго по величине элемента в этой последовательности. Использовать глобальные переменные, массивы и циклы нельзя. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. Результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает. Гарантируется, что последовательность содержит хотя бы два числа (кроме нуля).

2.(2 балла) Используя перегрузку, дополните программу для решения индивидуальной задачи по структурам из л.р.№4, функциями поиска по всем полям и продемонстрируйте их работу.

3.(1 балл) Написать шаблон функции для решения задачи и продемонстрировать его работу для массивов разных типов. Найти:

Вариант 1: произведение элементов массива с нечетными номерами. Вариант 2: сумму элементов массива с четными номерами.

Вариант 3: номер минимального по модулю элемента массива. Вариант 4: сумму элементов массива с нечетными номерами. Вариант 5: произведение элементов массива с четными номерами. Вариант 6: сумму модулей элементов массива с четными номерами. Вариант 7: сумму модулей элементов массива с нечетными номерами. Вариант 8: сумму отрицательных элементов массива.

Вариант 9: количество положительных элементов массива. Вариант 10: произведение отрицательных элементов массива.

Вариант 11: сумму элементов массива, расположенных после минимального элемента массива.

Вариант 12: сумму элементов массива, расположенных после первого положительного элемента массива.

Вариант 13: произведение элементов массива, расположенных после максимального по модулю элемента массива.

Вариант 14: произведение элементов массива, расположенных до минимального по модулю элемента массива.

Вариант 15: произведение элементов массива, расположенных после максимального элемента массива.

Вариант 16: произведение элементов массива, расположенных до максимального элемента массива.

Вариант 17: сумму элементов массива, расположенных после максимального элемента массива.

Вариант 18: произведение элементов массива, расположенных после первого отрицательного элемента массива.

Вариант 19: произведение элементов массива, расположенных до минимального элемента массива.

Вариант 20: произведение элементов массива, расположенных после минимального по модулю элемента массива.

Подготовлено Латухиной Е.А., старшим преподавателем кафедры ПиВВ ИМИКТ САФУ