🗊Презентация Рекурсия. Метод решения задач

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Рекурсия. Метод решения задач, слайд №1Рекурсия. Метод решения задач, слайд №2Рекурсия. Метод решения задач, слайд №3Рекурсия. Метод решения задач, слайд №4Рекурсия. Метод решения задач, слайд №5Рекурсия. Метод решения задач, слайд №6Рекурсия. Метод решения задач, слайд №7Рекурсия. Метод решения задач, слайд №8Рекурсия. Метод решения задач, слайд №9Рекурсия. Метод решения задач, слайд №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 также натуральное
Описание слайда:
Рекурсивные определения Натуральные числа: 0 – натуральное число Если N – натуральное число, то число N+1 также натуральное

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


Факториал числа Рекурсивное определение: Fact(int n) { if(n==0) return 1; else return (Fact(n-1)); }
Описание слайда:
Факториал числа Рекурсивное определение: 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<=n;i++) f=f*I; return (f); }
Описание слайда:
Факториал числа: итеративное определение long Factorial (int n) { int i; long f; if (n==0) return 1; else for(i=1;i<=n;i++) f=f*I; return (f); }

Слайд 11


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

Слайд 12


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

Слайд 13


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

Слайд 14


Ошибка в использовании рекурсии Отсутствие базиса: void PRINT() { cout<<‘*’; PRINT(); } При вызове данной функции процесс вывода никогда не закончится, т.к. отсутствует базис
Описание слайда:
Ошибка в использовании рекурсии Отсутствие базиса: void PRINT() { cout<<‘*’; PRINT(); } При вызове данной функции процесс вывода никогда не закончится, т.к. отсутствует базис

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


Задача о параде Введем обозначения: P(n)- количество вариантов организации парадов длиной n F(n)-количество вариантов организации парадов длиной n, завершающихся платформой B(n) - количество вариантов организации парадов длиной n, завершающегося оркестром Тогда P(n)=F(n)+B(n)
Описание слайда:
Задача о параде Введем обозначения: 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)
Описание слайда:
Задача о параде 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 может состоять из: Платформы и оркестра Двух платформ Двух оркестров
Описание слайда:
Задача о параде Базис: P(1)=2-парад длины один может состоять либо из платформы, либо из оркестра P(2)=3- парад длины 2 может состоять из: Платформы и оркестра Двух платформ Двух оркестров

Слайд 22


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

Слайд 23


Рассуждения мистера Спока Есть две возможности: Либо мы посещаем некоторую планету Х и тогда другие k-1 можно выбрать из оставшихся n-1 планет Либо мы игнорируем планету Х и тогда из остальных n-1 планет можно выбрать k планет
Описание слайда:
Рассуждения мистера Спока Есть две возможности: Либо мы посещаем некоторую планету Х и тогда другие 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
Описание слайда:
Получаем формулу: 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
Описание слайда:
Базис: c(k,k)=1 – можно выбрать только одну группу, состоящую из всех планет c(n,0)=1 – есть только одна группа, не содержащая ничего c(n,k)=0, если k>n

Слайд 26


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

Слайд 27


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

Слайд 28


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

Скачать

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