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

Июль 24, 2022

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

Содержание

2. Пример: вычисление факториала Эквивалентные рекуррентные соотношения для n!: можно использовать для построения не только рекуррентного (на
3. Стек при рекурсивном спуске Последовательные вызовы рекурсивной функции с параметром n и возвращаемым значением f (условное
4. Стек при рекурсивном подъеме Состояние перед освобождением стека и возвратом в вызывающую функцию с передачей возвращаемого
5. Метод математической индукции 3 основных этапа метода математической индукции: 1) базис, 2) предположение, 3) индуктивный вывод.
6. Задача «Ханойские башни» Имеется три колышка: a, b, c. На колышке a расположено n дисков в
7. Иллюстрация для шага индукции
8. Рекурсивная функция void hanoi(int n, int a, int b, int c) { if (n == 1)
9. Рекуррентное соотношение для трудоемкости из которого получаем: H(n) = 2 H(n – 1) + 1 =
10. Рекурсивное вычисление чисел Фибоначчи int fib(int n) { if (!n) return 0; else if (n ==
12. Скачать презентацию

Слайд 2

Пример: вычисление факториала
Эквивалентные рекуррентные соотношения для n!:
можно использовать для построения не

только рекуррентного (на основе цикла), но и рекурсивного алгоритма (вычислить n! через (n-1)! и т.д.).
int fact(int n)
{
if (n <= 0) return 1;
else return fact(n-1) * n;
}
void main(…)
{
cout << fact(3);
}

Слайд 3

Стек при рекурсивном спуске
Последовательные вызовы рекурсивной
функции с параметром n и возвращаемым
значением

f (условное имя)
fact(3) fact(2) fact(1) fact(0)

Слайд 4

Стек при рекурсивном подъеме
Состояние перед освобождением стека и возвратом
в вызывающую

функцию с передачей возвращаемого значения f
fact(1) fact(2) fact(3)

Слайд 5

Метод математической индукции
3 основных этапа метода математической индукции:
1) базис, 2) предположение,

3) индуктивный вывод.
На этапе базиса проверяют, что доказываемое утверждение P(n) относительно параметра индукции n справедливо при n = n0.
На втором этапе делается предположение, что утверждение P(n) справедливо для всех значений n, не бóльших, чем некоторое k, k ≥ n ≥ n0.
На этапе индуктивного вывода доказывается, что P(n) будет справедливо при n = k + 1 > n0. Из этого следует, что утверждение P(n) справедливо для любого n ≥ n0.

Слайд 6

Задача «Ханойские башни»
Имеется три колышка: a, b, c. На колышке a

расположено n дисков в виде башни.
Задача: Переложить всю башню на колышек c, перекладывая по одному диску так, чтобы любой диск большего размера не лежал на меньшем диске.
Решение на основе математической индукции:
Базис. Число дисков n = 1. Переложить диск с колышка a на колышек c.
Предположение. Пусть алгоритм умеет перекладывать башни из n = k ≥ 1.
Индукция. Пусть n = k+1 ≥ 2. Перекладываем башню из k дисков с колышка a на колышек b, затем один диск с колышка a на колышек c и, наконец, башню из k дисков с колышка b на колышек c.

Слайд 7

Иллюстрация для шага индукции

Слайд 8

Рекурсивная функция
void hanoi(int n, int a, int b, int c)
{
if

(n == 1)
cout << a << “->” << c << endl;
else
{
hanoi(n-1, a, c, b);
cout << a << “->” << c << endl;
hanoi(n-1, b, a, c);
}
}
void main(…)
{
hanoi(6, 1, 2, 3); // 6 дисков с 1 на 3
}

Слайд 9

Рекуррентное соотношение для трудоемкости
из которого получаем:
H(n) = 2 H(n – 1) + 1 = 22H(n – 2) + 2 + 1 =
2n – 1 + 2n – 2 + … + 2 + 1 = 2n – 1.
Глубина рекурсии: n.
Если на

перекладывание одного диска тратить 1 секунду, то при n = 64 всю работу можно завершить за 264 сек ≈ 580 млрд. лет.

Слайд 10

Рекурсивное вычисление чисел Фибоначчи
int fib(int n)
{
if (!n) return 0;
else if

(n == 1) return 1;
else return fib(n-1) + fib(n-2);
}
Количество рекурсивных вызовов Rn и их связь с числами Фибоначчи Fn :
Rn : 1, 1, 3, 5, 9, 15, 25, 41, 67,...
Fn : 0, 1, 1, 2, 3, 5, 8, 13, 21,...
Rn = 2Fn+1 – 1

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

Содержание

Пример: вычисление факториалаЭквивалентные рекуррентные соотношения для n!:можно использовать для построения не

Стек при рекурсивном спускеПоследовательные вызовы рекурсивнойфункции с параметром n и возвращаемымзначением

Стек при рекурсивном подъемеСостояние перед освобождением стека и возвратом в вызывающую

Метод математической индукции3 основных этапа метода математической индукции:1) базис, 2) предположение,

Задача «Ханойские башни»Имеется три колышка: a, b, c. На колышке a

Иллюстрация для шага индукции

Рекурсивная функцияvoid hanoi(int n, int a, int b, int c){ if

Рекуррентное соотношение для трудоемкостииз которого получаем:H(n) = 2 H(n – 1) + 1 = 22H(n – 2) + 2 + 1 =2n – 1 + 2n – 2 + … + 2 + 1 = 2n – 1.Глубина рекурсии: n. Если на

Рекурсивное вычисление чисел Фибоначчи int fib(int n){ if (!n) return 0; else if

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