Примеры рекурсивных определений - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Примеры рекурсивных определений, слайд №1

Примеры рекурсивных определений, слайд №2

Примеры рекурсивных определений, слайд №3

Примеры рекурсивных определений, слайд №4

Примеры рекурсивных определений, слайд №5

Примеры рекурсивных определений, слайд №6

Примеры рекурсивных определений, слайд №7

Примеры рекурсивных определений, слайд №8

Примеры рекурсивных определений, слайд №9

Примеры рекурсивных определений, слайд №10

Примеры рекурсивных определений, слайд №11

Примеры рекурсивных определений, слайд №12

Примеры рекурсивных определений, слайд №13

Примеры рекурсивных определений, слайд №14

Примеры рекурсивных определений, слайд №15

Примеры рекурсивных определений, слайд №16

Примеры рекурсивных определений, слайд №17

Примеры рекурсивных определений, слайд №18

Примеры рекурсивных определений, слайд №19

Примеры рекурсивных определений, слайд №20

Примеры рекурсивных определений, слайд №21

Примеры рекурсивных определений, слайд №22

Примеры рекурсивных определений, слайд №23

Примеры рекурсивных определений, слайд №24

Примеры рекурсивных определений, слайд №25

Примеры рекурсивных определений, слайд №26

Примеры рекурсивных определений, слайд №27

Примеры рекурсивных определений, слайд №28

Примеры рекурсивных определений, слайд №29

Примеры рекурсивных определений, слайд №30

Примеры рекурсивных определений, слайд №31

Примеры рекурсивных определений, слайд №32

Примеры рекурсивных определений, слайд №33

Примеры рекурсивных определений, слайд №34

Примеры рекурсивных определений, слайд №35

Примеры рекурсивных определений, слайд №36

Примеры рекурсивных определений, слайд №37

Примеры рекурсивных определений, слайд №38

Примеры рекурсивных определений, слайд №39

Примеры рекурсивных определений, слайд №40

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Примеры рекурсивных определений. Доклад-сообщение содержит 40 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Алгоритмизация и программирование I Лекция 8

Слайд 2

Описание слайда:

Слайд 3

Описание слайда:

Повторение 1. Что будет выведено на экран? #include using namespace std; void main() { int a, *p; a=3; p=&a; *p*=a; cout

Слайд 4

Описание слайда:

Повторение 2) Что будет выведено на экран? 3) Что надо исправить для получения правильного результата для всех целых чисел?

Слайд 5

Описание слайда:

Слайд 6

Описание слайда:

ОТВЕТЫ: 1) 9 2) Нахождение суммы цифр целого числа 3) Исправления:k=sum_c(abs(m)); Подключить библиотеку: #include

Слайд 7

Описание слайда:

Лекция 8 Рекурсия

Слайд 8

Описание слайда:

Пример Что будет делать следующая программа? #include ; using namespace std; void privet(); { cout

Слайд 9

Описание слайда:

Примеры рекурсивных определений Определение факториала: n!=1*2*3*...*n.

Слайд 10

Описание слайда:

Рекурсия Рекурсией называется ситуация, когда какой-то алгоритм вызывает себя прямо (прямая рекурсия) или через другие алгоритмы (косвенная рекурсия) в качестве вспомогательного. Сам алгоритм называется рекурсивным. Рекурсивное решение задачи состоит из двух этапов: исходная задача сводится к новой задаче, похожей на исходную, но несколько проще; подобная замена продолжается до тех пор, пока задача не станет тривиальной, т. е. очень простой.

Слайд 11

Описание слайда:

Пример Что выведет на экран следующая программа, если N=123: #include using namespace std; void f(int x) { cout

Слайд 12

Описание слайда:

Пример Как изменить программу, чтобы цифры числа выводились в правильном порядке? #include using namespace std; void f(int x) { if(x>10) f(x/10); cout

Слайд 13

Описание слайда:

Действия, выполняемые на рекурсивном спуске Порождение все новых вызовов рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество вызовов рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. тип rec(параметры) { ; If rec(параметры); [else S;] } Обычно проверяют, что с каждым рекурсивным вызовом значение какого-то параметра уменьшается, и это не может продолжаться бесконечно.

Слайд 14

Описание слайда:

Действия, выполняемые на рекурсивном возврате Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным возвратом. тип Rec (параметры); { If Rec (параметры); [else S1]; ; }

Слайд 15

Описание слайда:

Действия, выполняемые на рекурсивном спуске и на рекурсивном возврате тип Rec (параметры); { ; If Rec(параметры); } Или тип Rec(параметры); { If { ; Rec; } }

Слайд 16

Описание слайда:

Задачи, решаемые с помощью рекурсии Вычислить факториал (n!), используя рекурсию. Вычислить степень, используя рекурсию. Вычислить n-е число Фиббоначи , используя рекурсию.

Слайд 17

Описание слайда:

Задача 1. Вычисление n! Вычислить факториал (n!), используя рекурсию. Исходные данные: n Результат: n! Рассмотрим эту задачу на примере вычисления факториала для n=5. Более простой задачей является вычисление факториала для n=4. Тогда вычисление факториала для n=5 можно записать следующим образом: 5!=4!*5. Аналогично: 4!=3!*4; 3!=2!*3; 2!=1!*2 ; 1!=0!*1 Тривиальная (простая) задача: 0!=1. Можно построить следующую математическую модель:

Слайд 18

Описание слайда:

Программа. Вычисление n! #include int fact(int n) { if (n==0) return 1; //тривиальная задача return (n*fact(n-1)); } void main() { coutk; //вводим число для вычисления факториала cout

Слайд 19

Описание слайда:

Как работает рекурсия Факториал:

Слайд 20

Описание слайда:

Стек Стек – область памяти, в которой хранятся локальные переменный и адреса возврата.

Слайд 21

Описание слайда:

Рекурсия При каждом рекурсивном вызове информация о нем сохраняется в специальной области памяти, называемой стеком. В стеке записываются значения локальных переменных, параметров подпрограммы и адрес точки возврата. Какой-либо локальной переменной A на разных уровнях рекурсии будут соответствовать разные ячейки памяти, которые могут иметь разные значения. Воспользоваться значением переменной A i‑ого уровня можно только находясь на этом уровне. Информация в стеке для каждого вызова подпрограммы будет порождаться до выхода на граничное условие. В случае отсутствия граничного условия, неограниченный рост количества информации в стеке приведёт к аварийному завершению программы за счёт переполнения стека.

Слайд 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)); } void main() { int x,k; coutx; //вводим число cin>>k; //вводим степень //вычисление и вывод результата cout

Слайд 24

Описание слайда:

Задача 3. Вычисление n-го числа Фибоначчи.

Слайд 25

Описание слайда:

Программа. Числа Фибоначчи #include 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; coutN; cout

Слайд 26

Описание слайда:

Числа Фибоначчи Каждый рекурсивный вызов при n > 1 порождает еще 2 вызова функции, многие выражения (числа Фибоначчи для малых n) вычисляются много раз.

Слайд 27

Описание слайда:

Задача 4. Вычисление суммы цифр числа int sumDig ( int n ) { int sum; sum = n %10; if ( n >= 10 ) sum += sumDig ( n / 10 ); return sum; }

Слайд 28

Описание слайда:

Задача 5. Алгоритм Евклида Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел. int NOD ( int a, int b ) { if ( a == 0 || b == 0 ) return a + b; if ( a > b ) return NOD( a - b, b ); else return NOD( a, b – a ); }

Слайд 29

Описание слайда:

Задача 6 Найти сумму 1!+2!+3!+…+n!

Слайд 30

Описание слайда:

Программа #include 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() { int n ; cin >> n; cout

Слайд 31

Описание слайда:

Задание 7 Вычислить сумму S=2+4+6+8+…2*n. #include using namespace std; int S(int n) { if (n) return (S(n-1)+2*n); else return 0; } void main() { int n; cin>>n; cout

Слайд 32

Описание слайда:

Задание 8 Определить максимальную цифру целого числа и ее позицию в числе (считать, что цифры пронумерованы справа налево). #include #include using namespace std; void max_c(int n, int &max, int i, int &i_max) { if (n) { max_c(n/10, max,i+1,i_max); if (max < n %10){max=n%10; i_max=i;} } else max=0; } void main() { int n, m,i=1,im; cin>>n; max_c(abs(n),m,i,im); cout

Слайд 33

Описание слайда:

Задание 9 Дано натуральное число N, заданное в четверичной системе счисления. Написать рекурсивный алгоритм позволяющий перевести это число в десятичную систему счисления. #include #include using namespace std; int per4(int p4,int t) { if (p4) return per4(p4/10,t*4)+p4%10*t; else return 0; } void main() { int n, t=1; cin>>n; cout

Слайд 34

Описание слайда:

Задание 10 Что будет изображено на экране?

Слайд 35

Описание слайда:

Косвенная рекурсия

Слайд 36

Описание слайда:

Рекурсия – «за» и «против» с каждым новым вызовом расходуется память в стеке (возможно переполнение стека) затраты на выполнение служебных операций при рекурсивном вызове +: программа становится более короткой и понятной -: возможно переполнение стека; замедление работы