Функции
Язык программирования Паскаль допускает введение в программу функции, определяемой пользователем. Она помещается в разделе описаний основной программы.
Запись функции начинается так:
Function
<имя> (<список формальных параметр.>) : <тип рез.>
var
<описание переменных, участвующих в работе функции>
Дальнейшее построение такое же, как и во всех других программах на языке Паскаль.
begin
<операторы>
<имя> := <результат>
end;
Обязательной
является команда присваивания имени функции результата, полученного в итоге ее работы. Функция может быть использована несколько раз в программе.
Для ее вызова достаточно указать имя функции и задать значение формальных параметров: <имя> (<значение параметров>).
Например: s(2, 3) или s(n, a). Параметры и переменные функции могут иметь те же имена, что и переменные в основной программе.
Снова обратимся к наиболее типичным примерам, создаваемых функций. Как вы смогли уже убедиться, их конструкция мало чем отличается от процедур, да и существует возможность обратных преобразований функций в процедуру и процедур в функции.
Известный ряд чисел Фибоначчи имеет вид:
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Каждый член этой последовательности, начиная с третьего, равен сумме двух предыдущих членов.
Если первый член последовательности обозначить f1, второй -
Пользуясь такой зависимостью, можно получить все члены последовательности чисел Фибоначчи.
Формулу, выражающую любой член последовательности, начиная с некоторого, через предыдущие (один или несколько), называют рекуррентной (от латинского слова recurro - возвращаться).
Зная зависимость между последующим и предыдущими членами, легко создать рекурсивную функцию, позволяющую найти n-е число ряда Фибоначчи:
Function fib(n : integer) : longint;
begin
if (n = 1) or (n = 2) then fib := 1
else fib := fib(n - 1) + fib(n - 2)
end;
Здесь, мы одновременно проследим и построение функции и рекурсии.
В заголовке указывается зарезервированное слово Function, далее пишется по фантазии пользователя ее имя, удовлетворяющее всем требованиям, предъявляемым к идентификаторам.
В скобках описываются, как и в процедурах, входные параметры, заметьте, в функции есть только входные параметры, в качестве выходного значения используется сама функция, поэтому обязательно указывается ее тип.
И вот теперь ее имя fib может быть использовано в программе, наряду со встроенными функциями, в различных операторах и арифметических вычислениях.
Построение самой функции начинается, как и построение любой другой программы, но обязательно надо присваивать конечное значение самой функции: fib.
Function fib(n : integer) : longint;
var
f, f1, f2, i : integer;
begin
f1 := 1; f := 0;
for i := 1 to n do
begin
f2 := f1; f1 := f;
f := f1 + f2;
end;
fib := f
end;
Конечно, удобно составлять программу, когда все члены ряда вычисляются по одному правилу, но в ряде Фибоначчи выпадают из общего правила два первых члена. Если мы хотим вычислить и их по тому же правилу, тогда следует в функции fib искусственно продолжить ряд влево, пополнив его двумя фиктивными членами: f(-1) = 1 и f(0) = 0. Тогда ряд примет следующий вид:
1 0 - фиктивные члены ряда
1 1 2 3 5 ... - подлинные члены ряда.
При наличии этих двух фиктивных членов все подлинные члены ряда вычисляются по тем же правилам.
Работу этой функции понять несложно, поэтому мы не будем останавливаться на детальном разборе ее работы.
Можно составить функцию для вычисления чисел Фибоначчи используя рекурсию, тогда она будет выглядеть более компактной:
Function fib(n : integer) : integer;
begin
if (n = 1) or (n = 2) then fib := 1
else fib := fib(n - 1) + fib(n - 2)
end;
Однако, несмотря на внешнюю изысканность, эта функция крайне неэффективна.
Давайте детально проследим за ходом ее работы.
Когда n = 1 или n = 2, получаем значение функции, выполнив функцию один (первый) раз.
Когда n = 3, выполняется вторая (else) ветвь условного оператора и значение функции находится из выражения fib(2) + fib(1).
Для того, чтобы вычислить значение выражения, следует еще два раза (рекурсивно) обратиться к функции fib.
Когда n = 4, функция будет выполняться пять раз, а когда n = 5 - девять раз.
fib(3) fib(2) fib(4) fib(3)
fib(2) fib(1) fib(3) fib(2) fib(2) fib(1)
fib(2) fib(1)
Таким образом, при возрастании значения параметра функции очень быстро возрастает и число обращений к функции, а тем самым увеличивается время вычисления. Это происходит от того, что вторая рекурсивная ветвь условного оператора содержит сразу два рекурсивных вызова. Поэтому эта рекурсивная функция служит примером очень часто встречаемых неэффективных рекурсивных функций.
Часто, внешняя любезность рекурсии оборачивается большими неприятностями.
Приведем и другой способ вычисления членов ряда Фибоначчи с помощью с помощью функции, построенной итеративно. Для ее построения возможны два способа.
Пример 1
Первый способ
Function
Fib(n: integer):longint;
var
f1, f2, f : longint;
i : integer;
begin
f2 := 1; f := 1;
if (n = 1) or (n = 2) then f := 1
else
for i := 3 to
n do
begin
f1 := f2; f2 := f
f := f1 + f2;
end;
fib := f
end;
Второй способ
Function fib(n : integer) : integer;
var
f, f1, f2, i : integer;
begin
f1 := 1; f := 0;
for i := 1 to n do
begin
f2 := f1; f1 := f;
f := f1+f2;
end;
fib := f
end;
Полностью программа:
Program Problem1;
uses WinCrt;
var
i, n : integer;
{----------------------------------------------------------------------------------------}
Function fib(n : integer) : integer;
var
f, f1, f2, i : integer;
begin
f1 := 1; f := 0;
for i := 1 to n do
begin
f2 := f1; f1 := f;
f := f1 + f2;
end;
fib := f
end;
{----------------------------------------------------------------------------------------}
begin
write('Введите значение n '); readln(n);
writeln('Числа Фибоначчи');
for i := 1 to n do write(fib(i), ' ');
writeln
end.
Пример 2.
Последовательность (an) задается так:
Решение
При построение членов последовательности нам придется находить сумму цифр числа. Поэтому есть смысл составить функцию, которая определяет сумму цифр числа. Эта функция может быть построена так:
Function
Sum(a : integer) : integer;
var
s : integer;
begin
s := 0;
repeat
s := s + a mod 10;
a := a div 10
until a = 0;
Sum := s
end;
Вторая функция - это функция, с помощью которой можно получить любой член последовательности:
Function Succ(n : integer) : integer;
var
a, i : integer;
begin
a := 7;
for i := 2 to n do
a := Sum(a*a) + 1;
Succ := a
end;
Полностью программа может быть построена так:
Program Succession; { succession - последовательность }
uses WinCrt;
var
a, i, n : integer;
{----------------------------------------------------------------------------------------}
Function Sum(a: integer): integer;
var
s: integer;
begin
s:=0;
repeat
s := s + a mod 10;
a := a div 10
until a = 0;
Sum := s
end;
{----------------------------------------------------------------------------------------}
Function Succ(n : integer): integer;
var
a, i : integer;
begin
a := 7;
for i := 2 to n do
a := Sum(a*a) + 1;
Succ := a
end;
{----------------------------------------------------------------------------------------}
begin
write(' Введите число членов последовательности ');
readln(n);
for i := 1 to n do write(Succ(i), ' ');
writeln
end.
