Рекурсия. Метод решения задач - презентация, доклад, проект скачать

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

Рекурсия. Метод решения задач, слайд №10

Рекурсия. Метод решения задач, слайд №11

Рекурсия. Метод решения задач, слайд №12

Рекурсия. Метод решения задач, слайд №13

Рекурсия. Метод решения задач, слайд №14

Рекурсия. Метод решения задач, слайд №15

Рекурсия. Метод решения задач, слайд №16

Рекурсия. Метод решения задач, слайд №17

Рекурсия. Метод решения задач, слайд №18

Рекурсия. Метод решения задач, слайд №19

Рекурсия. Метод решения задач, слайд №20

Рекурсия. Метод решения задач, слайд №21

Рекурсия. Метод решения задач, слайд №22

Рекурсия. Метод решения задач, слайд №23

Рекурсия. Метод решения задач, слайд №24

Рекурсия. Метод решения задач, слайд №25

Рекурсия. Метод решения задач, слайд №26

Рекурсия. Метод решения задач, слайд №27

Рекурсия. Метод решения задач, слайд №28

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Рекурсия. Метод решения задач. Доклад-сообщение содержит 28 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

Описание слайда:

Рекурсия

Слайд 2

Описание слайда:

Определения Рекурсивным называется объект, частично содержащий себя, или определенный с помощью самого себя.

Слайд 3

Описание слайда:

Рекурсивные определения Натуральные числа: 0 – натуральное число Если N – натуральное число, то число N+1 также натуральное

Слайд 4

Описание слайда:

Рекурсивные определения Факториал числа: 0!=1 N!=(N-1)!*N, для любого N>0;

Слайд 5

Описание слайда:

Достоинство Рекурсивное определение позволяет определить бесконечное множество объектов с помощью конечного высказывания

Слайд 6

Описание слайда:

Рекурсия в программировании С помощью конечной рекурсивной программы можно описать бесконечное вычисление, причем программа не будет содержать явных повторений

Слайд 7

Описание слайда:

Рекурсивные функции Если некоторая подпрограмма (функция) содержит явную ссылку на саму себя, то ее называют прямо-рекурсивной Если подпрограмма P ссылается на другую подпрограмму Q, которая содержит ссылку на P, то такую подпрограмму называют косвенно-рекурсивной

Слайд 8

Описание слайда:

Рекурсия Рекурсия сводит решение задачи к решению более мелких идентичных задач Сложные задачи могут иметь простые рекурсивные решения Не всегда рекурсивный метод решения лучше итеративного (основанного на использовании циклов)

Слайд 9

Описание слайда:

Факториал числа Рекурсивное определение: Fact(int n) { if(n==0) return 1; else return (Fact(n-1)); }

Слайд 10

Описание слайда:

Факториал числа: итеративное определение long Factorial (int n) { int i; long f; if (n==0) return 1; else for(i=1;i

Слайд 11

Описание слайда:

Рекурсивное решение При вызове подпрограммы всякий раз создаются новые экземпляры локальных переменных При этом не возникает никаких конфликтов при использовании имен

Слайд 12

Описание слайда:

Рекурсивное решение: факториал числа 5

Слайд 13

Описание слайда:

Свойства рекурсивного решения Функция вызывает саму себя При каждом вызове функции решается идентичная, но меньшая задача Одна из подзадач решается иначе, чем другие : в итоге одна из подзадач является базовой Проверка базисных условий позволяет остановить процесс рекурсии

Слайд 14

Описание слайда:

Ошибка в использовании рекурсии Отсутствие базиса: void PRINT() { cout

Слайд 15

Описание слайда:

Четыре вопроса о рекурсивном решении: Как свести задачу к идентичным задачам меньшего размера? Как уменьшать размер задачи при каждом рекурсивном вызове Какая задача является базовой Можно ли достичь базиса, постоянно уменьшая размер задачи?

Слайд 16

Описание слайда:

Числа Фибоначчи F(n)=F(n-1)+F(n-2) Необходимо 2 базиса:F(1)=1, F(2)=1; int F(int n) { if (n

Слайд 17

Описание слайда:

Задача о параде Необходимо на параде расставить k оркестров и m платформ, так, чтобы никакие два оркестра не стояли рядом. Сколькими способами можно расставить оркестры и платформы, если их всего N штук.

Слайд 18

Описание слайда:

Задача о параде Допустим, что у нас есть N оркестров и N платформ Будем считать, что варианты оркестр-платформа и платформа-оркестр – различны Парад может закрываться либо платформой, либо оркестром

Слайд 19

Описание слайда:

Задача о параде Введем обозначения: P(n)- количество вариантов организации парадов длиной n F(n)-количество вариантов организации парадов длиной n, завершающихся платформой B(n) - количество вариантов организации парадов длиной n, завершающегося оркестром Тогда P(n)=F(n)+B(n)

Слайд 20

Описание слайда:

Задача о параде F(n)=P(n-1) – парад, завершающийся платформой длины n получается из парада длиной n-1, завершающийся оркестром B(n)=F(n-1) – если парад заканчивается оркестром, значит перед ним стоит платформа Таким образом получаем: B(n)=P(n-2) P(n)=P(n-1)+P(n-2)

Слайд 21

Описание слайда:

Задача о параде Базис: P(1)=2-парад длины один может состоять либо из платформы, либо из оркестра P(2)=3- парад длины 2 может состоять из: Платформы и оркестра Двух платформ Двух оркестров

Слайд 22

Описание слайда:

Дилемма мистера Спока Сколько разных способов можно применить для исследования k планет, если солнечная система состоит из n планет (с(n,k))

Слайд 23

Описание слайда:

Рассуждения мистера Спока Есть две возможности: Либо мы посещаем некоторую планету Х и тогда другие k-1 можно выбрать из оставшихся n-1 планет Либо мы игнорируем планету Х и тогда из остальных n-1 планет можно выбрать k планет

Слайд 24

Описание слайда:

Получаем формулу: c(n,k)=c(n-1,k-1)+ c(n-1,k), где c(n-1,k-1) – количество групп, состоящих из k планет, включающих планету X c(n-1,k) - количество групп, состоящих из k планет, не включающих планету X

Слайд 25

Описание слайда:

Базис: c(k,k)=1 – можно выбрать только одну группу, состоящую из всех планет c(n,0)=1 – есть только одна группа, не содержащая ничего c(n,k)=0, если k>n

Слайд 26

Описание слайда:

Разложение числа на слагаемые Сколькими способами можно разбить число M на слагаемые Обозначим число разбиений P(M) Введем новую функцию Q(M,N) – количество разбиений числа M на слагаемые

Слайд 27

Описание слайда:

Разложение числа на слагаемые Q(M,1)=1 – только одним способом можно представить число М с помощью 1: 1+1+….+1 Q(1,N)=1 – число один можно разложить на слагаемые только одним способом, независимо от N Q(M,N)=Q(M,M), M

Слайд 28

Описание слайда:

Разложение числа на слагаемые Q(M,M)=Q(M,M-1)+1 – существует только одно разбиение со слагаемым = М, все остальные имеют слагаемые меньшие M Q(M,N)=Q(M,N-1)+Q(M-N,N) – любое разбиение М с наибольшим слагаемым