Решение

Неравенство решается перебором значений n, метод решения реализован в функции largest_power, аргументами которой являются значения a и b.

program Example_75;

functionlargest_power(a, b: longint):word;

var n: word;

x: longint;

Begin

x:=b; n:=0;

while x<=a do

Begin

x:=b*x; inc(n);

end; {while}

largest_power:=n;

end;{function}

Begin

writeln('3^n<=10000<3^(n+1)');

writeln('n=', largest_power (10000, 3));

write('Нажмите <Enter>');

readln;

End.

Обратите внимание на то, как вызывается функция: writeln('n=', largest_power(10000, 3)). Внутри выражения функция вызывается следующим образом:

имя функции (фактические параметры).

Примеры рекурсивного

Программирования

Алгоритм, который в процессе работы обращает­ся сам к себе, называется рекурсивным. Для иллюст­рации понятия рекурсия часто приводят пример с те­левизором, на экране которого изображен этот же телевизор, на экране второго − опять телевизор и так далее.

Можно разбить все рекурсивные задачи на 4 вида.

Задачи с рекурсивной

Формулировкой

Некоторые объекты являются рекурсивными по оп­ределению, поэтому рекурсивные алгоритмы их получе­ния буквально повторяют соответствующие определения.

Пример

Вычисление факториала натурального числа. Для того чтобы вычислить N!, надо значение (N-1)! умножить на N, при этом 1!=1. В общем виде это можно записать так:

1 при N=1;

N!=

N(N-1)! при N>1.

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

ProgramExample_76;

Function factorial (n: Integer):

Longint;

Begin

if n=1 Then factorial:=1

Else factorial:=n*factorial(n-1);

End;

Рассмотрим последовательность вызовов этой функ­ции для n=5.Первый вызов функции происходит в основной программе a:=factorial(5). Отметим, что при каждом обращении к функции будет создаваться свой набор локальных переменных (в данном случае в функции factorial имеется всего одна локальная переменная n). Для каждой локальной переменной на время работы функции выделяется память. После завер­шения работы функции эта память освобождается и пе­ременные удаляются.

Так как n≠1, то управление передается на ветку Else и функции factorial присваивается значение n*factorial(n-1), то есть 5*factorial(4). Про­исходит второй вызов функции factorial, с парамет­ром 4. Этот процесс повторяется до тех пор, пока значе­ние параметра не станет равным 1. Тогда n=1, а поэто­му значение функции factorial=1. Таким образом, n=1 − это условие окончания рекурсии. Управление пе­редается в точку вызова, то есть в предыдущую функцию для n=2 factorial:=n*factorial(n-1), значит, factorial: =2*1, следовательно, factorial(2)=2. Возвращаемся назад, поднимаясь "вверх" по цепочке ре­курсивных вызовов. Таким образом, получаем значение factorial(5)=120, это значение и присваивается пе­ременной а.