Презентация Рекурсия. Определение факториала. (Тема 10) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Рекурсия. Определение факториала. (Тема 10) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 22 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Рекурсия. Определение факториала. (Тема 10)
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:22 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:335.17 kB
- Просмотров:86
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№3 слайд
Содержание слайда: СОДЕРЖАНИЕ
Рекурсивные объекты
Рекурсивное определение
Рекурсия
Рекурсивный алгоритм
Пример 1. Определение факториала (слайды 8-11)
Пример 2. Вычисление степени с натуральным показателем (слайд 12)
Пример 3. Вычисление чисел Фибоначчи (слайды 13-15)
Пример 4. Решение задачи о Ханойских башнях (слайды 16-20)
Вопросы и задания
Источники
№4 слайд
Содержание слайда: Рекурсивные объекты
Если поставить два зеркала напротив друг друга и между ними поместить предмет, то получится бесконечное множество изображений, причем каждое из них содержит свое собственное.
Любое из этих изображений можно рассматривать как рекурсивный объект, который частично состоит или определяется с помощью самого себя.
Рекурсивные объекты обладают несколькими свойствами:
простотой построения;
несхожестью конечного результата с начальными данными;
внутренним самоподобием.
№5 слайд
Содержание слайда: Рекурсивное определение
В математике встречаются рекурсивные определения, позволяющие описать объекты через самих себя.
К таким определениям относится, например, определение натурального числа:
единица есть натуральное число;
число, следующее за натуральным (т.е. больше его на единицу), есть натуральное число.
Определение, которое задает некоторый объект в терминах более простого случая этого же объекта, называется рекурсивным определением.
№6 слайд
Содержание слайда: Рекурсия
Мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов.
Как и цикл, рекурсивное определение содержит повторения, но каждый раз при этом используются новые данные, т. е. повторения не являются явными.
Рекурсия — это способ описания функций или процессов через самих себя.
№7 слайд
Содержание слайда: Рекурсивный алгоритм
Процесс может быть описан некоторым алгоритмом, называемым в данном случае рекурсивным.
В таких алгоритмах выделяется два этапа выполнения:
«погружение» алгоритма в себя, т. е. применение определения «в обратную сторону», пока не будет найдено начальное определение, не являющееся рекурсивным;
последовательное построение от начального определения до определения с введенным в алгоритм значением.
Рассмотрим примеры рекурсивных алгоритмов, часто оформляемых в виде процедур и функций.
№8 слайд
Содержание слайда: Пример 1. Определение факториала
Наиболее распространенным рекурсивным определением является определение факториала (нерекурсивное вычисление факториала приведено в примере Е9):
(a) 1! = 1,
(b) n > 1, n: = n*(n - 1)!
На основе этого определения можно записать программу вычисления факториала, использующую рекурсивную функцию.
№10 слайд
Содержание слайда: Выполним программу Е25 для n=4.
Выполним программу Е25 для n=4.
Рекурсивная функция будет работать следующим образом (при вызове функции значение n присваивается переменной x).
Сначала осуществляется «погружение», работает оператор ветви else условного оператора:
1-й шаг: х = 4, х - 1 = 3,
выполняется промежуточное вычисление 4! = 4 * 3!
2-й шаг: х = 3, х - 1 = 2,
выполняется промежуточное вычисление 3! = 3 * 2!
3-й шаг: х = 2, х - 1 = 1,
выполняется промежуточное вычисление 2! = 2 * 1!
4-й шаг (последний): 1! = 1 по начальному определению, работает оператор F: = 1 ветви then условного оператора.
№11 слайд
Содержание слайда: Следующий этап выполнения рекурсивного алгоритма
Следующий этап выполнения рекурсивного алгоритма — построение «прямого» определения, от начального до получения результата с исходными для алгоритма данными (числом 4). При этом осуществляется подстановка предыдущих вычислений (более поздних шагов) в более ранние:
5-й шаг: 2! = 2 * 1 = 2
6-й шаг: 3! = 3 * 2 = 6
7-й шаг: 4! = 4 * 6 = 24 — получен результат, он возвращается в плавную программу и присваивается переменной Y.
№13 слайд
Содержание слайда: Пример 3. Вычисление чисел Фибоначчи
Вычисление чисел Фибоначчи.
Итальянский математик Фибоначчи придумал последовательность натуральных чисел: 1, 1, 2, 3, 5, 8. 13, ... . Первые два члена последовательности равны единице, а каждый, начиная с третьего, равен сумме двух предыдущих. Для чисел Фибоначчи верно соотношение:
Fk=Fk-1 + Fk-2
Рекурсивная функция получения значения n-го числа Фибоначчи имеет вид:
№14 слайд
Содержание слайда: Для чисел Фибоначчи используется следующее рекурсивное определение
Для чисел Фибоначчи используется следующее рекурсивное определение:
(a) n = 1, n = 2: fib(n) = 1
(b) n > 2: fib(n) = fib(n - 2) + fib(n - 1)
Для того чтобы определить fib(6), применяя данное рекурсивное определение, надо вычислить:
fib(6) = fib(4) + fib(5) = fib(2) + fib(3) + fib(5)=
=1 + fib(3) + fib(5)=
=1 + fib(1) + fib(2) + fib(5) =
= 1 + 1 + 1 + fib(5) =
= 3 + fib(3) + fib(4) =
= 3 + fib(1) + fib (2) + fib(4) =
=3 + 1 + 1 + fib(4) =
=5 + fib(2) + fib(3) =
=5 + 1 + fib(1) + fib(2) = 6+1 + 1= 8
№15 слайд
Содержание слайда: Количество действий в данных вычислениях с использованием рекурсивного определения чисел Фибоначчи резко возрастает, потому что это определение ссылается само на себя дважды.
При вычислении факториала количество действий при выполнении программы с рекурсивной функцией и примера E9 одинаково.
№16 слайд
Содержание слайда: Пример 4. Решение задачи
о Ханойских башнях
Рекурсивные алгоритмы могут быть оформлены и в виде процедур.
Примером такой процедуры является решение задачи о Ханойских башнях.
Эта задача связана с легендой о том, что в одном из восточных храмов находится бронзовая плита с тремя алмазными стержнями. На один из них при сотворении мира нанизали 64 диска из чистого золота так, как показано на рисунке 36. Жрецы должны переносить диски с одного стержня на другой, следуя следующим законам:
диски можно перемещать только по одному;
нельзя класть больший диск на меньший.
Согласно легенде, когда все диски будут перенесены с одного стержня на другой, наступит конец света.
№18 слайд
Содержание слайда: Решение этой задачи реализовано в виде рекурсивного алгоритма
Решение этой задачи реализовано в виде рекурсивного алгоритма, который представляет собой инструкцию по перемещению дисков.
Сформулируем задачу, присвоив имена стержням (A, B, C) и номера дискам (от 1 до n).
Надо перенести диски со стержня A на стержень C, используя B как вспомогательный и следуя приведенным выше правилам переноса дисков.
Алгоритм на естественном языке имеет вид:
если n = 0, остановиться;
переместить верхние n - 1 дисков со стержня A на стержень B, используя стержень C как вспомогательный;
переместить оставшийся диск со стержня A на стержень C;
переместить n - 1 дисков со стержня B на стержень C, используя стержень A как вспомогательный.
В процедуре появляется новый тип данных — char, значение этого типа — один символ, заключенный в апострофы.
№20 слайд
Содержание слайда: Результат работы программы для n=3
Результат работы программы для n=3 — это инструкция из 7 пунктов (n= 4 — инструкция из 15 пунктов):
переместить диск 1 со стержня A на стержень C
переместить диск 2 со стержня A на стержень B
переместить диск 1 со стержня C на стержень B
переместить диск 3 со стержня A на стержень C
переместить диск 1 со стержня B на стержень A
переместить диск 2 со стержня B на стержень C
переместить диск 1 со стержня A на стержень C
№21 слайд
Содержание слайда: Вопросы и задания
Что такое рекурсивный объект и каковы его свойства?
Приведите примеры рекурсивного определения в математике.
Что такое рекурсия?
Как выполняется рекурсивный алгоритм?
Поясните выполнения рекурсивной функции вычисления степени с натуральным показателем.
Напишите главную программу для вычисления n-го числа Фибоначчи.
Почему использовать рекурсивный алгоритм вычисления n-го числа Фибоначчи невыгодно?
Определите рекурсивно умножение как сложение и деление как вычитание и оформите алгоритмы в виде рекурсивных функций с вызовом из главных программ.
Скачать все slide презентации Рекурсия. Определение факториала. (Тема 10) одним архивом:
-
Примеры рекурсивных определений
-
Математическое обеспечение САПР. Основные понятия и определения
-
Рекурсивные структуры данных. Списки в Prolog. (Тема 7)
-
BASE-8. 2: Компьютерная танцевальная система
-
ОПЕРАЦІЙНА СИСТЕМА UNIX 1. Загальні відомості і структура ОС UNIX 2. Основи роботи у UNIX 3. Типи оболонок 4. Маски 5. Трубопроводі UNIX - ст
-
Процедуры и функции в Паскале. Рекурсия
-
Обработка строк в Паскале. (Тема 11)
-
Язык программирования Паскаль. (Тема 1)
-
Структура программы в Паскале. Ввод и вывод данных. (Тема 2)
-
Работа в системе Turbo Pascal. (Тема 3)