Практические работы для 11 класса (по учебнику К.Ю. Полякова, Е.А. Еремина)



Практическая работа № 58
«Числа Фибоначчи»




Файлы-заготовки для выполнения этой практической работы


1. Напишите программу для вычисления N-ого числа Фибоначчи, использующую рекурсию. Проверьте ее работу при различных значениях N и постройте (например, с помощью электронных таблиц) график зависимости времени счёта от N.

Оцените асимптотическую сложность этого алгоритма.

Ответ:

2. Напишите программу для вычисления N-ого числа Фибоначчи, использующую динамическое программирование. Проверьте ее работу при различных значениях N и постройте (например, с помощью электронных таблиц) график зависимости времени счёта от N. Сравните эти данные с рекурсивным вариантом программы:

Оцените асимптотическую сложность алгоритма, использующего динамическое программирование.

Ответ:






Наверх