Подставляемые (встраиваемые) функции. Перегрузка функций
В окружающем нас мире часто можно встретить объекты, обладающие самоподобием. То есть часть большого объекта в чем-то сходна с самим объектом. Например, ветка дерева повторяет форму и характер ветвления, схожие с самим деревом. Приведенные ниже графические объекты также обладают самоподобием. Такие объекты называются рекурсивными.
В языках программирования процедурной парадигмы предусмотрено использование рекурсивных функций в решении задач.
Функция называется рекурсивной, если в своем теле она содержит обращение к самой себе с измененным набором параметров. При этом количество обращений конечно, так как в итоге решение сводится к базовому случаю, когда ответ очевиден.
Пример 1. В арифметической прогрессии найдите an, если известны а1= -2.5, d=0.4, не используя формулу n-го члена прогрессии.
По определению арифметической прогрессии, an= an-1+ d, при этом
an-1= an-2+ d, an-2= an-3+ d,… a2= a1+ d.
Таким образом, нахождение an для номера n сводится к решению аналогичной задачи, но только для номера n-1, что в свою очередь сводится к решению для номера n-2, и так далее, пока не будет достигнут номер 1 (значение а1дано по условию задачи).
float arifm (int n, float a, float d) {
if (n<1) return 0; // для неположительных номеров
if (n==1) return a; // базовый случай: n=1
return arifm(n-1,a,d)+d; // общий случай
}
Пояснение к примеру.
В рекурсивных функциях несколько раз используется return.В базовом случае возвращается конкретный результат (в примере – значение а), а общий случай предусматривает вызов функцией себя же, но с меняющимися значениями отдельных параметров (в примере изменяется только номер члена последовательности, при этом не меняются разность и первый член прогрессии).
Для решения задач рекурсивными методами разрабатывают следующие этапы, образующие рекурсивную триаду:
● параметризация – выделяют параметры, которые используются в решении;
● база рекурсии – определяют тривиальный случай, при котором решение очевидно;
● декомпозиция – выражают общий случай через подзадачи с измененными параметрами.
Пример 2. Для целого неотрицательного числа n найдите его факториал.
Разработаем рекурсивную триаду.
Параметризация: n – неотрицательное целое число.
База рекурсии: для n=0 факториал равен 1.
Декомпозиция: n!=(n-1)!*n.
long factor (int n) {
if (n<0) return 0; // для отрицательных чисел
if (n==0) return 1; // базовый случай: n=0
return factor(n-1)*n; // общий случай (декомпозиция)
}
Целесообразность применения рекурсии в программировании обусловлена спецификой задач, в постановке которых явно или опосредовано указывается на возможность сведения задачи к подзадачам, аналогичным самой задаче.
Пример 3. Дан прямоугольник, стороны которого выражены натуральными числами. Разрежьте его на минимальное число квадратов с натуральными сторонами.
#include <stdio.h>
int kv(int m,int n);
void main(){
int a,b,k;
printf("Введите стороны прямоугольника->");
scanf("%d%d",&a,&b);
k = kv(a,b);
printf("Прямоугольник со сторонами %d и %d можно
разрезать на %d квадратов",a,b,k);
}
int kv(int m,int n){
if(m==n) return 1;
if(m>n) return 1+kv(m-n,n);
return 1+kv(m,n-m);
}
Подставляемые (встраиваемые) функции. Перегрузка функций
Цель работы: повторить принципы работы с функциями, изучить подставляемые (встраиваемые) функции, научиться разрабатывать программы с использованием перегрузки функций на языке C++.
Дата добавления: 2015-02-16; просмотров: 910;