Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 11 классы | Практические работы для 11 класса (по учебнику К.Ю. Полякова, Е.А. Еремина) | Практическая работа №58
Практическая работа № 58
«Числа Фибоначчи»
1. Напишите программу для вычисления N-ого числа Фибоначчи, использующую рекурсию. Проверьте ее работу при различных значениях N и постройте (например, с помощью электронных таблиц) график зависимости времени счёта от N.
Оцените асимптотическую сложность этого алгоритма.
Ответ:
2. Напишите программу для вычисления N-ого числа Фибоначчи, использующую динамическое программирование. Проверьте ее работу при различных значениях N и постройте (например, с помощью электронных таблиц) график зависимости времени счёта от N. Сравните эти данные с рекурсивным вариантом программы:
Оцените асимптотическую сложность алгоритма, использующего динамическое программирование.
Ответ:
