Задача №3 (ЕГЭ 2016 (Ушаков), вар.11)

Begin

<операторы>

End;

Для вызова процедуры достаточно указать ее имя со списком фактических параметров.

Функция — подпрограмма, имеющая единственный результат, записываемый в ячейку памяти, имя которой совпадает с именем функции.

function <имя_функции>(<описание входных данных>)<тип функции>;

Begin

<операторы>

<имя_функции>:=<результат>

End;

Для вызова функции, ее имя со списком параметров можно использовать в любом выражении, в условиях, в некоторых операторах главной программы.

Рекурсивная функция -это такая функция, в которой реализован способ вычисления очередного значения функции через вычисление ее предшествующих значений. Это прямая рекурсия.(смотри задача1, задача3 и задача4)

Косвенной называется рекурсия, когда две или более процедуры или функции вызывают друг друга. Пример косвенного вызова процедуры или функции: процедура A вызывает процедуру B, а процедура B вызывает процедуру A.(задача 2).

Понятие рекурсивной функции тесно связано с понятием стек. Это «разновидность списка, в котором любой доступ производится только на одном из его концов, который называется вершиной стека. Иногда стек называют списком LIFO(Last In – First Out - последний вошел, первым вышел).

Механизм стека напоминает железнодорожный тупик, из которого первым может выехать только поезд, въехавший в него последним.»[1] или его можно сравнить с пачкой документов, в которой в любой момент доступен только верхний документ. Можно положить поверх пачки еще один документ, который сделает недоступным документ, лежащий под ним, или снять верхний документ с пачки, открыв доступ к нижележащему.

Рекурсивые функции работают по принципу стека: пока не закончится процесс последней вызванной программы, предыдущие выполняться не могут и находяться в состоянии ожидания. Рассмотрим задачи №11 из включенных в ЕГЭ, решение которых невозможно без понятия рекурсии.

 

Задача №1(ЕГЭ 2017, вар.12)

Записана рекурсивная функция(процедура) F.

Procedure F (n:integer);

Begin

write(n);

If n>2 then begin

F(n-1);

F(n-2);

F(n-3)

End

End;

 

Что выведет программа при вызове F(4)?

Решение:

Решение будем представлять в виде таблицы и в виде схемы.

F(n)	Что печатает?	Проверка условия	Возврат к каким функциям будет возврат по порядку?
F(4)		n>2, выполняется	F(3); F(2); F(1);
F(3)		N>2 выполняется	F(2); F(1); F(0);
F(2)		N=2 не выполняется	Тело цикла не выполняться
F(1)		n<2 не выполняется	Тело цикла не выполняться
F(0)		N<2 не выполняется	Тело цикла не выполняться Конец выполнения F(3). Возврат к F(4)
F(2)		N=2 не выполняется	Тело цикла не выполняться
F(1)		N=1 не выполняется	Тело цикла не выполняться Конец выполнения F(4)

Больше процедура выполняться не будет. Программа завершится.

Ответ: 432021

Задача №2 (Демо 2016)

Записаны две рекурсивные функции F и G.

Procedure G (n:integer);forward;

Procedure F (n:integer);forward;

Procedure F (n:integer);

Begin

If n>0 then G(n-1);

End;

Procedure G (n:integer);

Begin

writeln(‘*’);

if n>1 then F(n-3);

End

End;

Сколько символов «*» будет напечатано на экране при выполнении вызова F(11)?

Решение:

Решение будем представлять в виде таблицы и в виде схемы.

F(n)	Что печатает?	Проверка условия	Возврат к каким функциям будет возврат по порядку?
F(11)		11>0, выполняется	G(10)
G(10)	*	10>1выполняется	F(7)
F(7)		7>0,выполняется	G(6)
G(6)	*	6>1,выполняется	F(3)
F(3)	-	3>0,выполняется	G(2)
G(2)	*	2>1выполняется	F(-1)
F(-1)	-	-1<0 не выполняется	Тело цикла не выполняться Процесс возвращается к функции G(2)

Больше процедура выполняться не будет. Программа завершится.

Ответ: 3

Задача №3 (ЕГЭ 2016 (Ушаков), вар.11)

Определите, сколько звездочек будет напечатано в результате вызова F(5) приведенной подпрограммы:

Procedure F (n:integer);

Begin

If n>1 then begin

F(n div 2);

F(n-1);

End;

write('*');

End;

Решение:

Решение будем представлять в виде таблицы и в виде схемы.

F(n)	Проверка условия	Возврат к каким функциям будет возврат по порядку?	Что печатает?
F(5)	n>1, выполняется	F(2); F(4);	*. Алгоритм закончился
F(2)	n>1 выполняется	F(1); F(1);	*
F(1)	n=1 не выполняется	Тело цикла не выполняться. Возврат к F(2)	*
F(1)	n=1 не выполняется	Тело цикла не выполняться. Возврат к F(2)	*
F(4)	n>1 выполняется	F(2); F(3);	*.возврат в F(5)
F(2)	n>1 выполняется	F(1); F(1)	*
F(1)	n=1 не выполняется	Тело цикла не выполняться. Возврат к F(2)	*
F(1)	n=1 не выполняется	Тело цикла не выполняться. Возврат к F(2)	*
F(3)	n>1 выполняется	F(1); F(2)	* возврат в F(4)
F(1)	n=1 не выполняется	Тело цикла не выполняться. Возврат к F(3)	*
F(2)	n>1 выполняется	F(1); F(1)	*
F(1)	n=1 не выполняется	Тело цикла не выполняться. Возврат к F(2)	*
F(1)	n=1 не выполняется	Тело цикла не выполняться. Возврат к F(2)	*

 

