Меню
Разработки
Разработки  /  Информатика  /  Презентации  /  11 класс  /  Рекурсивные алгоритмы. 11 класс ЕГЭ

Рекурсивные алгоритмы. 11 класс ЕГЭ

Разбор заданий №11 "Рекурсивные алгоритмы" ЕГЭ
21.04.2020

Содержимое разработки

ЕГЭ_11_рекурсия. Рекурсивные алгоритмы Все подпрограммы в языке Паскаль (и функции, и процедуры) являются рекурсивными. Это означает, что внутри подпрограммы можно обращаться к самой подпрограмме. Подпрограмма – это поименованная или каким-либо образом обозначенная часть программы, которая может быть многократно вызвана из различных частей основной программы. Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие , по достижению которого дальнейшее обращение к подпрограмме не происходит.

ЕГЭ_11_рекурсия. Рекурсивные алгоритмы

Все подпрограммы в языке Паскаль (и функции, и процедуры) являются рекурсивными. Это означает, что внутри подпрограммы можно обращаться к самой подпрограмме.

Подпрограмма – это поименованная или каким-либо образом обозначенная часть программы, которая может быть многократно вызвана из различных частей основной программы.

Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие , по достижению которого дальнейшее обращение к подпрограмме не происходит.

2 . procedure F(n: integer); begin if n 2 then begin writeln(n); F(n - 3); F(n - 4) end end; Запишем все вызовы в виде дерева вызовов. F(n-3) F(n-4) 1 102 2 9 72 62 3 13 42 10 32 6 32 22 Программа_2 5 4 11 8 7 02 -12 02 -12 02 12 12 *10 10 *7 7 *4 4 *1 *0 *3 3 *0 *-1 *6 6 *3 3 *0 *-1 *2 10 7 4 3 6 3 " width="640"

Чему будет равна сумма чисел при F(10)?

После каждого вызова на экран выводится значение параметра функции, если выполняется условие  n2 .

procedure F(n: integer); begin if n 2 then begin writeln(n); F(n - 3); F(n - 4) end end;

Запишем все вызовы в виде дерева вызовов.

F(n-3)

F(n-4)

1

102

2

9

72

62

3

13

42

10

32

6

32

22

Программа_2

5

4

11

8

7

02

-12

02

-12

02

12

12

*10 10 *7 7 *4 4 *1 *0 *3 3 *0 *-1 *6 6 *3 3 *0 *-1 *2

10 7 4 3 6 3

2 2 6 72 62 42 8 7 3 5 32 32 22 4 12 10 + 7 + 4 + 3 + 6 + 3 = 33 " width="640"

F(n-3)

F(n-4)

1

102

2

6

72

62

42

8

7

3

5

32

32

22

4

12

10 + 7 + 4 + 3 + 6 + 3 = 33

0 then          G(n - 1); end;   procedure G(n: integer); begin      writeln('*');      if n 1 then          F(n - 3); end; Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11 )? Программа_3 Используя Forward-описания (предописания), вы можете делать процедуры или функции известными без фактического определения ее операторной части. F(11) G(10): * F(7) G(6): * F(3) G(2): * F(-1) 11 10 * 7 6 * 3 2 * -1 Ключевое слово forward переводится как опережающий, что следует понимать как опережающее объявление функции или процедуры, что подразумевает, что компилятор должен только проанализировать как вызывается эта функция и занести её имя в таблицу имен. " width="640"

Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.

procedure F(n: integer); forward;

