Презентация на тему "Решение задач ЕГЭ типа В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

• 
  Слайд 4
  

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

• 
  Слайд 5
  

  Задача 2. ИНФОРМАТИКА 2014г. Кирсанов Илья Андреевич © Решение1. сначала определим рекуррентную формулу; обозначим через G(n) количество звездочек, которые выводит программа при вызове F(n) из программы видим, что G(n) = 1 при всех n 0 вспомним, что ndiv 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)