Рекурсия. Метод решения задач презентация
Содержание
- 2. Определения Рекурсивным называется объект, частично содержащий себя, или определенный с помощью
- 3. Рекурсивные определения Натуральные числа: 0 – натуральное число Если N –
- 4. Рекурсивные определения Факториал числа: 0!=1 N!=(N-1)!*N, для любого N>0;
- 5. Достоинство Рекурсивное определение позволяет определить бесконечное множество объектов с помощью конечного
- 6. Рекурсия в программировании С помощью конечной рекурсивной программы можно описать бесконечное
- 7. Рекурсивные функции Если некоторая подпрограмма (функция) содержит явную ссылку на саму
- 8. Рекурсия Рекурсия сводит решение задачи к решению более мелких идентичных задач
- 9. Факториал числа Рекурсивное определение: Fact(int n) { if(n==0) return 1;
- 10. Факториал числа: итеративное определение long Factorial (int n) { int 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) {
- 17. Задача о параде Необходимо на параде расставить k оркестров и m
- 18. Задача о параде Допустим, что у нас есть N оркестров и
- 19. Задача о параде Введем обозначения: P(n)- количество вариантов организации парадов длиной
- 20. Задача о параде F(n)=P(n-1) – парад, завершающийся платформой длины n получается
- 21. Задача о параде Базис: P(1)=2-парад длины один может состоять либо из
- 22. Дилемма мистера Спока Сколько разных способов можно применить для исследования k
- 23. Рассуждения мистера Спока Есть две возможности: Либо мы посещаем некоторую планету
- 24. Получаем формулу: c(n,k)=c(n-1,k-1)+ c(n-1,k), где c(n-1,k-1) – количество групп, состоящих из
- 25. Базис: c(k,k)=1 – можно выбрать только одну группу, состоящую из всех
- 26. Разложение числа на слагаемые Сколькими способами можно разбить число M на
- 27. Разложение числа на слагаемые Q(M,1)=1 – только одним способом можно представить
- 28. Разложение числа на слагаемые Q(M,M)=Q(M,M-1)+1 – существует только одно разбиение со
- 29. Скачать презентацию
Слайды и текст этой презентации