Рекурсивные алгоритмы.. F(n) = 2 при n = 1. F(n) = F(n–1) + 5n*n, если n > 1. Чему равно значение функции F(6)?. Как вы поступите, если вас попросят вычислить значение F(36)?. В этом случае стоит написать программу, которая возьмет на себя громоздкие в

Стр 1 из 2Следующая ⇒

Рекурсивные алгоритмы.

ЗАДАЧА 1. Алгоритм вычисления функции F(n) задан следующими соотношениями:

F(n) = 2 при n = 1

F(n) = F(n–1) + 5n*n, если n > 1

Чему равно значение функции F(6)?

F(1) = 2

F(2) = F(1) + 5*2*2 = 2 + 20 = 22

F(3) = F(2) + 5*3*3 = 22 + 45 =67

F(4) = F(3) + 5*4*4 = 67 + 80 = 147

F(5) = F(4) + 5*5*5 = 147 + 125 = 272

F(6) = F(5) + 5*6*6 = 272 + 180 = 452

Как вы поступите, если вас попросят вычислить значение F(36)?

В этом случае стоит написать программу, которая возьмет на себя громоздкие вычисления и получит ответ.

PROGRAM PR_1;

var N:integer;

function F(N:integer):integer;

Begin if N=1

then F:=2

else F:=F(N-1)+5*N*N

End;

Begin writeln(F(36) ) End.

ОТВЕТ: 81027

ЗАДАЧА 2. Теперь рассмотрим задачу, в которой нужно узнать какое количество звездочек будет напечатано, если вызвать написанную ниже процедуру F при N=4.

procedure F( n: integer );

begin

write('*');

if n >= 1 then begin

write('*');

F(n-1);

F(n-2);

end;

Здесь удобно представить последовательность вызовов в виде дерева.

Здесь мы довольно быстро и легко получаем, что F(4) = 22.

Если же вызвать процедуру, например, при N=28, то вычисления становятся очень громоздкими, и получить правильный ответ практически невозможно.

В этом случае снова нужно написать программу.

В этой программе нужно добавить глобальную переменную (k), которая будет считать количество звездочек, которые планируется печатать, а печать символов ‘*’ убрать или закомментировать.

Программа может выглядеть, например, так.

PROGRAM PR_2;

var k:integer;

procedure F( n: integer );

begin

K:=K+1; //write('*');

if n >= 1 then begin

k:=k+1; //write('*');

F(n-1);

F(n-2);

end;

Begin k:=0; F(28); writeln(k)

End.

Ответ в этой задаче: 2496118

ЗАДАЧА 3. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

writeln(n);

if n < 6 then begin

n:= n + 1;

F(n + 1);

F( n*2 );

writeln ( n );

end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

Используя представление вызовов процедуры в виде дерева, получаем, что F(1) = 73.

12 Следующая ⇒