Поделиться
Л3-00150.docx
Практическая работа № 25. Числа Фибоначчи
1. Напишите программу для вычисления N-ого числа Фибоначчи, использующую рекурсию. Проверьте ее работу при различных значениях N и постройте (например, с помощью электронных таблиц) график зависимости времени счёта от N.
Оцените асимптотическую сложность этого алгоритма.
Ответ:
2. Напишите программу для вычисления N-ого числа Фибоначчи, использующую динамическое программирование. Проверьте ее работу при различных значениях N и постройте (например, с помощью электронных таблиц) график зависимости времени счёта от N. Сравните эти данные с рекурсивным вариантом программы:
|
N |
Время счёта |
|
|
рекурсия |
динамическое программирование |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Оцените асимптотическую сложность алгоритма, использующего динамическое программирование.
Ответ:
алгоритм Флойда-Уоршелла
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