Программа завершилась.

Считаем количество «*».

Ответ: 13

 

Задача №4 (ЕГЭ 2017, вар.20)

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

F(1)=1

F(2)=1

F(n)=2F(n-1) + F(n-2), при n>2.

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

Решение:

F(5) = 2F(4) + F(3)

F(4) = 2F(3) + F(2)

F(3) = 2F(2) + F(1) = 2*1 + 1 = 3

F(4) = 2*3 + 1 = 7

F(5) = 2*7 + 3

= 17

Ответ: 17

Разбор заданий № 21.

Для решения задач данного задания необходимо владение основами анализа функций в пределах курса математики средней школы. Рассмотрим некоторые стандартные варианты.

Задача №1 (ЕГЭ 2017, вар.12)

Найти наименьшее значение k, при котором программа выдает тот же ответ, что при k=20.

Var k,i: longint;

function f (n: longint): longint;

begin

f:=n*n*n;

end;

function g (n: longint): longint;

begin

g:=3*n-2;

end;

begin

readln(k);

I:=1;

while f(i)<g(k) do

i:=i+1;

writeln(i);

end.

Решение:

1. Найдем значение I, которое напечатает программа при вводе k=20.
Цикл повторится до тех пор, пока f(i) не станет больше или равным g(20), а это равно g(20)= 3*20-2=58. Следовательно, f(i) станет большим или равным 58 при i = 4, так как f(i)= i*i*i =64 при i =4. При i = 3 (f(i)=27) ответ не будет соответствовать условию задачи.

2. По результатам анализа программы, проведенному в п.1, видим, что число к, которое удовлетворяет условию найдем из неравенства:

27<g(k)<=64.

3. Наименьшее значение, которое удовлетворяет этому условию g(k)=28. Откуда находим, 3*k-2=28
3*k=30
k=10.
Ответ: 10

Задача №2 (ЕГЭ 2017, вар.18)

Дан алгоритм:

Var a,b,t,R: integer;

function F (x: integer): integer;

begin

F:=-3*(x+2)*x;

end;

begin

a:=-10; b:=10;

R:=F(a);

for t:=a to b do

begin

if (F(t)<R) then begin

R:= F(t);

end;
writeln(R);
end.

Какое число будет напечатано в результате выполнения алгоритма?

Решение:

1. Проанализируем функцию F(х). F(х):=-3*(x+2)*x квадратичная и имеет два корня х=-2 и х=0. F'(х):=-6*x-6, из которого х_max =-1, при этом значение F_max(-1):= 3. График функции — парабола, ветви которой направлены вниз.

2. Рассмотрим значения F(х).и R вблизи критических точек:
- При t=-10, начало цикла. F(x)=R и условие выполняться не будет. И

3. R =F(-10)=-240. Затем функция возрастает и условие R <F(x) до достижения максимума функции F(x).
- При t=-1, функция F(x) будет иметь максимальное значение равное и начинает уменьшаться до значения F(x)=-240, при x=8. В этом случае значения сравняются, F(x)=R,

4. При х=9, F(x)=-3*(9+2)*9= -297. Это значение уже меньше, чем -240, поэтому условие выполняется и значение R станет равным -297.

5. При х=10, F(x)=-3*(10+2)*10= -360. Это значение так же меньше, чем -297, поэтому условие выполняется и R примет значение равное -360.

6. При х=11 цикл уже не выполняется, а значит будет напечатано значение R=-360.

Ответ: -360

Задача №3 (ЕГЭ 2017, вар.10)

Найти наибольшее значение входной переменной k, при котором программа выдает тот же ответ, что при k=9.

Var k,i: longint;

function f (n: longint): longint;

begin

f:=-n*(n+1);

end;

function g (n: longint): longint;

begin

g:=-2*n+2;

end;

begin

readln(k);

i:=1;

while f(i)>g(k) do

i:=i+1;

writeln(i);

end.

Решение:

1. Найдем значение I, которое будет напечатает программа при вводе k=9.
Цикл повторится до тех пор, пока f(i) не станет больше или равным g(9).
Рассчитаем g(9)= -2*9+2=-16.

2. При i=1, F(1)=-2. Условие выполняется и цикл работает.

3. При i=2, F(2)=-6.Условие также должно выполняться. -6>-16.

4. При i=3, F(3)=-12.Условие также должно выполняться. -12>-16.

5. При i=4, F(4)=-20.Условие не выполняется, так как -20<-16.
6. Следовательно, f(i) станет меньше или равно -16 при i =4 (f(i)=64).
При i = 5 ответ не будет соответствовать условию задачи.

7. По результатам анализа программы, проведенному в п.1, видим, что число к, которое удовлетворяет условию найдем из неравенства:

-30<g(k)<=-20. Наибольшее значение, которое удовлетворяет этому условию g(k)=-20. Откуда находим,
-2*k+2=-20
-2*k=-22
k=11.
Ответ: 11

 

 

Список литературы

1. «ОГЭ. Информатика: универсальный справочник»/Дьячкова О.В. - Москва:Эксмо, 2016.