Презентация «Примеры рекурсивных определений»

Смотреть слайды в полном размере
Презентация «Примеры рекурсивных определений»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 40 слайдов и доступен в формате ppt. Размер файла: 560.00 KB

Просмотреть и скачать

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


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!