我不一定在寻找答案，但我在寻找这个问题的问题是什么。在准备面试时发现了这个问题，但不知道他们在问什么?
编写遍历斐波那契数列并返回的函数作为参数传入的索引。
首先，您可以使用这个来自wiki的链接更新有关斐波那契的基本数学信息。看看这个快速计算公式。你可以在这个链接中阅读所有关于它的内容。
这是计算第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的直接闭合解，你需要保持a非常精确。即使小数点后9位，例如，Fn≈round(0.723606798⋅(1.618033989)n)只对直到n=38(观察这里和这里)。此外，添加整数也很麻烦计算成本更低，比对a取幂更精确符号分数或浮点值
计算第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)):
这个链接:
正如你已经猜到的那样，这将非常相似。使用x * x矩阵的n次幂
|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，寻找Binet或Moivre的公式。
，看看:
在我看来，你被要求返回第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(0) fib(1) fib(0)/心房纤颤(1)fib (0)额外空间:如果考虑函数调用堆栈大小，则为O(n)，否则为O(1)。
方法二(使用动态规划)我们可以通过存储到目前为止计算的斐波那契数来避免方法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中使用的空间，因为这是我们获得下一个序列Fibannaci数所需要的全部。
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)额外空间:0 (1)
方法4(使用矩阵{{1,1}，{0,1}}的幂)这是另一个O(n)，它依赖于这样一个事实:如果我们将矩阵M ={{1,1}，{0,1}}与自身相乘n次(换句话说，计算幂(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)额外空间:0 (1)
方法五(优化方法四)方法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",fib (9));获取字符();返回0;}
引用:http://en.wikipedia.org/wiki/Fibonacci_numberhttp://www.ics.uci.edu/~eppstein/161/960109.html
这是一个非常糟糕的问题，但你必须假设他们要求的是n斐波那契数，其中n作为参数提供。
对于n > 1，除了其他人列出的所有技术之外，您还可以使用黄金分割法，它比任何迭代方法都要快。但正如题目所说的"遍历斐波那契数列"，这可能不符合条件。你可能还会把他们吓死。
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);
}
我对这个问题的解释不同....给定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;
}