Алгоритм, с которым я столкнулся и который изначально изо всех сил пытался завершить, был алгоритмом ряда Фибоначчи. Учитывая число, функция должна быть в состоянии произвести запись ряда Фибоначчи в этом числе.

Понимание проблемы

Ряд Фибоначчи представляет собой упорядоченный список чисел, который можно рассчитать, взяв два предыдущих числа и добавив их для получения следующего элемента в списке.

Пример ряда Фибоначчи: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Как решить проблему

Лучший способ получить значение, необходимое для запрошенного индекса, — это вычислить ряд Фибоначчи до этого индекса, а затем вернуть значение. Одним из способов решения проблемы было бы использование цикла for. Перед реализацией цикла for необходимо создать массив результатов, содержащий 0 и 1 в первых двух индексах. Это делается потому, что каждый раз, когда мы пытаемся построить ряд Фибоначчи, мы знаем, что первые два числа останутся прежними, и это дает нам ссылку для создания третьего индекса. В цикле for нам нужно предоставить ссылку на две последние добавляемые записи. Сумма должна быть помещена в массив результатов. После завершения цикла функция должна вернуть значение, хранящееся в массиве результатов по этому конкретному индексу.

Другое решение

Другой способ решения этого алгоритма — рекурсивное решение. В этом рекурсивном решении вы должны объявить свой базовый случай. Ваш базовый случай - это то, что может привести к остановке вашей рекурсии. Затем мы должны вернуть вызываемую функцию с измененными аргументами, чтобы убедиться, что мы продвигаемся к базовому случаю.

При сравнении двух решений обычно мы смотрим на временную сложность. Первое решение можно описать как имеющее линейное время выполнения, так как для каждого int функция должна выполняться один раз. Второе решение, с другой стороны, имеет экспоненциальное время выполнения. Это когда количество входных данных резко увеличивает время обработки для завершения функции. Чтобы улучшить время выполнения второго решения, можно использовать метод мемоизации вызова. Обычно это используется для ускорения функций путем сохранения результатов вызова функции и возврата их при повторении того же ввода.