Решение 16 задание егэ информатика в excel
ЕГЭ-16: решение через Excel
В этой презентации рассмотрено решение некоторых
задач из 16 задания ЕГЭ через Excel.
Презентация не подготовит Вас полностью к решению
16-го задания!
Нужно будет также научиться решать задачи
программированием: некоторые типы задач невозможно
или слишком тяжело решить с помощью Excel.
Задача 1
Алгоритм вычисления функции 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)?
Решение задачи 1 - Excel
Решение с помощью Excel является усовершенствованным способом решения через
таблицу. Будьте очень аккуратны при решении задач таким методом: очень легко
допустить ошибку, скопировав не в ту ячейку.
Требуется создать таблицу из двух строк и 27 колонок:
Заполним ячейку B2 (значение F(1)). По условию задачи F(1) = 1.
Решение задачи 1 - Excel
Следующая ячейка, которую нужно заполнить, B3 (значение F(2)). 2 – чётное число,
поэтому:
F(n) = n + F(n–1)
Если n = 2, F(2) = 2 + F(1)
Чтобы формулу в дальнейшем можно было растиражировать, везде, там, где в
формуле стоит n и F(n -1), мы поставим ссылки на конкретные ячейки в таблице.
Конкретные значения (2 и 1) подставлять ни в коем случае не нужно!
n = 2 - это ячейка C1
F(n - 1) = F(1) – это ячейка B2
Формула в ячейка выглядит так:
= C1 + B2
Формулу требуется переписать прямо вместе с равно.
Решение задачи 1 - Excel
Получаем:
Для F(4), F(6), F(8), F(10) . F(26) будет работать та же формула, что и для F(2), а для
F(5), F(7), F(9), F(11) . F(25) – та же формула, что и для F(3).
Растиражируем формулу:
до числа 26
Самостоятельно
1.1) Чему равно значение функции F(10)?
F(n) = 1 при n = 1
F(n) = 2·F(n–1) + n + 3, если n > 1
1.2) Чему равно значение функции F(1)?
F(n) = 2n – 5 при n > 12
F(n) = 2·F(n+2) + n – 4, если n 1.3) Чему равно значение F(64)?
F(n) = 1 при n = 1
F(n) = 2·F(n–1), если n чётно,
F(n) = 5n + F(n–2), если n нечётно.
Задача 2
Алгоритм вычисления функции F(n) задан следующими
соотношениями:
F(n) = 5–n при n < 5
F(n) = 4· (n – 5)·F(n–5), если n делится на 3,
F(n) = 3n + 2·F(n–1) + F(n–2), если n не делится на 3.
Чему равно значение функции F(20)?
Решение задачи 2 - Excel
Решение подстановкой выходит очень сложным – слишком много возможностей
допустить арифметическую ошибку. Гораздо удобнее решать эту задачу в Excel.
Требуется создать таблицу из двух строк и 21 колонки:
По условию задачи F(n) = 5–n при n < 5. На самом деле это – выход из рекурсии
(потому что значение F(n) можно вычислить сразу же).
Определим, какую формулу нужно записать в ячейку B2:
5 – это константа, поэтому так и перепишем в формулу;
n находится в ячейке B1. Нельзя подставлять сюда значение 1: так формулу не
получится растиражировать.
Решение задачи 2 - Excel
Итоговая формула для ячейки B2:
=5 – B1
Формула F(n) = 5 – n справедлива при n < 5, т.е. для ячеек B2 – E2. Растиражируем:
до числа 4 (ячейка E2)
Решение задачи 2 - Excel
Получаем:
Для остальных ячеек эта формула уже не подойдёт.
Для n=5:
F(n) = 3n + 2·F(n–1) + F(n–2)
3 и 2 – константы, их просто переписываем в формулу. Значение n для n=5 находится
в ячейке F1, значение F(n-1) находится в ячейке E2, значение F(n – 2) находится в
ячейке D2, значение F(n) (т.е. F(5)) находится в ячейке F2. Итоговая формула в
ячейке F2:
=3*F1 + 2*E2 + D2
Решение задачи 2 - Excel
Для F(6) (ячейка G2):
F(n) = 4· (n – 5)·F(n–5), т.к. 6 делится на 3
4 – константа, так и переписываем, n - это ячейка G1, F(n – 5) – это F(1), т.е. ячейка
B2. Получаем:
= 4 * (G1 - 5) * B2
Решение задачи 2 - Excel
Для F(7) (ячейка H2) формула строится по такому же принципу, как и для F(5).
Получаем, что в ячейку H2 надо записать формулу:
=3*H1+2*G2+F2
Для F(9), F(12), F(15), F(18) формула строится таким же образом, как и для F(6).
Для F(8), F(11), F(14), F(17), F(20) формула строится так же, как и для F(5).
Для F(10), F(13), F(16), F(19) формула строится так же, как и для F(7).
Все значения n "покрыты". Можно тиражировать формулу.
Решение задачи 2 - Excel
нижнем углу выделения и протянуть до
числа 4 (ячейка E2)
Обратите внимание: тиражируются ячейки F2-H2, первые ячейки таблицы мы не
трогаем.
После тиражирования:
полностью значение в ячейки S2-U2 не
влезает, чтобы увидеть ответ, растяните
ячейку U2
Самостоятельно
2.1) Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 2 · n · n · n + n · n при n > 25
F(n) = F(n+2) + 2 · F(n+3), если n Чему равна сумма цифр значения функции F(2)?
2.2) Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 1+2n при n < 5
F(n) = 2·(n + 1)·F(n–2), если n делится на 3,
F(n) = 2·n + 1 + F(n–1) + 2·F(n–2), если n не делится на 3.
Чему равно значение функции F(15)?
2.3) Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = n + 3 при n < 3
F(n) = (n + 2)·F(n–4), если n делится на 3,
F(n) = n + F(n–1) + 2·F(n–2), если n не делится на 3.
Чему равно значение функции F(20)?
Задача 3
Алгоритм вычисления функций 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)?
Решение задачи 3 – Excel
Создадим таблицу из 3 строк и 15 колонок.
По условию задачи F(1) = 1, G(1) = 1.
Решение задачи 3 – Excel
Разберём формулу F(n) = 2·F(n–1) + G(n–1) – 2, если n > 1
Для F(2) получаем: F(2) = 2*F(1) + G(1) – 2
F(1) – это ячейка B2
G(1) – это ячейка B3
F(2) – это ячейка C2
Т.е. в ячейку C2 нужно записать формулу:
= 2*B2 + B3 – 2
Решение задачи 3 – Excel
Получаем:
Сразу же тиражируем на всю 2-ю строчку. Значения получатся
неправильные, но мы потом их исправим.
Решение задачи 3 – Excel
Разберём формулу G(n) = F(n–1) +2·G(n–1), если n > 1
Для G(2) получаем: G(2) = F(1) + 2*G(1)
F(1) – это ячейка B2
G(1) – это ячейка B3
G(2) – это ячейка C3
Т.е. в ячейку C3 нужно записать формулу:
= B2 + 2*B3
Решение задачи 3 – Excel
Получаем:
Сразу же тиражируем на всю 3-ю строчку. Теперь значения во всей
таблице будут правильными.
Решение задачи 3 – Excel
Растянем последний столбец, чтобы увидеть, чему равны
значения F(14) и G(14).
Т.к. в ответе требуется сумма F(14)+G(14), в какой-нибудь
произвольной пустой ячейке запишем:
= O2 + O3
Самостоятельно
3.1) Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:
F(n) = G(n) = 1 при n = 1
F(n) = F(n–1) – n· G(n–1), при n > 1
G(n) = F(n–1) + 2· G(n–1), при n > 1
Чему равно значение функции G(18)?
3.2) Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:
F(n) = G(n) = 1 при n = 1
F(n) = F(n–1) – 2 · G(n–1), при n > 1
G(n) = F(n–1) + G(n–1) + n, при n > 1
Чему равна сумма цифр значения функции G(36)?
3.3) Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:
F(n) = G(n) = 4*n – 2 при n > 7
F(n) = F(n+1) - G(n+2) + n, при n G(n) = 2*F(n+2) - G(n+1), при n Чему равно значение F(-9) + G(-9)?
16-е задание: «Вычисление рекуррентных выражений»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 9 минут.
Проверяемые элементы содержания: Вычисление рекуррентных выражений
"Для успешного выполнения этого задания следует аккуратно произвести трассировку
предложенной рекурсивной функции"
Типичные ошибки и рекомендации по их предотвращению:
"Крайне важно отслеживать правильность возврата выполнения программы в нужную точку для
каждого рекурсивного вызова"
Объяснение темы «Рекурсивные процедуры и функции»
Для начала, разберем некоторые определения.
-
Процедура (функция)– это вспомогательный алгоритм (фрагмент кода программы), который служит для выполнения определенных действий.
var x,y:integer; < заголовок процедуры с формальными переменными x и y:>procedure Sum(x,y:integer); begin . end; // основная программа begin . end.
var x,y:integer; < заголовок функции с формальными переменными x и y:>function Sum(x,y:integer): integer; begin . end; // основная программа begin . end.
< заголовок процедуры с формальными переменными x и y:>procedure Sum(x,y:integer); begin . end; // основная программа begin Sum(100,200) end.
< заголовок функции с формальными переменными x и y:>function Sum(x,y:integer): integer; begin . end; // основная программа begin write (Sum(100,200)) end.
var x,y:integer; procedure Sum(x,y:integer); begin //3. Выводим сумму двух запрошенных чисел write(x+y); end; begin // 1. запрашиваем два числа readln(x,y); // 2. передаем запрошенные числа в процедуру Sum(x,y) end.
Подробное описание работы с процедурами можно найти, перейдя по ссылке.
procedure row(n:integer); begin if n >=1 then begin write (n, ' '); row(n-1) end; end; begin row(10); end.
Для использования рекурсии, необходимо задать:
-
условие остановки рекурсии (обычно, в виде условного оператора):
if n >=1 then begin
Подробное описание работы с рекурсивными процедурами и функциями в Паскале можно найти здесь.
Решение заданий 16 ЕГЭ по информатике
Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ
Решение по рекуррентной формуле
Алгоритм вычисления значений функций F(n) и G(n) , где n – натуральное число, задан следующими соотношениями:
Чему равна сумма цифр значения F(18)?
✍ Решение:
function F(n: integer): integer; forward; function G(n: integer): integer; forward; function F(n: integer): integer; begin if n = 1 then F := 1 // или result := 1 else if n >= 2 then F := F(n - 1) + 3 * G(n - 1) // или result := F(n - 1) + 3 * G(n - 1) end; function G(n: integer): integer; begin if n = 1 then G := 1 // или result := 1 else if n >= 2 then G := F(n - 1) - 2 * G(n - 1) // или result := F(n - 1) - 2 * G(n - 1) end; begin var res := F(18); var s := 0; while res > 0 do begin s := s + (res mod 10); res := res div 10; end; print(s) end.
def F( n ): if n == 1: return 1 elif (n >= 2): return F(n-1)+3*G(n-1) def G( n ): if n == 1: return 1 elif (n >= 2): return F(n-1)-2*G(n-1) res = F(18) s = 0 while res > 0: s += res%10 res = res // 10 print(s)
Результат: 46
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
Чему равно значение функции F(5)? В ответе запишите только целое число.
✍ Решение:
function F(n: integer): integer; begin if n = 1 then F := 1 else if n > 1 then F := F(n - 1) * (n + 2) end; begin print(F(5)) end.
function F(n:integer):integer:= n=1 ? 1 : F(n-1) * (n+2); begin print(F(5)) end.
def F( n ): if n == 1: return 1 elif (n > 1): return F(n-1)*(n+2) print (F(5))
✎ Решение теоретическое (методом с конца к началу):
- Из условия задания мы имеем рекуррентную формулу: F(n–1) * (n + 2) и условие остановки рекурсии: n > 1.
- Поскольку рекуррентная формула уже задана, то остается подставить в нее начальный параметр — число 5:
- Теперь применим эту формулу для всех вызываемых вложенных функций, вплоть до F(1) (при котором «сработает» остановка рекурсии). Получим:
- На F(2) необходимо остановиться, так как действует условие остановки рекурсии: формула работает для n > 1. Также учтем, что по условию F(1) = 1.
- Теперь с конца к началу перепишем все получившиеся сомножители и перемножим их:
Результат: 840
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
Чему равно значение функции F(6)? В ответе запишите только целое число.
✍ Решение:
function F(n:integer):integer; begin if (n = 0) or (n = 1) then result:=1 else if n>1 then result:=2*F(n-1) + F(n-2); end; begin print(F(6)) end.
✎ Решение 1. Теоретическое (метод решения с начала к концу):
✎ Решение 2. Теоретическое (метод решения с конца к началу):
- Поскольку рекуррентная формула уже задана, то остается подставить в нее начальный параметр — число 6:
- Теперь применим эту формулу для всех вызываемых вложенных функций, вплоть до F(2) (F(1) и F(0) известны из условия задачи). Получим:
- Теперь с конца к началу перепишем все получившиеся значения функций:
Результат: 99
Решение данного задания 16 также можно посмотреть в видеоуроке (теоретическое):
Видеорешение на RuTube здесь
Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
Чему равно значение величины F(5)/G(5)?
В ответе запишите только целое число.
function F(n: integer): integer; forward; function G(n: integer): integer; forward; function F(n:integer):integer; begin if n = 1 then result:=1 else if n>=2 then result:=F(n-1) - G(n-1); end; function G(n:integer):integer; begin if n = 1 then result:=1 else if n>=2 then result:=F(n-1) + 2*G(n-1); end; begin print(F(5)/G(5)) end.
✎ Решение теоретическое:
- Решим задание с вызова функций F(5) и G(5). Будем получать формулы последовательно для F(5), F(4), …, F(1), G(5), G(4), …, G(1). Дойдя до известных значений F(1) = 1 и G(1) = 1, подставим их в полученные формулы:
- Итого:
Ответ: -2
Что вернет функция. Сколько символов «звездочка». Какова сумма чисел
16_9: ЕГЭ по информатике 2020 задание 1 (Самылкина Н.Н., Синицкая И.В., Соболева В.В., «Тематические тренировочные задания»):
Что вернет функция F, если ее вызвать с аргументом 6?
function f(a:word):longword; begin if a>0 then f := f(a-1)*a; else f:=1; end;
FUNCTION F(a) IF a > 0 THEN F = F(a - 1) * a ELSE F = 1; END IF END FUNCTION
def F(a): if a > 0: return F(a - 1) * a else: return 1
int F(int a); int F(int a) < if (a >0) return F(a - 1) * a; else return 1; >
function f(a:word):longword; begin if a>0 then f := f(a-1)*a else f:=1; end; begin print(f(6)) end.
✎ Решение теоретическое:
Рассмотрим алгоритм функции:
Ответ: 720
16_3: ЕГЭ по информатике 2017 задание 16 (11) ФИПИ вариант 2 (Крылов С.С., Чуркина Т.Е.):
Ниже записаны две рекурсивные функции (процедуры): F и G.
Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(18)?
procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin write('*'); if n > 10 then F(n - 2) else G(n); end; procedure G(n: integer); begin write('**'); if n > 0 then F(n - 3); end;
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) PRINT "*" IF n > 10 THEN F(n - 2) ELSE G(n) END IF END SUB SUB G(n) PRINT "**" IF n > 0 THEN F(n - 3) END IF END SUB
def F(n): print("*") if n > 10: F(n - 2) else: G(n) def G(n): print("**") if n > 0: F(n - 3)
✍ Решение:
procedure F(n: integer); forward; procedure G(n: integer); forward; var k:=0; // объявление глобальной переменной-счетчика procedure F(n: integer); begin write('*'); k+=1; // увеличение счетчика if n > 10 then F(n - 2) else G(n); end; procedure G(n: integer); begin write('**'); k+=2;// увеличение счетчика if n > 0 then F(n - 3); end; begin f(18); print(k) // вывод счетчика end.
✎ Решение теоретическое:
Результат: 19
Результат: 19
Пошаговое аналитическое решение данного 16 задания ЕГЭ по информатике доступно в видеоуроке:
Видеорешение на RuTube здесь
16_12: Решение задания 16 (Поляков К., вариант 31):
Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(5)?
procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-2); F(n div 2); F(n div 2); end end;
DECLARE SUB F(n) SUB F(n) PRINT '*' IF n > 0 THEN F(n - 2) F(n \ 2) F(n \ 2) END IF END SUB
def F(n): print('*') if n > 0: F(n-2) F(n // 2) F(n // 2)
- В начале каждого вызова независимо от условия на экран выводится «звездочка». Кроме того, если условие n > 0 истинно, то функция вызывается еще три раза с разными аргументами. Таким образом, каждая функция выводит на экран либо одну звездочку (если условие ложно), либо 4 звездочки если условие истинно.
- Схематично рассмотрим вызов каждой функции, начиная с функции F(5). Дойдя до F(0), для которой условие будет ложно, будем подставлять полученное количество «звездочек», двигаясь опять к F(5):
Ответ: 34
16_4: ЕГЭ по информатике «Типовые экзаменационные варианты» 2019, ФИПИ, ВАРИАНТ 10 (Крылов С.С., Чуркина Т.Е.):
Ниже записаны две рекурсивные функции (процедуры): F и G.
Какова сумма чисел, напечатанных на экране при выполнении вызова F(17)?
procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin writeln(n); if n mod 2 =0 then F(n div 2) else G((n - 1) div 2); end; procedure G(n: integer); begin writeln (n); if n > 0 then F(n); end;
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) PRINT n IF n MOD 2 = 0 THEN F(n \ 2) ELSE G ( (n - 1) \ 2) END IF END SUB SUB G(n) PRINT n IF n > 0 THEN F(n) END IF END SUB
def F(n): print(n) if n % 2 == 0: F(n // 2) else: G((n - 1) // 2) def G(n): print(n) if n > 0: F(n)
✍ Решение:
procedure F(n: integer); forward; procedure G(n: integer); forward; var sum:=0; // сумматор procedure F(n: integer); begin writeln(n); sum+=n; // добавляем число в сумматор if n mod 2 =0 then F(n div 2) else G((n - 1) div 2); end; procedure G(n: integer); begin writeln (n); sum+=n; // добавляем число в сумматор if n > 0 then F(n); end; begin F(17); print('sum =',sum) end.
✎ Решение теоретическое:
Результат: 40
16_5, Источник: Поляков К, ВАРИАНТ 77
Ниже записаны две рекурсивные функции (процедуры): F и G.
Чему будет равно значение, вычисленное при выполнении вызова F(6)?
function F(n: integer):integer; forward; function G(n: integer):integer; forward; function F(n:integer):integer; begin if (n > 2) then F:= F(n - 1) + G(n - 2) else F:= n; end; function G(n:integer):integer; begin if (n > 2)then G:= G(n - 1) + F(n -2) else G:= n+1; end;
FUNCTION F(n) IF n > 2 THEN F = F(n - 1) + G(n - 2) ELSE F = n; END IF END FUNCTION FUNCTION G(n) IF n > 2 THEN G = G(n - 1) + F(n -2) ELSE G = n+1; END IF END FUNCTION
def F(n): if n > 2: return F(n - 1) + G(n - 2) else: return n def G(n): if n > 2: return G(n - 1) + F(n - 2) else: return n+1
int F(int n); int G(int n); int F(int n) < if (n >2) return F(n - 1) + G(n - 2); else return n; > int G(int n) < if (n >2) return G(n - 1) + F(n - 2); else return n + 1; >
✍ Решение:
Предлагаем посмотреть видеоразбор данного аналитического решения:
Видеорешение на RuTube здесь
С каким аргументом?
Вызов представленной ниже рекурсивной функции приводит к появлению на экране чисел и точек. С каким минимальным натуральным аргументом а нужно вызвать эту функцию, чтобы в результате на экране появилось 5 точек (не обязательно подряд, между точками могут встречаться числа)?
Паскаль:
✍ Решение:
procedure F(n: integer); forward; procedure G(n: integer); forward; var sum:=0; // сумматор procedure F(n: integer); begin writeln(n); sum+=n; // добавляем число в сумматор if n mod 2 =0 then F(n div 2) else G((n - 1) div 2); end; procedure G(n: integer); begin writeln (n); sum+=n; // добавляем число в сумматор if n > 0 then F(n); end; begin F(17); print('sum =',sum) end.
Результат: 6
Смотрите подробное аналитическое решение:
📹 Видеорешение на RuTube здесь (аналитическое)
Не актуально для компьютерного ЕГЭ
Все числа, которые будут напечатаны на экране, в том же порядке
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Паскаль:
procedure F(n: integer); begin if n > 0 then begin write(n); F(n - 3); F(n div 3) end end;
SUB F(n) IF n > 0 THEN PRINT n F(n - 3) F(n \ 3) END IF END SUB
def F(n): if n > 0: print(n) F(n - 3) F(n // 3)
Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
✍ Решение:
Результат: 9631231
Подробное решение 16 (11) задания демоверсии ЕГЭ 2018 года смотрите на видео:
📹 Видео 1 способ
📹 Видеорешение на RuTube здесь
2 способ:
📹 Видеорешение на RuTube здесь
16_7: Решение задания 16 (11) Информатика и ИКТ 2019 3 вариант (Крылов С.С, Чуркина Т.Е., 10 вариантов):
Ниже записан рекурсивный алгоритм F. Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(130).
Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
procedure F(n: integer); begin if n > 1 then begin write(n); F(n div 10); F(n - 40) end end;
16-е задание: «Вычисление рекуррентных выражений»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 9 минут.
Проверяемые элементы содержания: Вычисление рекуррентных выражений
Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ
Решение по рекуррентной формуле
Алгоритм вычисления значений функций F(n) и G(n) , где n – натуральное число, задан следующими соотношениями:
Чему равна сумма цифр значения F(18)?
Ответ: 46
function F(n: integer): integer; forward; function G(n: integer): integer; forward; function F(n: integer): integer; begin if n = 1 then F := 1 // или result := 1 else if n >= 2 then F := F(n - 1) + 3 * G(n - 1) // или result := F(n - 1) + 3 * G(n - 1) end; function G(n: integer): integer; begin if n = 1 then G := 1 // или result := 1 else if n >= 2 then G := F(n - 1) - 2 * G(n - 1) // или result := F(n - 1) - 2 * G(n - 1) end; begin var res := F(18); var s := 0; while res > 0 do begin s := s + (res mod 10); res := res div 10; end; print(s) end.
def F( n ): if n == 1: return 1 elif (n >= 2): return F(n-1)+3*G(n-1) def G( n ): if n == 1: return 1 elif (n >= 2): return F(n-1)-2*G(n-1) res = F(18) s = 0 while res > 0: s += res%10 res = res // 10 print(s)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
Чему равно значение функции F(5)? В ответе запишите только целое число.
Ответ: 840
function F(n: integer): integer; begin if n = 1 then F := 1 else if n > 1 then F := F(n - 1) * (n + 2) end; begin print(F(5)) end.
function F(n:integer):integer:= n=1 ? 1 : F(n-1) * (n+2); begin print(F(5)) end.
def F( n ): if n == 1: return 1 elif (n > 1): return F(n-1)*(n+2) print (F(5))
✎ Решение теоретическое (методом с конца к началу):
- Из условия задания мы имеем рекуррентную формулу: F(n–1) * (n + 2) и условие остановки рекурсии: n > 1.
- Поскольку рекуррентная формула уже задана, то остается подставить в нее начальный параметр — число 5:
- Теперь применим эту формулу для всех вызываемых вложенных функций, вплоть до F(1) (при котором «сработает» остановка рекурсии). Получим:
- На F(2) необходимо остановиться, так как действует условие остановки рекурсии: формула работает для n > 1. Также учтем, что по условию F(1) = 1.
- Теперь с конца к началу перепишем все получившиеся сомножители и перемножим их:
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
Чему равно значение функции F(6)? В ответе запишите только целое число.
Ответ: 99
function F(n:integer):integer; begin if (n = 0) or (n = 1) then result:=1 else if n>1 then result:=2*F(n-1) + F(n-2); end; begin print(F(6)) end.
✎ Решение 1. Теоретическое (метод решения с начала к концу):
✎ Решение 2. Теоретическое (метод решения с конца к началу):
- Поскольку рекуррентная формула уже задана, то остается подставить в нее начальный параметр — число 6:
- Теперь применим эту формулу для всех вызываемых вложенных функций, вплоть до F(2) (F(1) и F(0) известны из условия задачи). Получим:
- Теперь с конца к началу перепишем все получившиеся значения функций:
Видеорешение на RuTube здесь
Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
Чему равно значение величины F(5)/G(5)?
В ответе запишите только целое число.
Ответ: -2
function F(n: integer): integer; forward; function G(n: integer): integer; forward; function F(n:integer):integer; begin if n = 1 then result:=1 else if n>=2 then result:=F(n-1) - G(n-1); end; function G(n:integer):integer; begin if n = 1 then result:=1 else if n>=2 then result:=F(n-1) + 2*G(n-1); end; begin print(F(5)/G(5)) end.
✎ Решение теоретическое:
- Решим задание с вызова функций F(5) и G(5). Будем получать формулы последовательно для F(5), F(4), …, F(1), G(5), G(4), …, G(1). Дойдя до известных значений F(1) = 1 и G(1) = 1, подставим их в полученные формулы:
- Итого:
Что вернет функция. Сколько символов «звездочка». Какова сумма чисел
16_9: ЕГЭ по информатике 2020 задание 1 (Самылкина Н.Н., Синицкая И.В., Соболева В.В., «Тематические тренировочные задания»):
Что вернет функция F, если ее вызвать с аргументом 6?
function f(a:word):longword; begin if a>0 then f := f(a-1)*a; else f:=1; end;
FUNCTION F(a) IF a > 0 THEN F = F(a - 1) * a ELSE F = 1; END IF END FUNCTION
def F(a): if a > 0: return F(a - 1) * a else: return 1
int F(int a); int F(int a) < if (a >0) return F(a - 1) * a; else return 1; >
Ответ: 720
function f(a:word):longword; begin if a>0 then f := f(a-1)*a else f:=1; end; begin print(f(6)) end.
✎ Решение теоретическое:
Рассмотрим алгоритм функции:
ЕГЭ по информатике 2017 задание 16 (11) ФИПИ вариант 2 (Крылов С.С., Чуркина Т.Е.):
Ниже записаны две рекурсивные функции (процедуры): F и G.
Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(18)?
procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin write('*'); if n > 10 then F(n - 2) else G(n); end; procedure G(n: integer); begin write('**'); if n > 0 then F(n - 3); end;
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) PRINT "*" IF n > 10 THEN F(n - 2) ELSE G(n) END IF END SUB SUB G(n) PRINT "**" IF n > 0 THEN F(n - 3) END IF END SUB
def F(n): print("*") if n > 10: F(n - 2) else: G(n) def G(n): print("**") if n > 0: F(n - 3)
Шестнадцатое задание из ЕГЭ по информатике 2022 даётся на рекурсию.
Это задание нужно делать с помощью компьютера.
В программировании рекурсией называется процесс, когда функция вызывает сама себя или, когда две функции попарно вызывают друг друга.
Мы будем писать все программы на языке программирования Python.
Что такое Функция в языке программирования Python ?
Рассмотрим пример функции, которая суммирует два числа!
Здесь функция F, которая суммирует два числа.
В главной части программы запрашиваются два числа с клавиатуры: a и b! Эти два числа передаются в функцию F. В функции эти числа кладутся в локальные переменные x и y. Сумма переменных x и y записывается в переменную s. Переменная s возвращается, как результат работы функции F.
Результат работы функции будет помещён в переменную r (в строке r = F(a, b)) в основной части программы.
Таким образом, в переменной r будет сумма двух переменных a и b.
Функции позволяют сократить программный код для однотипных расчётов.
Тренировочные задачи 16 задания из ЕГЭ по информатике 2022
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 3 × F(n − 2), если n > 1 и при этом n – нечётно.
Чему равно значение функции F(25)?
Напишем программу для решения данной задачи. В начале опишем все правила, которые даны в условии задачи для функции. В основной части программы запустим эту функцию.
После запуска рекурсивной функции программа выведет ответ 531441.
Выражение n%2 != 0 (остаток от деления на "2" не равен нулю) обозначает нечётное число. Выражение n%2==0 обозначает чётное число.
Ответ: 531441
Продолжаем тренировку по подготовке к 16 заданию ЕГЭ по информатике 2022.
Задача (Продолжаем подготовку)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(2) = 3
F(n) = F(n–1) * n + F(n–2) * (n – 1) , при n > 2
Чему равно значение функции F(8)? В ответе запишите только натуральное число.
Ответ получается 148329.
Ответ: 148329
Закрепляющий пример на рекурсию 16 задания из ЕГЭ по информатике 2022.
Алгоритм вычисления значения функций F(n) и G(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 0, если n 2
Чему равно значение функции F(8)? В ответе запишите только натуральное число.
Получается ответ 9.
Задача (Количество значений)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 2*n*n*n + 1, при n > 25
F(n) = F(n+2) + 2*F(n+3), при n ≤ 25
Определите количество натуральных значений n из отрезка [1; 1000], для которых значение F(n) кратно 11.
В начале формируем функцию F. Затем перебираем числа из диапазона от 1 до 1000. Каждое число подставляем в функцию F. Если значение функции F делится на 11, то мы зачитываем такое значение i.
В ответе получается 91.
Задача (Используем глобальную переменную)
Решение:
При решении этой задачи можно применить глобальную переменную.
Здесь внутри функции заводим глобальную переменную s, которая будет подсчитывать количество напечатанных звёздочек. Теперь эту переменную видно при любом вызове функции, и при каждом вызове функции она будет одна и та же переменная. Вместо печати звёздочек пишем конструкцию s=s+1.
В основной части программы перед первым запуском функции переменной s присваиваем 0.
Программа может немного медленно работать из-за большой глубины рекурсии, но через минуту выведет число 96631265.
Продолжаем изучение демонстрационного варианта ЕГЭ по информатике 2022.
В этой статье разберём с 16-ого по 21 задание.
Желаю победы на ЕГЭ по информатике 2022!
Алгоритм вычисления значения функции 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)?
Запрограммируем эту задачу на Python'е.
Формируем функцию F, в точности, как нам предоставили описание. И запускаем функцию с указанным параметром 26.
Проверить чётное ли число n или нет, можно, посмотрев остаток от деления n на 2.
Ответ: 4122
В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от –10 000 до 10 000 включительно. Определите и запишите в ответе сначала количество пар элементов последовательности, в которых хотя бы одно число делится на 3, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности. Например, для последовательности из пяти элементов: 6; 2; 9; –3; 6 – ответ: 4 11
Решим задачу на языке Python. Файл должен быть в той же папке, в которой сохранили программу (или нужно прописать полный путь до файла).
В начале подключаем файл. Заводим переменные count, sm, где будут храниться количество пар и наибольшая сумма.
Считываем в n1 из файла первое число для нашей пары. Затем, формируем цикл for, где в переменную s считывается очередная строчка из файла, начиная со второй (ведь первая уже считалась в n1). Т.е. n1 - первое число из пары, n2 - второе число из пары.
Проверяем с помощью условия, делится ли хотя бы одно число из пары на 3. Если да, то прибавляем единицу к счётчику count. Так же, если выполняется условие, в переменную sm записывается максимальное значение между старым значением переменной sm и суммой очередной пары. Т.е. в переменной sm будет записана максимальная сумма элементов всех пар, которые удовлетворяют условию задачи.
В конце цикла кладём значение n2 в переменную n1, и всё повторяется.
Ответ:
2802 | 1990 |
Квадрат разлинован на N × N клеток (1
Отметим особым цветом те ячейки, которые "спрятаны" от движения Робота стенками.
Для этих ячеек будем составлять другие формулы, в отличии от обычных ячеек.
Цвет ячейки можно поменять, нажав на кнопку "Цвет заливки" на главной вкладке программы.
Т.к. Робот направляется из левой верхней ячейки, то мы сначала и напишем формулу для этой ячейки. Пишем для ячейки B22:
=МАКС( B21 ; A22 )+ B1
Робот в любую ячейку может прийти либо сверху, либо слева. Для подсчёта максимального количества монет, мы должны выбрать максимальное предыдущее значение. Это и делаем формула. Плюс Робот должен взять монеты с текущей клетки.
Распространим формулу на всё пространство, не трогая закрашенные клетки.
Получается такая картина:
В ячейки для первой закрашенной области, Робот может попасть только сверху! Поэтому пишем формулу для ячейки H25:
Распространяем формулу по всему закрашенному столбцу.
В ячейки для второй закрашенной области, Робот может попасть только слева! Поэтому пишем формулу для ячейки М39:
Распространяем формулу по всей закрашенной строчке.
В правом нижнем углу нашего рабочего пространства получается максимальное количество монет, которое может собрать Робот. В ячейке U41 получается число 721.
Чтобы получить минимальную возможную сумму, в главной формуле функцию МАКС нужно заменить на МИН!
Удобно воспользоваться автоматической заменой через Ctrl+F.
Минимальная сумма равна 640.
Ответ:
721 | 640 |
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 29 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 28.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решим задачу с помощью шаблона на языке программирования Python. Если хотите ознакомится с аналитическим решением задач на теорию игр, можете посмотреть мои статьи по 19 Заданию, 20 Заданию, 21 Заданию. Но с помощью шаблонов на экзамене решать быстрее и легче.
Введём параметр p, который будет олицетворять позицию игры (ход).
Начальная позиция | Ход Пети | Ход Вани | Ход Пети | Ход Вани | Ход Пети | |
p | 1 | 2 | 3 | 4 | 5 | 6 |
Заводим функцию F. Т.к. у нас одна куча, то она принимает параметры: x - количество камней в куче, p-позиция игры.
Дальше описываем победу. Если x>=29 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.
Если, позиция уже равна 3, но камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).
Третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.
Если мы не вышли на первых трёх условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F.
Для нечётных p (это ходы Вани), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае. При этом увеличиваем на 1 значение p.
Для чётных p (это ходы Пети), возвращаем ходы через or.
В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи.
Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задача точно такая же, как и в 19 задании, только теперь обязательно должен побежать Петя на своём втором ходу (p=4), при любой игре Вани.
Пишем тот же шаблон, немного отредактировав его.
Получается 7 и 13.
Ответ:
7 | 13 |
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите минимальное из них.
Опять используем прошлый шаблон, но немного модернизируем.
Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).
Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.
Читайте также: