Функция алгоритма для ряда фибоначчи

Question

Я не ищу ответа, но я ищу, о чем спрашивает этот вопрос. Нашел этот вопрос, изучая интервью, но не уверен, что они спрашивают?

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

Answer 1

Во-первых, вы можете обновить свою базовую математическую информацию о Фибоначчи с помощью этого link из wiki. и посмотрите на this formula для быстрого расчета. И вы можете прочитать все об этом в this link.

Это рекурсивная функция для вычисления п-й ряд Фибоначчи и О (2^п):

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 (см. here по сравнению с here). Кроме того, добавление целых чисел намного меньше вычислительных затрат, и более точно, чем потенцируя в символическую фракцию или значение с плавающей запятой

это лучше идея, чтобы вычислить п-ю число Фибоначчи и О (п):

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;} 

и это лучший способ для вычисления п-й ряд Фибоначчи и имеет O (журнал (п)) время:

this link:

Как вы уже подозреваете, это будет очень похоже. Используйте п-й степени 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) 

Matrix экспоненциации может выполняться в O (log (n)) времени (когда x считается постоянным).

Для повторения Фибоначчи существует также замкнутое решение формулы, см. Здесь http://en.wikipedia.org/wiki/Fibonacci_number, ищите формулу Бине или Мойвра.

и посмотреть на: 1- nth fibonacci number in sublinear time

Answer 2

public static int fibonacci(int i){ 
if(i==0) 
    return 0; 

if(i==1) 
    return 1; 
return fib(--i,0,1); 
} 


public static int fib(int num,int pre,int prepre){ 
    if(num==0){ 
    return prepre+pre; 
    } 
    return fib(--num,pre+prepre,pre); 
} 

Answer 3

интерпретировать вопрос иначе .... дается в 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; 
} 

Answer 4

Мне кажется, что вас попросят вернуть n-й фибоначчи, где n - переданный параметр. Вы можете использовать различные методы для ответа на этот вопрос, тогда как все это зависит от сложности времени и сложности кода.

Метод 1 (использование рекурсии) Простой метод, который представляет собой математическое отношение к выполнению прямой рекультивации, приведенное выше.

int fib(int n) 
{ 
    if (n <= 1) 
    return n; 
    return fib(n-1) + fib(n-2); 
} 

Время Сложность: Т (п) = Т (п-1) + Т (п-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 (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]; 
} 

Время Сложность: О (п) Дополнительное пространство: О (п)

Метод 3 (Космический Otimized Способ 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 (1)

Метод 4 (использование мощности Matrx {{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 (п) Дополнительное пространство: O (1)

Метод 5 (оптимизированный метод 4) Метод 4 может быть оптимизирован для работы во временной сложности O (Logn). Мы можем сделать рекурсивного умножения, чтобы получить власть (M, N) в prevous методе (по аналогии с оптимизацией, проводимой в этой должности)

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() { {img} int n = 9; printf ("% d", fib (9)); getchar(); return 0; }

Ссылки: http://en.wikipedia.org/wiki/Fibonacci_number http://www.ics.uci.edu/~eppstein/161/960109.html

Answer 5

Это очень плохо сформулированный вопрос, но вы должны предположить, что они просят п ^{го числа} Fibonnaci где n предусмотрено в качестве параметра.

В дополнение ко всем методам, перечисленным другими, для n > 1 вы также можете использовать golden ratio method, который быстрее любого итерационного метода. Но поскольку вопрос говорит, что «проходит через последовательность Фибоначчи», это может не соответствовать. Вероятно, вы также напугаете их до смерти.