C ++ ctime, чтобы увидеть, как секунды не работают должным образом. Фибоначчи
int main() {
clock_t start, finish;
double elapsedTime;
start = clock();
unsigned __int64 result = fibonacci_recursion(300);finish = clock();
elapsedTime = (finish - start);
cout << "result is " << result << endl;
cout << "Time required = " << elapsedTime << " seconds " << endl;}unsigned __int64 fibonacci_recursion(int number) {
unsigned __int64 result = 1;
if (number > 2) {
int firstNumber = 1;
int secondNumber = 1;
int swapHolder;
for (int i = 3; i <= number; ++i) {
swapHolder = firstNumber + secondNumber;
firstNumber = secondNumber;
secondNumber = swapHolder;
}
result = swapHolder;
}
return result;
}
Функция является рекурсивным методом для выполнения числовой последовательности Фибоначчи. Рекурсия для этого должна занять некоторое время. По словам нашего инструктора, время должно быть больше. Как … через несколько секунд. Я продолжаю получать 0. Мой компьютер просто очень быстро?
Решение
64-битное число может содержать около 20 цифр. Fib 300, кажется, около 60 цифр или 222232244629420445529739893461909967206666939096499764990979600. Таким образом, вы не можете ожидать хорошего результата.
Кроме того, вы не делаете никакой рекурсии, поэтому вы получаете быстрый результат.
Рекурсивным решением будет функция, которая содержит обращения к себе, как
really_really_big_int_t rec_fib(int n){
if (n < 1) return 0; // catch invalid values
if (n < 3) return 1; // catch recursion base case
return rec_fib(n - 1) + rec_fib(n - 2);
}
Числа Фибоначчи используются здесь для иллюстрации рекурсии, потому что это очень простой случай. Рекурсивный подход для фактического вычисления чисел Фибоначчи был бы очень плохим решением. Это приводит ко многим, многим ненужным вычислениям. Вот почему вас просят определить время в вашей лаборатории. Было бы показать, что некоторые алгоритмы занимают неоправданное количество времени даже для небольших входов (300).
Итеративный подход, который вы предоставили в своем вопросе, очень предпочтителен.
Другие решения
Других решений пока нет …