Основы программирования. Рекурсивные алгоритмы - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Основы программирования. Рекурсивные алгоритмы, слайд №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

Слайд 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

Слайд 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

Слайд 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