Решение задач ЕГЭ типа В6
материал для подготовки к егэ (гиа) по информатике и икт (11 класс) на тему

Слайд 1

ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Рекурсивные алгоритмы . В6 Разбор задач ЕГЭ

Слайд 2

Задача 1. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Последовательность чисел Фибоначчи задается рекуррентным соотношением: F(1) = 1 F(2) = 1 F( n ) = F( n –2) + F( n –1), при n >2, где n – натуральное число. Чему равно девятое число в последовательности Фибоначчи? В ответе запишите только натуральное число. Решение. F(3) = F(1) + F(2) = 2, F(4) = F(2) + F(3) = 3, F(5) = F(3) + F(4) = 5, F(6) = F(4) + F(5) = 8, F(7) = F(5) + F(6) = 13, F(8) = F(6) + F(7) = 21, F(9) = F(7) + F(8) = 34. Ответ 34

Слайд 3

Задача 1. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение. Условие k < 13 проверяется сразу после k:=k+4, следовательно, действие s:=s+2*k для k=16 выполняться не будет. s+k = 49 +1 6 = 65 Ответ 65 Шаг S= K= 1 1+2*0=1 0+4=4 2 1+2*4=9 4 +4= 8 3 9+2* 8 = 2 5 8 +4= 12 4 25+2*12=49 12+4=16

Слайд 4

Задача 2 . ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Дан рекурсивный алгоритм: procedure F( n : integer ); begin writeln ('*'); if n > 0 then B egin F(n-2); F( n div 2) end ; end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

Слайд 5

Задача 2 . ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение 1. сначала определим рекуррентную формулу; обозначим через G( n ) количество звездочек, которые выводит программа при вызове F( n ) из программы видим, что G ( n ) = 1 при всех n <= 0 G(n) = 1 + G(n-2) + G(n div 2) при n > 0 вспомним, что n div 2 – это частное от деления n на 2 по этим формулам заполняем таблицу, начиная с нуля: G(0) = 1 G(1) = 1 + G(-1) + G( 0) = 1 + 1 + 1 = 3 G( 2 ) = 1 + G( 0 ) + G( 1) = 1 + 1 + 3 = 5 G( 3 ) = 1 + G( 1 ) + G( 1) = 1 + 3 + 3 = 7 G( 4 ) = 1 + G( 2 ) + G( 2) = 1 + 5 + 5 = 11 G( 5 ) = 1 + G( 3 ) + G( 2) = 1 + 7 + 5 = 13 G( 6 ) = 1 + G( 4 ) + G( 3) = 1 + 11 + 7 = 19 G( 7 ) = 1 + G( 5 ) + G( 3) = 1 + 13 + 7 = 21 Ответ 21

Слайд 6

Задача 2 . ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение2(«с конца») . пп . 1-3 – как в варианте 1 по формулам G(7) = 1+ G(5) + G(3), поэтому нужно найти G(5) и G(3) G (5) = 1 + G (3) + G (2), нужны G (3) и G (2) G(3) = 1 + G(1) + G(1), нужно G(1) G (2) = 1 + G (0) + G (1) = 2 + G (1), нужно G (1) G(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3 теперь идем «обратным ходом»: G(2) = 2 + G(1) = 5 G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7 G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13 G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21 Ответ 21

Слайд 7

G(0) выведет одну звёздочку « * » , G(-1) выведет одну звёздочку « * » , отметим все звездочки (зелёным) и посчитаем их количество, получим ответ: 21. Задача 2 . ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение3(построение графа) . Ответ 21

Слайд 8

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Дан рекурсивный алгоритм: procedure F(n: integer); begin writeln ('*'); if n > 0 then begin writeln ('*'); F(n-2); F(n div 2); end; end; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? Ответ 31

Слайд 9

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Дан рекурсивный алгоритм: procedure f(n:integer); begin writeln (n); if n>0 then begin f(n-2); f(n-3); end; end; Найти сумму всех чисел которые выведет программа при вызове F(7)? Ответ 17

Слайд 10

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Алгоритм вычисления значения функции F( n ) и G( n ), где n – натуральное число, задан следующими соотношениями: F(1) = 1 F( n ) = 2 * G( n –1) + 5 * n , при n >1 G(1) = 1 G( n ) = F( n –1) + 2 * n , при n >1 Чему равно значение функции F(4) + G(4)? В ответе запишите только натуральное число. Ответ 89

Слайд 11

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Последовательность чисел трибоначчи задается рекуррентным соотношением: F(1) = 0 F(2) = 1 F(3) = 1 F( n ) = F( n –3) + F( n –2) + F( n –1), при n >3, где n – натуральное число. Чему равно одиннадцатое число в последовательности трибоначчи ? В ответе запишите только натуральное число. Ответ 149

Слайд 12

Вопросы. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © F(1) = 1, F(2) = 3, F(3) = 6, F(4) = 10, .... F(40) =? Что это за функция? Как можно её представить в виде рекуррентного соотношения? Ответ 820 Ответ Э то сумма n членов арифметической прогрессии . F(n)= n+F (n-1)