Презентация на тему: Рекурсивные алгоритмы

Рекурсивные алгоритмы
Рекурсивные алгоритмы
Примеры рекурсивных алгоритмов
Примеры рекурсивных алгоритмов
Задачи для тренировки (запишите пошаговое решение и ответ)
Рекурсивные алгоритмы
Рекурсивные алгоритмы
1/7
Средняя оценка: 4.7/5 (всего оценок: 67)
Код скопирован в буфер обмена
Скачать (497 Кб)
1

Первый слайд презентации: Рекурсивные алгоритмы

ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ

Изображение слайда
2

Слайд 2: Рекурсивные алгоритмы

Алгоритм называется рекурсивным, если на каком-­либо шаге он прямо или косвенно обращается сам к себе. В рекурсивном определении должно присутствовать ограничение (граничное условие), при выходе на которое дальнейшая инициация рекурсивных обращений прекращается. ! Ночь, улица, фонарь, аптека, Бессмысленный и тусклый свет. Живи еще хоть четверть века – Все будет так. Исхода нет. Умрешь – начнешь опять сначала И повторится все, как встарь: Ночь, ледяная рябь канала, Аптека, улица, фонарь. А. Блок

Изображение слайда
3

Слайд 3: Примеры рекурсивных алгоритмов

Пример 1. Числа Фибоначчи – элементы последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …, в которой первые два числа равны 1, а каждое следующее число равно сумме двух предыдущих чисел. Запишите рекуррентное определение чисел Фибоначчи. Ответ: F ( n ) = 1 при n ≤ 2 ; F ( n ) = F ( n -1 ) + F ( n -2 ) при n > 2. Это можно проверить так: F(1)=1 F(2)=1 F(3)=F(3-1)+F(3-2)=F(2)+F(1)=1+1=2 F(4)=F(4-1)+F(4-2)=F(3)+F(2)=2+1=3 F(5)=F(5-1)+F(5-2)=F(4)+F(3)=3+2=5 и т.д. Из первого условия Из второго условия

Изображение слайда
4

Слайд 4: Примеры рекурсивных алгоритмов

Пример 4. Алгоритм вычисления значения функции F ( n ), где n – натуральное число, задан следующими соотношениями: F ( 1 ) = 2; F ( n ) = n ∙ F ( n – 1) при n > 1. Определите значение функции F ( 6 ). Решение: F ( 1 ) = 2 F ( 2 ) = 2 ∙ F ( 1 ) = 2 ∙ 2 = 4 F ( 3 ) = 3 ∙ F ( 2 ) = 3 ∙ 4 = 12 F ( 4 ) = 4 ∙ F ( 3 ) = 4 ∙ 12 = 48 F ( 5 ) = 5 ∙ F (4) = 5 ∙ 48 = 240 F ( 6 ) = 6 ∙ F (5) = 6 ∙ 240 = 1440 Ответ: 1440 Из первого условия Из второго условия

Изображение слайда
5

Слайд 5: Задачи для тренировки (запишите пошаговое решение и ответ)

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

Изображение слайда
6

Слайд 6

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

Изображение слайда
7

Последний слайд презентации: Рекурсивные алгоритмы

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

Изображение слайда