ЕГЭ–2026, информатика: задания, ответы, решения

Каталог заданий.
Рекурсивные функции с возвращаемыми значениями

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word

Тип 16 № 36871 Добавить в вариант

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

F(0)  =  0;

F(n)  =  F(n / 2), если n > 0 и при этом чётно;

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

Сколько существует таких чисел n, что 1 ≤ n ≤ 1000 и F(n)  =  3?

Решение.

Приведём аналитическое решение Романа Решетилова :

Докажем, что F(n) - это количество единиц в двоичной записи числа n. По условию, F(0) = 0. F(1) = 1 + F(0) = 1. Предположим, что утверждение верно для любого k-значного в двоичной записи числа с двоичной записью A. Тогда F(A0) = F(A), F(A1) = 1 + F(A). Утверждение доказано.

В промежутке от 1 до 1023 включительно чисел, у которых в точности три единицы в двоичной записи, С(3, 10) = 10!/(3!*7!)=120 (число сочетаний).

Среди чисел от 1001 до 1023 ни одно не содержит в точности три единицы в двоичной записи. Действительно, 24 < 2⁵, поэтому каждое такое число в двоичном виде начинается по крайней мере с пяти единиц.

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

k = 0

for n in range(1, 1001):

if bin(n).count('1') == 3:

k += 1

print(k)

Приведём программу на PascalABC, решающую данную задачу:

var n: longint;

i, count: integer;

function F(n: longint): longint;

begin

if n = 0

then F := 0

else if (((n mod 2) = 0) and (n > 0))

then F := F(n div 2)

else if ((n mod 2) <> 0)

then F := 1 + F(n - 1);

end;

begin

count := 0;

for i := 1 to 1000 do

if F(i) = 3 then count := count + 1;

writeln(count);

end.

Результат работы программы  — 120.

Ответ: 120.

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

def f(n):

if n == 0:

return 0

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

return f(n / 2)

if n % 2 != 0:

return 1 + f(n - 1)

k = 0

for n in range(1, 1001):

if f(n) == 3:

k += 1

print(k)

Приведём решение Виктории Зиберовой на языке Python.

f = [0]*1001

for n in range(1,1001):

if n==0:

f[n]=0

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

f[n]=f[n//2]

if n%2!=0:

f[n]=1+f[n-1]

print(sum([1 for i in f if i==3]))

Решение · Помощь

Тип 16 № 37151 Добавить в вариант

F(n)  =  0, при n ≤ 1;

F(n)  =  F(n − 1) + 3n², если n > 1 и при этом нечётно;

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

Чему равно значение функции F(49)? В ответе запишите только целое число.

Паскаль
function F(N: integer): integer; begin     if n <= 1 then F := 0     else if n mod 2 = 1 then F := F(n-1) + 3nn     else F := (n div 2) + F(n-1) + 2 end; begin     writeln(F(49)) end.
Python
def F(n):     if n <= 1:         return 0     if n % 2 == 1:         return F(n-1) + 3nn     return n // 2 + F(n-1) + 2 print(F(49))
С++
#include <iostream> using namespace std; int F(int n){     if(n <= 1) return 0;     if(n % 2 == 1) return F(n-1) + 3nn;     return n/2 + F(n-1) + 2; } int main(){ std::cout << F(49);}
Алгоритмический
алг цел F(цел n) нач выбор при n<=1 : знач:=0 при n>1 и mod(n,2)=1 : знач:=F(n-1)+3nn при n>1 и mod(n,2)=0 : знач:=div(n,2)+F(n-1)+2 все кон

Источник: ЕГЭ по информатике 24.06.2021. Основная волна

Решение · Помощь

Тип 16 № 38591 Добавить в вариант

Алгоритм вычисления значения функции 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)?

Паскаль
function F(N: integer): integer; begin     if n = 1 then F := 1     else if n mod 2 = 0 then F := n + F(n-1)     else F := 2 * F(n-2) end; begin     writeln(F(26)) end.
Python
def F(n):     if n == 1:         return 1     if n % 2 == 0:         return n + F(n-1)     if n>1 and n % 2 != 0:         return 2 * F(n-2) print(F(26))
С++
#include <iostream> using namespace std; int F(int n){     if(n == 1) return 1;     if(n % 2 == 0) return n + F(n-1);     return 2 * F(n-2); } int main(){ std::cout << F(26);}
Алгоритмический
алг цел F(цел n) нач выбор при n =1 : знач:=1 при mod(n,2)=0 : знач:=n + F(n-1) при n>1 и mod(n,2)=1 : знач:=2 * F(n-2) все кон