我并不是在寻找答案,而是想知道这个问题要求什么。我在为面试学习时发现了这个问题,但不确定他们想问什么?
编写一个函数,遍历斐波那契数列并返回作为参数传递的索引。
首先,你可以通过这个链接从维基百科了解并更新有关斐波那契数列的基本数学信息。然后,看一下这个公式以进行快速计算。你可以在这个链接上阅读有关它的所有内容。
这是一个递归函数来计算第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被认为是常数时)。
对于斐波那契递归序列,也存在一个闭式解,可以在这里查看:http://en.wikipedia.org/wiki/Fibonacci_number,查找Binet或Moivre公式。
并参考以下链接: 1-nth fibonacci number in sublinear time
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}
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)。
方法二(使用动态规划) 我们可以通过存储到目前为止计算出的斐波那契数列来避免方法一中重复的工作。
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];
}
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)
方法四(使用矩阵{{1,1},{0,1}}的幂) 这是另一种O(n)的方法,它依赖于一个事实,即如果我们将矩阵M = {{1,1},{0,1}}自乘n次(换句话说,计算power(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);
}
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;
}
References: http://en.wikipedia.org/wiki/Fibonacci_number http://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);
}
我对这个问题的理解有所不同...给定一个数字
作为输入,该数字在序列中的索引
是多少?例如,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;
}