Содержание
- 3. Повторение 1. Что будет выведено на экран? #include using namespace std; void main() { int a,
- 4. Повторение 2) Что будет выведено на экран? 3) Что надо исправить для получения правильного результата для
- 6. ОТВЕТЫ: 1) 9 2) Нахождение суммы цифр целого числа 3) Исправления:k=sum_c(abs(m)); Подключить библиотеку: #include
- 7. Лекция 8 Рекурсия
- 8. Пример Что будет делать следующая программа? #include ; using namespace std; void privet(); { cout privet();
- 9. Примеры рекурсивных определений Определение факториала: n!=1*2*3*...*n. Определение функции K(n), которая возвращает количество цифр в заданном натуральном
- 10. Рекурсия Рекурсией называется ситуация, когда какой-то алгоритм вызывает себя прямо (прямая рекурсия) или через другие алгоритмы
- 11. Пример Что выведет на экран следующая программа, если N=123: #include using namespace std; void f(int x)
- 12. Пример Как изменить программу, чтобы цифры числа выводились в правильном порядке? #include using namespace std; void
- 13. Действия, выполняемые на рекурсивном спуске Порождение все новых вызовов рекурсивной подпрограммы до выхода на граничное условие
- 14. Действия, выполняемые на рекурсивном возврате Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы,
- 15. Действия, выполняемые на рекурсивном спуске и на рекурсивном возврате тип Rec (параметры); { ; If Rec(параметры);
- 16. Задачи, решаемые с помощью рекурсии Вычислить факториал (n!), используя рекурсию. Вычислить степень, используя рекурсию. Вычислить n-е
- 17. Задача 1. Вычисление n! Вычислить факториал (n!), используя рекурсию. Исходные данные: n Результат: n! Рассмотрим эту
- 18. Программа. Вычисление n! #include int fact(int n) { if (n==0) return 1; //тривиальная задача return (n*fact(n-1));
- 19. Как работает рекурсия Факториал: int Fact ( int N ) { int F; cout N=" if
- 20. Стек Стек – область памяти, в которой хранятся локальные переменный и адреса возврата. Fact(3) Fact(2) Fact(1)
- 21. Рекурсия При каждом рекурсивном вызове информация о нем сохраняется в специальной области памяти, называемой стеком. В
- 22. Задача 2. Вычисление степени Исходные данные: x,n Результат: xn Математическая модель:
- 23. Программа. Вычисление xn #include int pow( int x,int n) { if(n==0)return 1; //тривиальная задача return(x*pow(x,n-1)); }
- 24. Задача 3. Вычисление n-го числа Фибоначчи.
- 25. Программа. Числа Фибоначчи #include using namespace std; int fib(int x) { if(x==1 || x==2) return 1;
- 26. Числа Фибоначчи Каждый рекурсивный вызов при n > 1 порождает еще 2 вызова функции, многие выражения
- 27. Задача 4. Вычисление суммы цифр числа int sumDig ( int n ) { int sum; sum
- 28. Задача 5. Алгоритм Евклида Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего
- 29. Задача 6 Найти сумму 1!+2!+3!+…+n!
- 30. Программа #include using namespace std; int fact(int n) { return (n>1) ? n * fact(n -
- 31. Задание 7 Вычислить сумму S=2+4+6+8+…2*n. #include using namespace std; int S(int n) { if (n) return
- 32. Задание 8 Определить максимальную цифру целого числа и ее позицию в числе (считать, что цифры пронумерованы
- 33. Задание 9 Дано натуральное число N, заданное в четверичной системе счисления. Написать рекурсивный алгоритм позволяющий перевести
- 34. Задание 10 Что будет изображено на экране?
- 35. Косвенная рекурсия
- 36. Рекурсия – «за» и «против» с каждым новым вызовом расходуется память в стеке (возможно переполнение стека)
- 37. Итерационный алгоритм Любой рекурсивный алгоритм можно заменить нерекурсивным: int Fact ( int N ) { int
- 38. Задание Дан рекурсивный алгоритм: #include using namespace std; void f(int n) { cout if (n {
- 39. Задание #include using namespace std; void F(int n) { cout if (n > 0 ) {
- 41. Скачать презентацию