Рекурсивные алгоритмы

Июль 31, 2022

Главная
Информатика
Рекурсивные алгоритмы

Содержание

2. Рекурсивные алгоритмы Рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым
3. Пример задания из демоверсии Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими
4. Способы решения задания В6 В рекурсивных алгоритмах выделяются два способа их выполнения: 1)«погружение» алгоритма в себя,
5. Решение задания из демоверсии 1 способ F(1) = 1 F(n) = F(n–1) * n, при n
6. Решение задания из демоверсии 2 способ F(1) = 1 F(n) = F(n–1) * n, при n
7. Пример задания с сайта Полякова Алгоритм вычисления значения функции F(n), где n – натуральное число, задан
8. Пример задания с сайта ege.yandex.ru Последовательность чисел Фибоначчи задаётся рекуррентным соотношением: F(n)=F(n−1)+F(n−2) при натуральном n>2 F(1)=1
9. Пример задания с сайта ege.yandex.ru Максимальное число L(n) областей, на которые плоскость делится n прямыми, можно
10. Пример задания с сайта ege.yandex.ru Для подсчета минимального числа ходов в головоломке ханойская башня используется функция
11. Пример задания с сайта ege.yandex.ru Алгоритмы вычисления значений функции F(n) и Q(n), где n – натуральное
12. Пример с сайта Димы Гущина «Решу ЕГЭ» http://www.inf.reshuege.ru Последовательность чисел задаётся рекуррентным соотношением: F(1) = 0
14. Скачать презентацию

Слайд 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 – натуральное число.
Чему равно девятое число в этой последовательности? В ответе запишите только натуральное число.

Рекурсивные алгоритмы

Содержание

Рекурсивные алгоритмыРекурсия – это приём, позволяющий свести исходную задачу к одной

Пример задания из демоверсииАлгоритм вычисления значения функции F(n), где n –

Способы решения задания В6 В рекурсивных алгоритмах выделяются два способа их

Решение задания из демоверсии 1 способF(1) = 1F(n) = F(n–1) * n,

Решение задания из демоверсии 2 способF(1) = 1F(n) = F(n–1) * n,

Пример задания с сайта ПоляковаАлгоритм вычисления значения функции F(n), где n

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

Пример задания с сайта ege.yandex.ruМаксимальное число L(n) областей, на которые плоскость

Пример задания с сайта ege.yandex.ruДля подсчета минимального числа ходов в головоломке

Пример задания с сайта ege.yandex.ruАлгоритмы вычисления значений функции F(n) и Q(n),

Пример с сайта Димы Гущина «Решу ЕГЭ» http://www.inf.reshuege.ru Последовательность чисел задаётся рекуррентным

Похожие презентации