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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Основы программирования. Рекурсивные алгоритмы, слайд №1Основы программирования. Рекурсивные алгоритмы, слайд №2Основы программирования. Рекурсивные алгоритмы, слайд №3Основы программирования. Рекурсивные алгоритмы, слайд №4Основы программирования. Рекурсивные алгоритмы, слайд №5Основы программирования. Рекурсивные алгоритмы, слайд №6Основы программирования. Рекурсивные алгоритмы, слайд №7Основы программирования. Рекурсивные алгоритмы, слайд №8Основы программирования. Рекурсивные алгоритмы, слайд №9Основы программирования. Рекурсивные алгоритмы, слайд №10Основы программирования. Рекурсивные алгоритмы, слайд №11
Скачать
Вы можете ознакомиться и скачать презентацию на тему Основы программирования. Рекурсивные алгоритмы. Доклад-сообщение содержит 11 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


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

Слайд 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); }
Описание слайда:
Пример: вычисление факториала Эквивалентные рекуррентные соотношения для 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)
Описание слайда:
Стек при рекурсивном спуске Последовательные вызовы рекурсивной функции с параметром n и возвращаемым значением f (условное имя) fact(3) fact(2) fact(1) fact(0)

Слайд 4


Стек при рекурсивном подъеме Состояние перед освобождением стека и возвратом в вызывающую функцию с передачей возвращаемого значения f fact(1) fact(2) fact(3)
Описание слайда:
Стек при рекурсивном подъеме Состояние перед освобождением стека и возвратом в вызывающую функцию с передачей возвращаемого значения 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.
Описание слайда:
Метод математической индукции 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.
Описание слайда:
Задача «Ханойские башни» Имеется три колышка: 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 }
Описание слайда:
Рекурсивная функция 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 млрд. лет.
Описание слайда:
Рекуррентное соотношение для трудоемкости из которого получаем: 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
Описание слайда:
Рекурсивное вычисление чисел Фибоначчи 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

Слайд 11


Рекурсивный алгоритм с массивом int F[50]; int fib(int n) { if (!n) return F[0] = 0; else if (n == 1) return F[1] = 1; else if (F[n] > 0) return F[n]; else return F[n] = fib(n-1) + fib(n-2); } void main(…) { int i, n; cin >> n; for (i = 0; i < n; i++) F[i] = 0; cout << fib(n); }
Описание слайда:
Рекурсивный алгоритм с массивом int F[50]; int fib(int n) { if (!n) return F[0] = 0; else if (n == 1) return F[1] = 1; else if (F[n] > 0) return F[n]; else return F[n] = fib(n-1) + fib(n-2); } void main(…) { int i, n; cin >> n; for (i = 0; i < n; i++) F[i] = 0; cout << fib(n); }

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию