Презентация Примеры рекурсивных определений онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Примеры рекурсивных определений абсолютно бесплатно. Урок-презентация на эту тему содержит всего 40 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Примеры рекурсивных определений
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:40 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:560.00 kB
- Просмотров:81
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№10 слайд
Содержание слайда: Рекурсия
Рекурсией называется ситуация, когда какой-то алгоритм вызывает себя прямо (прямая рекурсия) или через другие алгоритмы (косвенная рекурсия) в качестве вспомогательного. Сам алгоритм называется рекурсивным.
Рекурсивное решение задачи состоит из двух этапов:
исходная задача сводится к новой задаче, похожей на исходную, но несколько проще;
подобная замена продолжается до тех пор, пока задача не станет тривиальной, т. е. очень простой.
№13 слайд
Содержание слайда: Действия, выполняемые на рекурсивном спуске
Порождение все новых вызовов рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском.
Максимальное количество вызовов рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии.
тип rec(параметры)
{
<действия на входе в рекурсию>;
If <проверка условия> rec(параметры);
[else S;]
}
Обычно проверяют, что с каждым рекурсивным вызовом значение какого-то параметра уменьшается, и это не может продолжаться бесконечно.
№14 слайд
Содержание слайда: Действия, выполняемые на рекурсивном возврате
Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным возвратом.
тип Rec (параметры);
{
If <проверка условия> Rec (параметры);
[else S1];
<действия на выходе из рекурсии>;
}
№15 слайд
Содержание слайда: Действия, выполняемые на рекурсивном спуске и на рекурсивном возврате
тип Rec (параметры);
{
<действия на входе в рекурсию>;
If <условие> Rec(параметры);
<действия на выходе из рекурсии>
}
Или
тип Rec(параметры);
{
If <условие>
{
<действия на входе в рекурсию>;
Rec;
<действия на выходе из рекурсии>
}
}
№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.
Можно построить следующую математическую модель:
№21 слайд
Содержание слайда: Рекурсия
При каждом рекурсивном вызове информация о нем сохраняется в специальной области памяти, называемой стеком.
В стеке записываются значения локальных переменных, параметров подпрограммы и адрес точки возврата.
Какой-либо локальной переменной A на разных уровнях рекурсии будут соответствовать разные ячейки памяти, которые могут иметь разные значения.
Воспользоваться значением переменной A i‑ого уровня можно только находясь на этом уровне.
Информация в стеке для каждого вызова подпрограммы будет порождаться до выхода на граничное условие.
В случае отсутствия граничного условия, неограниченный рост количества информации в стеке приведёт к аварийному завершению программы за счёт переполнения стека.
№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?";
cin>>x; //вводим число
cin>>k; //вводим степень
//вычисление и вывод результата
cout<<x<<"^"<<k<<"="<<pow(x,k);
}
№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 );
}
№32 слайд
Содержание слайда: Задание 8
Определить максимальную цифру целого числа и ее позицию в числе (считать, что цифры пронумерованы справа налево).
#include <iostream>
#include <cmath>
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<<m<<" "<<im;
}
№33 слайд
Содержание слайда: Задание 9
Дано натуральное число N, заданное в четверичной системе счисления. Написать рекурсивный алгоритм позволяющий перевести это число в десятичную систему счисления.
#include <iostream>
#include <cmath>
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<< per4(n,t);
}
Скачать все slide презентации Примеры рекурсивных определений одним архивом:
-
Примеры использования OpenMP. Вычисление определенного интеграла
-
Рекурсия. Определение факториала. (Тема 10)
-
Рекурсивные функции
-
Рекурсивные алгоритмы. ЕГЭ-2017 по информатике. Задание 11
-
Функциональные типы и описание функций. Примеры
-
Определение разницы между максимальным и минимальным корнем уравнения y1(x) y2(x) интервале значений x 0, 10)
-
Рекурсия. Рекурсивная функция
-
Дополнительные возможности в определении функций
-
Структура команд и режимы адресации на примере PDP-11
-
Деревья. Формальное определение дерева