procedure G(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;

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

Программа_3

Используя Forward-описания (предописания), вы можете делать процедуры или функции известными без фактического определения ее операторной части.

F(11)

G(10): *

F(7)

G(6): *

F(3)

G(2): *

F(-1)

11 10 * 7 6 * 3 2 * -1

Ключевое слово forward переводится как опережающий, что следует понимать как опережающее объявление функции или процедуры, что подразумевает, что компилятор должен только проанализировать как вызывается эта функция и занести её имя в таблицу имен.

0 F(n-3) n 1 110 101 * 7 0 * 6 1 3 0 * 2 1 -1 0 " width="640"

G(n-1) n 0

F(n-3) n 1

110

101

*

7 0

*

6 1

3 0

*

2 1

-1 0

Найти сумму чисел при вызове F(1)? Программа_4 procedure F(n: integer); begin write(n,' '); if n  F(n+1); F(n+3); end end; begin F(1); end. F(n+1) F(n+3) F(1) F(2) F(4) F(5) F(7) F(3) F(5) F(6) F(4) F(5) F(7) 1 +2 +3 + 4 +5 + 7 + 6 +5 + 4 +5 +7 = 49 1 *1 2 *2 3 *3 4 *4 5 7 6 5 4 *4 5 7

Найти сумму чисел при вызове F(1)?

Программа_4

procedure F(n: integer);

begin

write(n,' ');

if n

F(n+1);

F(n+3);

end

end;

begin

F(1);

end.

F(n+1)

F(n+3)

F(1)

F(2)

F(4)

F(5)

F(7)

F(3)

F(5)

F(6)

F(4)

F(5)

F(7)

1 +2 +3 + 4 +5 + 7 + 6 +5 + 4 +5 +7 = 49

1 *1 2 *2 3 *3 4 *4 5 7 6 5 4 *4 5 7

0 then begin F(n-2); F(n div 2); end end; begin F(5); end. F(n-2) F(n div 2) F(5) * * F(3) * F(2) * * * F(1) F(1) F(1) F(1) * F(0) F(0) F(-1) F(-1) F(0) F(-1) * * * * * * procedure F(n: integer); begin write('*',n,' '); if n0 then begin F(n-2); F(n div 2); end end; begin F(5); end. * 5 * 3 * 1 * -1 * 0 * 1 * -1 * 0 * 2 * 0 * 1 * -1 * 0 " width="640"

Сколько символов звездочка выведется на экран при F(5)?

Программа__5

procedure F(n: integer);

begin

write('*');

if n0 then begin

F(n-2);

F(n div 2);

end

end;

begin

F(5);

end.

F(n-2)

F(n div 2)

F(5)

*

*

F(3)

*

F(2)

*

*

*

F(1)

F(1)

F(1)

F(1)

*

F(0)

F(0)

F(-1)

F(-1)

F(0)

F(-1)

*

*

*

*

*

*

procedure F(n: integer);

begin

write('*',n,' ');

if n0 then begin

F(n-2);

F(n div 2);

end

end;

begin

F(5);

end.

* 5 * 3 * 1 * -1 * 0 * 1 * -1 * 0 * 2 * 0 * 1 * -1 * 0

1 then begin F(n-4); if n1 then begin F(n-4); write(n,' '); write(n,' '); F(n div 2); end; F(n div 2); end; end; end; begin F(11); begin end. F(11); end. 3 7 3 11 5 2 *11 *7 *3 *-1 3 *1 7 *3 *-1 3 *1 11 *5 *1 5 *2 *-2 2 *1 " width="640"

Что буде напечатано при выполнении F(11)?

Программа_6

procedure F(n: integer);

procedure F(n: integer);

begin

begin

write('*',n,' ');

if n1 then begin

F(n-4);

if n1 then begin

F(n-4);

write(n,' ');

write(n,' ');

F(n div 2);

end;

F(n div 2);

end;

end;

end;

begin

F(11);

begin

end.

F(11);

end.

3 7 3 11 5 2

*11 *7 *3 *-1 3 *1 7 *3 *-1 3 *1 11 *5 *1 5 *2 *-2 2 *1

1 + F(7) 71 + F(3) 31 + F(-1) -11 - F(1) 11 - F(3) 31 + F(-1) -11 - procedure F(n: integer); begin if n1 then begin F(n-4); write(n,' '); F(n div 2); end; end; begin F(11); end. F(1) 11 - F(5) 51 + F(1) 11 - F(2) 21 + F(-2) -21 - F(1) 11 - *11 *7 *3 *-1 3 *1 7 *3 *-1 3 *1 11 *5 *1 5 *2 *-2 2 *1 " width="640"

F(n - 4)

F(n div 2)

F(11)

111 +

F(7)

71 +

F(3)

31 +

F(-1)

-11 -

F(1)

11 -

F(3)

31 +

F(-1)

-11 -

procedure F(n: integer);

begin

if n1 then begin

F(n-4);

write(n,' ');

F(n div 2);

end;

end;

begin

F(11);

end.

F(1)

11 -

F(5)

51 +

F(1)

11 -

F(2)

21 +

F(-2)

-21 -

F(1)

11 -

*11 *7 *3 *-1 3 *1 7 *3 *-1 3 *1 11 *5 *1 5 *2 *-2 2 *1

1 then begin F(n-4); write(n,' '); F(n div 2); end; end; begin F(11); end. 11 7 5 2 3 3 1 1 -1 -2 1 1 -1 *11 *7 *3 *-1 3 *1 7 *3 *-1 3 *1 11 *5 *1 5 *2 *-2 2 *1 " width="640"

procedure F(n: integer);

begin

write('*',n,' ');

if n1 then begin

F(n-4);

write(n,' ');

F(n div 2);

end;

end;

begin

F(11);

end.

11

7

5

2

3

3

1

1

-1

-2

1

1

-1

*11 *7 *3 *-1 3 *1 7 *3 *-1 3 *1 11 *5 *1 5 *2 *-2 2 *1

0 then begin 1 F(n-1); 2 write(n,' '); 3 F(n - 2); end; end; begin F(4); end. 4 2 3 F(4) F(2) F(3) 2 1 F(2) 1 F(1) F(1) F(0) 1 F(1) F(0) F(-1) F(0) F(-1) F(0) procedure F(n: integer); begin write('*',n,' '); if n0 then begin F(n-1); write(n,' '); F(n - 2); end; end; begin F(4); end. F(0) F(-1) *4 *3 *2 *1 *0 1 *-1 2 *0 3 *1 *0 1 *-1 4 *2 *1 *0 1 *-1 2 *0 1 2 3 1 4 1 2 " width="640"

Что буде напечатано при выполнении F(4)?

F(n-1)

F(n-2)

procedure F(n: integer);

begin

if n0 then begin

1 F(n-1);

2 write(n,' ');

3 F(n - 2);

end;

end;

begin

F(4);

end.

4

2

3

F(4)

F(2)

F(3)

2

1

F(2)

1

F(1)

F(1)

F(0)

1

F(1)

F(0)

F(-1)

F(0)

F(-1)

F(0)

procedure F(n: integer);

begin

write('*',n,' ');

if n0 then begin

F(n-1);

write(n,' ');

F(n - 2);

end;

end;

begin

F(4);

end.

F(0)

F(-1)

*4 *3 *2 *1 *0 1 *-1 2 *0 3 *1 *0 1 *-1 4 *2 *1 *0 1 *-1 2 *0

1 2 3 1 4 1 2

Чему равна сумма чисел, выведенных на экран при вызове F(2)? procedure F(n: integer); procedure F(n: integer); begin begin write(n,' '); write(n,' '); if n if n write( '*' ,n,' '); write(n,' '); F(n+1); F(n+1); F(n+2); F(n+2); F(n*2); F(n*2); end end end; end; begin begin F(2); F(2); end. end. Программа  2 *2 3 *3 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8

Чему равна сумма чисел, выведенных на экран при вызове F(2)?

procedure F(n: integer);

procedure F(n: integer);

begin

begin

write(n,' ');

write(n,' ');

if n

if n

write( '*' ,n,' ');

write(n,' ');

F(n+1);

F(n+1);

F(n+2);

F(n+2);

F(n*2);

F(n*2);

end

end

end;

end;

begin

begin

F(2);

F(2);

end.

end.

Программа

2 *2 3 *3 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8

n*2 n+1 n+2 If n 2 *2 3 *3 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 2+3+4+5+6 +7+8+12+7+10 +6+7+8 +12+8+5+6+7+8+12+7+10+6 +7+8 +12+4 +5 +6 +7+8+12+7+10+6 +7+8+12+8+4+5+6 +7+8+12+7+10+6+7+8+12+8=393 – сумма, первый write перед if  3+4+4+4+5+6+5+6+5+6+5+6+6+6+6+6=85 – сумма, второй write, который печатает все числа

n*2

n+1

n+2

If n

2 *2 3 *3 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8 4 *4 5 *5 6 *6 7 8 12 7 10 6 *6 7 8 12 8

2+3+4+5+6 +7+8+12+7+10 +6+7+8 +12+8+5+6+7+8+12+7+10+6 +7+8 +12+4 +5 +6 +7+8+12+7+10+6 +7+8+12+8+4+5+6 +7+8+12+7+10+6+7+8+12+8=393 – сумма, первый write перед if

3+4+4+4+5+6+5+6+5+6+5+6+6+6+6+6=85 – сумма, второй write, который печатает все числа

-80%
Курсы повышения квалификации

Внедрение современных педагогических технологий в условиях реализации ФГОС (в предметной области «Информатика»)

Продолжительность 72 часа
Документ: Удостоверение о повышении квалификации
4000 руб.
800 руб.
Подробнее
Скачать разработку
Сохранить у себя:
Рекурсивные алгоритмы. 11 класс ЕГЭ (313.89 KB)

Комментарии 0

Чтобы добавить комментарий зарегистрируйтесь или на сайт

Учителю!
Огромная база учебных материалов на каждый урок с возможностью удаленного управления
Тесты, видеоуроки, электронные тетради