РЕШУ ЕГЭ — информатика

Задания

Алгоритм вычисления значения функции F(n), где n  — натуральное число, задан следующими соотношениями:

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

F(n)  =  n + F(n − 1), если n чётно;

F(n)  =  2 · F(n − 2), если n > 1 и при этом n нечётно.

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

Решение. Приведём программу на Паскале, решающий данную задачу:

var n: longint;
function F(n: longint): longint;
  begin
    if n = 1 
      then F := 1
    else if ((n mod 2) = 0) 
      then F := n + F(n - 1)
    else if (((n mod 2) = 1) and (n > 1)) 
      then F := 2 * F(n - 2);
  end;
begin
  n := F(26);
  writeln(n);
end.

Приведём аналитическое решение. Заметим, что значения функции от нечётных n являются значениями степеней двойки: F(1)  =  1, F(3)  =  2, F(5)  =  4 и так далее. Значит, F(25)  =  4096. Тогда F(26)  =  26 + 4096  =  4122.

Ответ: 4122.

Приведём другое решение на языке Python.

def F(n):

if n == 1:

return 1

if n % 2 == 0:

return n + F(n - 1)

if n % 2 != 0 and n > 1:

return 2 * F(n - 2)

print(F(26))

№ п/п	№ задания	Ответ
1	27413	4122

Ключ