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