Я не обязательно ищу ответ, но я ищу, о чем спрашивает этот вопрос. Нашли этот вопрос, готовясь к интервью, но не уверены, о чем они спрашивают?
Напишите функцию, которая выполняет последовательность Фибоначчи и возвращает индекс, который передается в качестве параметра.
во-первых, вы можете обновить свою базовую математическую информацию о Фибоначчи с помощью этой ссылки из вики. и посмотрите на эту формулу для быстрого вычисления. a href="http://fusharblog.com/solving-linear-recurrence-for-programming-contest/" rel="noreferrer">эта ссылка.
Это рекурсивная функция для вычисления n-го числа Фибоначчи и времени O(2^n):
int Fibonacci(int n) {
if (n == 0 || n == 1) return n;
else
return Fibonacci(n - 1) + Fibonacci(n - 2); }
Вычисление последовательности
Вы можете возразить, что с точки зрения фактического вычисления значений последовательности Фибоначчи на компьютере лучше использовать исходное рекуррентное соотношение f[n]=f[n−1]+f[n−2]. Я склонен согласиться. Чтобы использовать прямое решение в закрытой форме для больших n, вам нужно поддерживать большую точность. Например, даже с 9 знаками после запятой fn≈round(0,723606798⋅(1,618033989)n) допустимо только до n=38 (обратите внимание на здесь по сравнению с здесь). Кроме того, сложение целых чисел требует меньше вычислительных затрат и более точно, чем возведение в степень символьной дроби или значения с плавающей запятой.
это лучшая идея для вычисления n-го числа Фибоначчи и времени O (n):
int Fibonacci(int n) {
if(n <= 0) return 0;
if(n > 0 && n < 3) return 1;
int result = 0;
int preOldResult = 1;
int oldResult = 1;
for (int i=2;i<n;i++) {
result = preOldResult + oldResult;
preOldResult = oldResult;
oldResult = result;
}
return result;}
и это лучший способ вычислить n-е число Фибоначчи и время O (log (n)) :
Как вы уже подозреваете, это будет работать очень похоже. Используйте n-ю степень матрицы x * x
|1 0 0 0 .... 1 1|
|1
| 1
| 1
| 1
| 1
...................
...................
| ... 1 0|
Это легко понять, если умножить эту матрицу на вектор
f(n-1), f(n-2), ... , f(n-x+1), f(n-x)
что приводит к
f(n), f(n-1), ... , f(n-x+1)
Возведение матрицы в степень может быть выполнено за время O (log (n)) (когда x считается постоянным).
Для повторения Фибоначчи также существует решение с закрытой формулой, см. здесь http://en.wikipedia.org/wiki/Fibonacci_number, найдите формулу Бине или Муавра.
и посмотрите на: 1-n-е число Фибоначчи в сублинейном времени
Мне кажется, что вас просят вернуть n-й номер Фибоначчи, где n - переданный параметр. Вы можете использовать различные методы, чтобы ответить на этот вопрос, тогда как все они различаются по временной сложности и сложности кода.
Метод 1 (Использование рекурсии) Простой метод, который представляет собой прямую рекурсивную реализацию математического отношения рекурсии, приведенного выше.
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}
Временная сложность: T(n) = T(n-1) + T(n-2), которая является экспоненциальной. Мы можем заметить, что эта реализация выполняет много повторяющейся работы (см. следующее дерево рекурсии). Так что это плохая реализация для n-го числа Фибоначчи.
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0) Дополнительное пространство: O(n), если учитывать размер стека вызовов функций, в противном случае O (1).
Метод 2 (Использование динамического программирования) Мы можем избежать повторяющейся работы, проделанной методом 1, сохраняя вычисленные числа Фибоначчи.
int fib(int n)
{
/* Declare an array to store fibonacci numbers. */
int f[n+1];
int i;
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
Временная сложность: O(n) Дополнительное пространство: O(n)
Метод 3 (Метод оптимизации пространства 2) Мы можем оптимизировать пространство, используемое в методе 2, сохраняя два предыдущих числа только потому, что это все, что нам нужно, чтобы получить следующее число Фибанначи в серии.
int fib(int n)
{
int a = 0, b = 1, c, i;
if( n == 0)
return a;
for (i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}
Временная сложность: O(n) Дополнительное пространство: O(1)
Метод 4 (с использованием мощности матрицы {{1,1},{0,1}}) Это еще один O (n), который основан на том факте, что если мы n раз умножим матрицу M = {{1,1}, {0,1}} самому себе (другими словами, вычислить мощность (M, n)), то мы получим (n+1)-е число Фибоначчи в качестве элемента в строке и столбце (0, 0) результирующей матрицы.
Матричное представление дает следующее замкнутое выражение для чисел Фибоначчи:
/* Helper function that multiplies 2 matricies F and M of size 2*2, and
puts the multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2]);
/* Helper function that calculates F[][] raise to the power n and puts the
result in F[][]
Note that this function is desinged only for fib() and won't work as general
power function */
void power(int F[2][2], int n);
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void power(int F[2][2], int n)
{
int i;
int M[2][2] = {{1,1},{1,0}};
// n - 1 times multiply the matrix to {{1,0},{0,1}}
for ( i = 2; i <= n; i++ )
multiply(F, M);
}
Временная сложность: O(n) Дополнительное пространство: O(1)
Метод 5 (оптимизированный метод 4) Метод 4 может быть оптимизирован для работы с временной сложностью O(Logn). Мы можем выполнить рекурсивное умножение, чтобы получить мощность (M, n) в предыдущем методе (аналогично оптимизации, выполненной в этом посте)
void multiply(int F[2][2], int M[2][2]);
void power(int F[2][2], int n);
/* function that returns nth Fibonacci number */
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
/* Optimized version of power() in method 4 */
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if( n%2 != 0 )
multiply(F, M);
}
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
Временная сложность: O(Logn) Дополнительное пространство: O(Logn), если учитывать размер стека вызовов функций, в противном случае O(1).
Программа драйвера: int main() { int n = 9; printf("%d", фиб(9)); получитьсимвол(); вернуть 0; }
Ссылки: http://en.wikipedia.org/wiki/Число_Фибоначчи http://www.ics.uci.edu/~eppstein/161/960109.html
Это очень плохо сформулированный вопрос, но вы должны предположить, что они запрашивают nое число Фибоначи, где n предоставляется в качестве параметра.
В дополнение ко всем методам, перечисленным другими, для n > 1 вы также можете использовать метод золотого сечения, что быстрее любого итеративного метода. Но, поскольку в вопросе говорится «пройти через последовательность Фибоначчи», это может не соответствовать требованиям. Вы, вероятно, также напугали бы их до смерти.
Я интерпретирую вопрос по-другому .... учитывая number в качестве входных данных, каково index этого числа в серии? например input=5, тогда индекс равен 5 (учитывая последовательность 0 1 1 2 3 5, где индекс начинается с 0)
Этот код выглядит следующим образом (который возвращает индекс): >http://talkbinary.com/programming/c/fibonacci-in-c/ ]
int Fibonacci(int n)
{
if ( n == 0 )
return 0;
if ( n== 1 )
return 1;
int fib1 = 0;
int fib2 = 1;
int fib = 0;
int i = 0;
for (i = 2; ; i++ )
{
fib = fib1 + fib2;
if ( n == fib )
break;
fib1 = fib2;
fib2 = fib;
}
return i;
}
