Может кто-то, пожалуйста, дайте мне знать, если в следующем коде есть что-то не так... В вопросе меня спрашивали, что-то не так, со следующей функцией числа фибоначчи.
int fib(int n)
{
if (n <= 1) return n;
return fib (n-1) + fib(n-2);
}
где n равно 0... 100
Поэтому мой ответ был ничем, поскольку я не вижу ничего очевидного. Синтаксис кажется точным и логически, это вычисление числа фибоначчи. Правильно ли я принимаю это предположение?
Это зависит от того, о каких проблемах вы спрашиваете. Здесь я вижу две проблемы:
int
type can not удерживает все числа Фибоначчи в диапазоне [0, 100] Это пример реализации с использованием итерации в Python (только потому, что он может содержать fib(100)
из коробки):
In [16]: def fib(n):
....: curr, next = 0, 1
....: for x in range(n):
....: curr, next = next, curr
....: next += curr
....: return curr
....:
In [17]: fib(100)
Out[17]: 354224848179261915075L
Извините, если ответ слишком поздний, но вы также должны изучить сложность этой функции, чтобы лучше понять, почему она не работает нормально.
Поскольку для каждого обращения функции, которую вы называете fib (n-1) и fib (n-2), количество операций, выполняемых fib (n), будет около 2 ^ n. Проверьте следующую программу, которая подсчитывает, сколько раз вызывается fib():
#include <iostream>
using namespace std;
int cnt = 0;
int fib(int n) {
cnt++;
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
cout << fib(15) << '\n';
cout << cnt << '\n';
}
Итак, если вы хотите называть fib (100), он будет выполнять около 10 ^ 18 операций и, предположив, что ваш компьютер достаточно быстро, чтобы сделать 10 ^ 9 операций за 1 секунду, для завершения этого потребуется около 33 лет.
Но это приведет к ошибке раньше.
Верно, что fib (100) будет содержать более 19 цифр, что (aprox.) Максимальное значение, которое может длиться долго, но это не главная причина, почему ваша функция "липкая".
Хорошая (и, может быть, лучшая) альтернатива здесь будет заключаться в том, что, как уже говорилось выше, с использованием итеративной функции/алгоритма с линейной сложностью (ваша функция экспоненциальна, читайте здесь).
Здесь код функции фибоначчи, реализованный с использованием больших чисел в C++ (там больше C на самом деле, но, в любом случае):
#include <iostream>
using namespace std;
const int maxsize = 10000; // number of digits
int n;
// note that the digits are keep reversed in the vector
// the bigsum function is as you would use add in math
// a = a + b
void bigsum(int a[], int b[]) { // in a[0] I hold the number of digits of 'a'
int i, t = 0;
for (i = 1; i <= a[0] || i <= b[0] || t; ++i) { // while you still have digits to add
t = t + a[i] + b[i];
a[i] = t % 10;
t /= 10;
}
a[0] = i - 1; // the new a[0]
}
int zero[maxsize];
// a = b
void copy(int a[], int b[]) {
for (int i = 0; i <= b[0]; ++i) {
a[i] = b[i];
}
}
void fib(int n) {
if (n < 0) {
cout << "NA";
} else if (n == 0) {
cout << 0;
} else if (n == 1 || n == 2) {
cout << 1;
} else if (n == 3) {
cout << 2;
} else {
int first[maxsize], second[maxsize], third[maxsize];
copy(first, zero); copy(second, zero); copy(third, zero);
first[0] = first[1] = second[0] = second[1] = 1; // initializing the numbers with 1
third[0] = 1; third[1] = 2; // initializing with 2
for (int i = 4; i <= n; ++i) {
copy(first, second);
copy(second, third); // if you don't understand why these 3, try to do it on a paper
bigsum(third, first);
}
for (int i = third[0]; i >= 1; --i) { // because the digits are reversed
cout << third[i];
}
}
cout << '\n';
}
int main() {
cin >> n;
fib(n);
}
Теперь функция fib работает для более высоких чисел (10000 цифр, просто измените значение maxsize, если хотите больше), а общее число операций - n * NUMBER_OF_DIGITS, что около n ^ 2 (путь меньше 2 ^ n).
Другим очень приятным решением будет использование матрицы 2x2, которая позволяет вычислять остаток fib (n)% SOME_NUMBER в aprox. log2 (n) (вы можете использовать "возведение в степень по квадрату", см. это). Подробнее о матричном решении читайте здесь.
В заключение, ваша программа не хороша, потому что она работает в экспоненциальной сложности, а также использует слишком много памяти стека (даже если она возвращает правильное значение).
Надеюсь, теперь вы поймете проблемы своей функции. Извините, если этого сообщения не должно быть здесь.
Всего наилучшего!
fib(100)
составляет 21 цифру, ноunsigned long long
может содержать только 19 цифр (если sizeof = 64 бита).