Презентация Рекурсия. Метод решения задач онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Рекурсия. Метод решения задач абсолютно бесплатно. Урок-презентация на эту тему содержит всего 28 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:28 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:135.00 kB
- Просмотров:56
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№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<=n;i++) f=f*I;
return (f);
}
№11 слайд
Содержание слайда: Рекурсивное решение
При вызове подпрограммы всякий раз создаются новые экземпляры локальных переменных
При этом не возникает никаких конфликтов при использовании имен
№12 слайд
Содержание слайда: Рекурсивное решение: факториал числа 5
№13 слайд
Содержание слайда: Свойства рекурсивного решения
Функция вызывает саму себя
При каждом вызове функции решается идентичная, но меньшая задача
Одна из подзадач решается иначе, чем другие : в итоге одна из подзадач является базовой
Проверка базисных условий позволяет остановить процесс рекурсии
№14 слайд
Содержание слайда: Ошибка в использовании рекурсии
Отсутствие базиса:
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);
}
№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 на слагаемые <=N
№27 слайд
Содержание слайда: Разложение числа на слагаемые
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
Скачать все slide презентации Рекурсия. Метод решения задач одним архивом:
