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

Слайд 1

Слайд 2

Рекурсивные алгоритмы Рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа. Чтобы определить рекурсию, нужно задать условие остановки рекурсии (базовый случай или несколько базовых случаев), рекуррентную формулу. Алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма. Любую рекурсивную процедуру можно запрограммировать с помощью цикла.

Слайд 3

Пример задания из демоверсии Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(1) = 1 F(n) = F(n–1) * n, при n > 1 Чему равно значение функции F(5)? В ответе запишите только натуральное число.

Слайд 4

Способы решения задания В6 В рекурсивных алгоритмах выделяются два способа их выполнения: 1)«погружение» алгоритма в себя, то есть использование определения «в другую сторону», пока не будет найдено начальное определение, не являющееся рекурсивным; 2)последовательное выполнение операций от начального определения до определения с введенным в алгоритм значением.

Слайд 5

Решение задания из демоверсии 1 способ F(1) = 1 F(n) = F(n–1) * n, при n > 1 1). используя заданную рекуррентную формулу, находим, что F(5) = F(4) * 5 2). применив формулу еще несколько раз, получаем F(5) = F( 3 ) * 4 * 5 = F(2) * 3 * 4 * 5 = F(1) * 2 * 3 * 4 * 5 3) мы дошли до базового случая, который останавливает рекурсию, так как определяет значение F(1) = 1 4) окончательно F(5) = 1 * 2 * 3 * 4 * 5 = 120 Ответ: 120.

Слайд 6

Решение задания из демоверсии 2 способ F(1) = 1 F(n) = F(n–1 ) * n, при n > 1 F(2) = F(1)*2 = 1*2 = 2 F(3) = F(2)*3 = 2*3=6 F(4) = F(3)*4 = 6*4 = 24 F(5) = F(4)*5 = 24*5 = 120 Ответ: 120.

Слайд 7

Пример задания с сайта Полякова Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F (1) = 1, F (2) = 1 F ( n ) = F ( n -2)* ( n -1) + 2, при n > 2 Чему равно значение функции F(8)? В ответе запишите только натуральное число.

Слайд 8

Пример задания с сайта ege . yandex . ru Последовательность чисел Фибоначчи задаётся рекуррентным соотношением: F ( n )= F ( n −1)+ F ( n −2) при натуральном n >2 F (1)=1 F (2)=1 Чему равно восьмое число в последовательности Фибоначчи? В ответ запишите только натуральное число.

Слайд 9

Пример задания с сайта ege . yandex . ru Максимальное число L ( n ) областей, на которые плоскость делится n прямыми, можно вычислить с помощью рекуррентного соотношения: L ( n )= L ( n −1)+ n при натуральных n ≥1 L (0)=1 Каково максимальное число областей, на которые плоскость делится десятью прямыми?

Слайд 10

Пример задания с сайта ege . yandex . ru Для подсчета минимального числа ходов в головоломке ханойская башня используется функция S ( n ), которая вычисляется по следующему алгоритму: S ( n )=2* S ( n −1)+1 при натуральном n >1 S (1)=1 Чему равно значение функции S (7)? В ответ запишите только натуральное число.

Слайд 11

Пример задания с сайта ege . yandex . ru Алгоритмы вычисления значений функции F ( n ) и Q ( n ), где n – натуральное число, заданы следующими соотношениями: F ( n )= F ( n −1)+2* Q ( n −1) при n >1 F (1)=1 Q ( n )=−2* F ( n −1)+ Q ( n −1) при n >1 Q (1)=1 Чему равно значения функций F (5)+ Q (5)? В ответ запишите только число.

Слайд 12

Пример с сайта Димы Гущина «Решу ЕГЭ» http:// www .inf.reshuege.ru Последовательность чисел задаётся рекуррентным соотношением: F(1) = 0 F(2) = 1 F(3) = 1 F(n) = F(n–3) + F(n–2) + F(n–1), при n >3, где n – натуральное число. Чему равно девятое число в этой последовательности? В ответе запишите только натуральное число.

Слайд 13

Вывод Задача на выполнение рекурсивных алгоритмов не представляет сложности, если учащийся понимает, что означают записанные формулы и как их применять.