Не связано с ограничением глубины, но сильно связано с вычислением числа Фибоначчи.
Рекурсия, возможно, неправильный подход и не нужна.
Существует сверхбыстрое решение с минимальным объемом памяти.
Итак, мы могли бы использовать предварительное вычисление во время компиляции всех чисел Фибоначчи, которые соответствуют 64-битному значению.
Одним из важных свойств ряда Фибоначчи является то, что значения растут строго экспоненциально. Таким образом, все существующие встроенные целочисленные типы данных довольно быстро переполнятся.
С помощью формулы Бине вы можете вычислить, что 93-е число Фибоначчи будет последним вписывается в 64-битное беззнаковое значение.
А вычисление 93 значений при компиляции - действительно простая задача.
Сначала мы определим подход по умолчанию для вычисления числа Фибоначчи как функцию constexpr:
// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
// Initialize first two even numbers
unsigned long long f1{ 0 }, f2{ 1 };
// calculating Fibonacci value
while (index--) {
// get next value of Fibonacci sequence
unsigned long long f3 = f2 + f1;
// Move to next number
f1 = f2;
f2 = f3;
}
return f2;
}
Благодаря этому числа Фибоначчи можно легко вычислить во время компиляции. Затем мы заполняем std::array всеми числами Фибоначчи. Мы также используем constexpr и делаем его шаблоном с вариативным пакетом параметров.
Мы используем std::integer_sequence для создания числа Фибоначчи для индексов 0,1,2,3,4,5, ....
Это просто и несложно:
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};
Эта функция будет загружена с целочисленной последовательностью 0,1,2,3,4, ... и вернет std::array<unsigned long long, ...> с соответствующими числами Фибоначчи.
Мы знаем, что можем сохранить максимум 93 значения. И поэтому мы создаем следующую функцию, которая будет вызывать вышеуказанное с целочисленной последовательностью 1,2,3,4, ..., 92,93, например:
constexpr auto generateArray() noexcept {
return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}
И вот, наконец,
constexpr auto FIB = generateArray();
даст нам время компиляции std::array<unsigned long long, 93> с именем FIB, содержащим все числа Фибоначчи. А если нам нужно i-е число Фибоначчи, мы можем просто написать FIB[i]. Во время выполнения вычислений не будет.
Я не думаю, что есть более быстрый способ вычислить n-е число Фибоначчи.
Пожалуйста, смотрите полную программу ниже:
#include <iostream>
#include <array>
#include <utility>
// ----------------------------------------------------------------------
// All the following will be done during compile time
// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) {
// Initialize first two even numbers
unsigned long long f1{ 0 }, f2{ 1 };
// calculating Fibonacci value
while (index--) {
// get next value of Fibonacci sequence
unsigned long long f3 = f2 + f1;
// Move to next number
f1 = f2;
f2 = f3;
}
return f2;
}
// We will automatically build an array of Fibonacci numberscompile time
// Generate a std::array with n elements
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};
// Max index for Fibonaccis that for in an 64bit unsigned value (Binets formula)
constexpr size_t MaxIndexFor64BitValue = 93;
// Generate the required number of elements
constexpr auto generateArray()noexcept {
return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}
// This is an constexpr array of all Fibonacci numbers
constexpr auto FIB = generateArray();
// ----------------------------------------------------------------------
// Test
int main() {
// Print all possible Fibonacci numbers
for (size_t i{}; i < MaxIndexFor64BitValue; ++i)
std::cout << i << "\t--> " << FIB[i] << '\n';
return 0;
}
Разработано и протестировано с помощью Microsoft Visual Studio Community 2019, версия 16.8.2.
Дополнительно скомпилирован и протестирован с помощью clang11.0 и gcc10.2
Язык: C ++ 17
person
Armin Montigny
schedule
17.04.2021
