Презентация Рекурсия. Определение факториала. (Тема 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
  • Просмотров:
    91
  • Скачиваний:
    0
  • Автор:
    неизвестен



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

№1 слайд
Основы программирования
Содержание слайда: Основы программирования Учитель информатики и ИКТ ГОУ г.Москвы СОШ №310 «У Чистых прудов» Цыбикова Т.Р.

№2 слайд
рекурсия Тема .
Содержание слайда: рекурсия Тема 10.

№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)! На основе этого определения можно записать программу вычисления факториала, использующую рекурсивную функцию.

№9 слайд
Содержание слайда:

№10 слайд
Выполним программу Е для n .
Содержание слайда: Выполним программу Е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.

№12 слайд
Пример . Вычисление степени с
Содержание слайда: Пример 2. Вычисление степени с натуральным показателем Вычисление степени с натуральным показателем можно определить рекурсивно: (а) x0 = 1 (б) k>0: хk = x*xk-1 Этому определению соответствует рекурсивная функция power(k,x). Программа имеет вид:

№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. Жрецы должны переносить диски с одного стержня на другой, следуя следующим законам: диски можно перемещать только по одному; нельзя класть больший диск на меньший. Согласно легенде, когда все диски будут перенесены с одного стержня на другой, наступит конец света.

№17 слайд
Содержание слайда:

№18 слайд
Решение этой задачи
Содержание слайда: Решение этой задачи реализовано в виде рекурсивного алгоритма Решение этой задачи реализовано в виде рекурсивного алгоритма, который представляет собой инструкцию по перемещению дисков. Сформулируем задачу, присвоив имена стержням (A, B, C) и номера дискам (от 1 до n). Надо перенести диски со стержня A на стержень C, используя B как вспомогательный и следуя приведенным выше правилам переноса дисков. Алгоритм на естественном языке имеет вид: если n = 0, остановиться; переместить верхние n - 1 дисков со стержня A на стержень B, используя стержень C как вспомогательный; переместить оставшийся диск со стержня A на стержень C; переместить n - 1 дисков со стержня B на стержень C, используя стержень A как вспомогательный. В процедуре появляется новый тип данных — char, значение этого типа — один символ, заключенный в апострофы.

№19 слайд
Программа имеет вид
Содержание слайда: Программа имеет вид:

№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-го числа Фибоначчи невыгодно? Определите рекурсивно умножение как сложение и деление как вычитание и оформите алгоритмы в виде рекурсивных функций с вызовом из главных программ.

№22 слайд
Литература А.А.Кузнецов,
Содержание слайда: Литература А.А.Кузнецов, Н.В.Ипатова «Основы информатики», 8-9 кл.: Раздел 3. ОСНОВЫ ПРОГРАММИРОВАНИЯ, С.130-135

Скачать все slide презентации Рекурсия. Определение факториала. (Тема 10) одним архивом: