![]()
|
|||||||
Рекурсивные алгоритмы.. 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; 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; 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.
|
|||||||
|