Для того, чтобы задать рекурсивную функцию, нужно определить
F(n) = 1 при n <= 1
F(n) = n + 1 + F(n–1), при n > 1
можно реализовать следующим образом в виде функций на языке программирования Паскаль:
function F( n: integer ): integer;
begin
if n <= 1 then
Result := 1;
else
Result := n + 1 + F(n-1);
end;
Слово Result в Паскале в используется для возврата результата из функции.
Иногда можно использовать ручной расчет результата по формуле, но вычисления будут многочисленными, решение задания потребует много времени.
Пример 1: (демо-2021). Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 1 при n = 1
F(n) = n + F(n–1), если n чётно,
F(n) = 2· F(n–2), если n > 1 и n нечётно.
Чему равно значение функции F(26)?
Решение (ручной счёт от последнего значения):
F(26) = 26 + F(25)
F(25) = 2 × F(23)
F(3) = 2 × F(1)
F(3) = 2 × F(1) = 2
Более эффективный способ - написать и выполнить программу на любом языке программирования ( в данном случае язык Паскаль):
function F( n: integer ): integer;
begin
if n = 1 then begin
F := 1;
Exit;
end;
if n mod 2 = 0 then
F := n + F(n-1)
else
F:= 2 * F(n-2);
end;
begin
writeln( F(26) )
end.
Разбор некоторых заданий ЕГЭ 16 с сайта К.Ю. Полякова (используется язык Паскаль)
Задача 18.
Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:
F(1) = G(1) = 1
F(n) = 2·F(n–1) + G(n–1) – 2, если n > 1
G(n) = F(n–1) +2·G(n–1), если n > 1
Чему равно значение F(14) + G(14)?
Программа:
function G(n:integer):integer;forward;
function F(n:integer):integer;
begin
if n=1
then F:=1
else if n>1
then f:=2*F(n-1)+G(n-1)-2;
end;
function G(n:integer):integer;
begin
if n=1
then G:=1
else if n>1
then G:=F(n-1)+2*G(n-1);
end;
begin
writeln (F(14)+G(14));
end.
Задача 26. Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 1000000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.
Паскаль |
procedure F ( n: integer ); begin writeln(n+1); if n > 1 then begin writeln(n+5); F(n-1); F(n-2); end; end; |
Решение: Вывод чисел в процедуре закомментирован, чтобы уменьшить время выполнения программы.
var s,n:integer;
procedure F ( n: integer );
begin
//writeln(n+1);
s:=s+n+1;
if n > 1 then begin
//writeln(n+5);
s:=s+n+5;
F(n-1);
F(n-2);
end;
end;
begin
n:=0;
repeat
n:=n+1;
s:=0;
F(n);
until s>1000000;
writeln( n, ' ',s);
end.
Задача 56.
Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = n · n · n + n при n > 20
F(n) = 3 · F(n+1) + F(n+3), при чётных n <= 20
F(n) = F(n+2) + 2 · F(n+3), при нечётных n <=20
Определите количество натуральных значений n из отрезка [1; 1000], при которых значение F(n) не содержит цифру 1.
begin
if n>20 Then F:=n*n*n+n
else if n mod 2 =0 then F:= 3*F(n+1)+F(n+3)
else F:=F(n+2)+2*F(n+3);
end;
begin
k:=0;
For n:=1 to 1000 do begin
x:=F(n);
s:=1;
while x>0 do begin
if x mod 10= 1 then s:=0;
x:=x div 10;
end;
k:=k+s;
end;
writeln(k)
end.