我不一定要寻找答案，但我正在寻找这个问题的要求。发现这个问题正在准备面试，但不确定他们在问什么？
编写遍历斐波那契数列并返回作为参数传入的索引的函数。
问问题
80198 次
5 回答
30
首先，您可以使用来自 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 使用直接闭式解，您需要保持很多精度。即使有 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))：
正如您已经怀疑的那样，这将非常相似。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 被认为是常数时）。
对于 Fibonacci 递归，还有一个封闭公式解决方案，请参阅此处http://en.wikipedia.org/wiki/Fibonacci_number，查找 Binet 或 Moivre 公式。
于 2013-05-05T21:15:23.990 回答
12
在我看来，您被要求返回第 n 个斐波那契数，其中 n 是传递的参数。您可以采用各种方法来回答这个问题，而所有这些方法的时间复杂度和代码复杂度各不相同。
方法一（使用递归） 一种简单的方法，是上面给出的直接递归实现数学递归关系。
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 中使用的空间，因为这就是我们获得下一个 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) 额外空间：O(1)
方法 4（使用矩阵 {{1,1},{0,1}} 的幂）这是另一个 O(n)，它依赖于这样一个事实：如果我们将矩阵 M = {{1,1} 相乘 n 次， {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", fib(9)); 获取字符（）；返回0；}
参考资料： http ://en.wikipedia.org/wiki/Fibonacci_number http://www.ics.uci.edu/~eppstein/161/960109.html
于 2013-05-06T21:10:53.253 回答
1
这是一个措辞非常糟糕的问题，但您必须假设他们要求提供作为参数的第 n个斐波那契数。n
除了其他人列出的所有技术之外，n > 1您还可以使用黄金比例方法，它比任何迭代方法都快。但正如问题所说的“遍历斐波那契数列”，这可能不符合条件。你可能也会把他们吓死。
于 2013-05-07T02:32:16.490 回答
0
我对这个问题的解释不同......给定 anumber作为输入，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;
}
于 2013-05-05T21:53:49.477 回答
0
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);
}
于 2013-05-05T21:19:02.413 回答