我不一定要找的答案，但我要寻找什么这个问题是问的。 发现这个问题接受采访，但不知道他们是问学习？
编写通过斐波那契序列运行并返回传递作为参数的指数函数。
Answer 1:
首先，你可以更新与此有关斐波纳契你的基础的数学信息的链接从维基。 并期待在这个公式为快速calculate.and你可以阅读所有关于它在这个环节 。
这是递归函数来计算第n个Fibonacci数和为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（日志（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完成（日志（n））的时间（当x被认为是恒定的）。
对于斐波那契复发，也有一个封闭的公式的解决方案，在这里看到http://en.wikipedia.org/wiki/Fibonacci_number ，寻找比奈的或棣美弗公式。
看看：1- 在次线性时间n个斐波纳契数
Answer 2:
什么在我看来，是你被要求返回第n个斐波那契数号，其中n是传递的参数。 您可以使用各种方法来回答这个问题，而所有这些在时间复杂度和代码的复杂变化。
方法1（用递归）的简单方法是上面给出的直接recusrive执行数学recurance关系。
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）的，如果我们考虑fuinction调用堆栈大小，否则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（空间Otimized方法2）我们可以通过将前面的两个数字，只是因为这是所有我们需要得到在系列的下Fibannaci数优化方法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（使用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（n）的额外空间：O（1）
方法5（优化方法4）的方法，4可以被优化为O工作（logN）的时间复杂度。 我们可以做递归乘法来获得在prevous方法电源（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主（）{INT N = 9; printf("%d", fib(9)); 的printf（ “％d”，FIB（9））; getchar(); 的getchar（）; return 0; 返回0; } }
参考文献： http://en.wikipedia.org/wiki/Fibonacci_number http://www.ics.uci.edu/~eppstein/161/960109.html
Answer 3:
这是一个非常不好的措辞问题，但你必须承担他们所要求的第 n Fibonnaci数，其中n作为参数提供。
除了由他人列出的所有技术， n > 1也可以使用黄金比例的方法 ，这是比任何迭代方法更快。 但随着问题说“通过斐波纳契数列运行”这可能不符合。 你可能也就能把人吓死。
Answer 4:
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 5:
我解释给定的问题不同.... 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;
}
文章来源: Algorithm function for fibonacci series [closed]
