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

Алгоритмы, опирающиеся на одно предыдущее значение

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

F(1)  =  1;

F(n)  =  F(n–1) · n при n > 1.

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

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

F(1)  =  3;

F(n)  =  F(n – 1) · (n – 1) при n > 1.

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

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

F(1)  =  1;

F(n)  =  5 · F(n – 1) + 3 · n при n > 1.

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

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

F(1)  =  1;

F(n)  =  F(n – 1) · F(n – 1) − F(n – 1) · n + 2 · n при n > 1.

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

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

F(1)  =  0;

F(n)  =  F(n – 1) + n при n > 1;

G(1)  =  1;

G(n)  =  G(n – 1) · n при n > 1.

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

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

F(1)  =  1;

F(2)  =  1;

F(n)  =  F(n – 2) · n при n > 2.

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

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

F(1)  =  1;

F(2)  =  1;

F(n)  =  F(n – 2) · (n – 1) при n > 2.

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

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

F(1)  =  1;

F(n)  =  2 · F(n – 1) + 1 при n > 1.

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

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

F(1)  =  1;

F(2)  =  1;

F(n)  =  F(n – 2) · n при n > 2.

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

10.  

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

F(1)  =  1;

F(2)  =  2;

F(3)  =  3;

F(n)  =  F(n − 3) · n при n > 3.

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

11.  

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

F(1)  =  1;

F(n)  =  F(n − 1) + n, если n > 1.

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

12.  

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

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

F(n)  =  F(n – 1) · n при n ≥ 2.

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

13.  

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

F(1)  =  1

F(n)  =  F(n – 1) · (n + 2) при n > 1.

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

14.  

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

F(1)  =  1;

F(n)  =  F(n – 1) · (2 · n + 1) при n > 1.

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

15.  

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

F(1)  =  1;

F(n)  =  F(n – 1) + 2^{n – 1}, если n > 1.

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

16.  

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

$F левая круглая скобка 0 правая круглая скобка = 0,$ $F левая круглая скобка n правая круглая скобка =F левая круглая скобка n — 1 правая круглая скобка плюс n.$

Укажите количество таких чисел n из интервала 237 567 892 ⩽ n ⩽ 1 134 567 004, для которых F(n) не делится без остатка на 3.

Решение. Функция F(n)  =  F(n – 1) + n возвращает сумму чисел от 1 до n.

Рассмотри начало последовательности:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20...

Заметим, что остаток от деления на 3 будет равен 0 каждое третье число.

Остатки от деления на 3:

1, 2, 0, 1, 2, 0, 1, 2, 0...

Известно, что остаток от деления на 3 суммы остатков от деления чисел на число 3 равен остатку от деления суммы чисел на число 3. Другими словами, остаток суммы остатков равен остатку суммы исходных чисел.

Поэтому последовательность остатков сумм всех чисел от 1 до n при делении на 3 будет:

1, 0, 0, 1, 0, 0, 1, 0, 0...

Таким образом, что F(n) не делится на 3, только если остаток от деления n на 3 равен 1.

Приведём решение Юрия Красильникова на языке Python.

Найдём минимальное число, которое не меньше a и даёт остаток 1 (то есть самое маленькое на отрезке). Это можно сделать, например, по формуле (a + 1)//3 · 3 + 1.

Найдём максимальное число, которое не больше b и даёт остаток 1. Возможная формула (b – 1)//3 · 3 + 1.

Количество таких чисел, очевидно, есть (максимальное-минимальное)//3 + 1.

a,b = 237567892,1134567004

print(((b-1)//3*3-(a+1)//3*3)//3+1)

Поскольку остаток деления числа 237 567 892 на 3 равен единице, то можно привести другое решение.

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

a,b = 237567892,1134567004

print(len(range((a+1)//3*3, b+1, 3)))

Ответ: 298 999 705.

17.  

Обозначим частное от деления натурального числа a на натуральное число b как a div b, а остаток  — как a mod b. Например, 13 div 3  =  4, 13 mod 3  =  1.

F(0)  =  0;

F(n)  =  F(n div 10) + (n mod 10).

Укажите количество таких чисел n из интервала

237 567 892 ≤ n ≤ 1 134 567 009,

для которых F(n) > F(n + 1).

18.  

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

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

F(n)  =  n · F(n – 1) при n > 1.

Чему равно значение выражения (F(2024) − F(2023)) / F(2022)?

19.  

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

$F левая круглая скобка n правая круглая скобка = 1,$ если n  =  1,

$F левая круглая скобка n правая круглая скобка = 2n \times F левая круглая скобка n минус 1 правая круглая скобка плюс F левая круглая скобка n минус 3 правая круглая скобка ,$ если $n больше 1$ и четное,

$F левая круглая скобка n правая круглая скобка = F левая круглая скобка n минус 2 правая круглая скобка \times 3,$ если $n больше 1$ и нечетное.

Чему равно значение выражения $дробь: числитель: F левая круглая скобка 2026 правая круглая скобка , знаменатель: F левая круглая скобка 2021 правая круглая скобка конец дроби ?$

20.  

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

F(n)  =  1000 при n ≤ 5;

F(n)  =  n + 3 + F(n − 2), если n > 5.

Чему равно значение выражения 3 × F(53079) − (F(53077) + F(53075) + F(53073))?

21.  

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

F(n)  =  n при n ≤ 10;

F(n)  =  n − 12 + F(n − 21), если n > 10.

Чему равно значение выражения (F(224356) − F(224272)) / F(59)?

22.  

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

F(n)  =  n при n ≤ 10;

F(n)  =  n − 7 + F(n − 21), если n > 10.

Чему равно значение выражения (F(185734) − F(185650)) / F(40)?

№ п/п	№ задания	Ответ
1	4558	120
2	4642	360
3	4643	332
4	4644	20
5	4656	134
6	4849	105
7	4937	48
8	5278	31
9	6189	105
10	6893	280
11	6958	465
12	7203	240
13	7270	840
14	7273	315
15	7308	1023
16	48437	298999705
17	51985	89699912
18	68517	4092529
19	76231	36471
20	78041	318484
21	83146	12125
22	83174	17274

Ключ