给定fibonacci数列的一项，如何求得它在数列中的项数

g99

1，1，2，3，5，8，13，21，34，55，。。。
比如我给出21，那么他在数列中的项数为8

不要说一一计算，再对比：）

liangbch

fibonacci 数列是有通项公式的，见下，解出这个方程即可
$a_n= sqrt(5)/5( (1+sqrt(5))/2)^n- sqrt(5)/5( (1-sqrt(5))/2)^n$

风云剑

通项公式

liangbch

解这个方程的最简单，但不是最好的方法。是2分法。因为这个序列是单调递增的，使用类似2分查找的算法，复杂度是log2(n)

gxqcn

比如 Fib(1) = Fib(2) = 1，
以及有 $Fib(-n)=(-1)^(n+1) * Fib(n) \quad (n in ZZ )$

liangbch

忘了说了，2楼的公式中，n是大于等于1的整数。

medie2005

设fibonacci序列中某项的值为x，那么，
1）：若x==1,则序号是1或者2。
2）：否则，它的序号是:log(x*5/sqrt(5))/log((sqrt(5)+1)/2)的四舍五入的整数。

g99

to liangbch：二分法，你现在没有数列的表，怎么查找？计算出来一一查找的话，时间复杂度不小啊
to medie2005：log(x*5/sqrt(5))/log((sqrt(5)+1)/2)你这个公式是怎么算出来的？

mathe

medie2005的方法就是利用通项公式计算的

liangbch

to liangbch：二分法，你现在没有数列的表，怎么查找？计算出来一一查找的话，时间复杂度不小啊

不需要对所有的项计算的，
  如low=1, high=k ,k满足$a_k>x$
          k的值的确立过程，
    计算前8项fibonacci 数列，由于该数列近似于等比数列，其公比是1.618, 因此不难求的$a_k= a_8 * 1.618^(k-8)$

  计算中位数 m= (low+hight)/2 , 然后计算 $a_m$,
         如 $x> a_m$ 则 low=m ,否则 high=m, 如此反复，最终在经过log2(K)次迭代可得到结果。

另外，由于fibonacci 数列近似于公比为1.618的等比数列。很容易求的k，使得 a_k近似于x。 然后在k附近查找就可以了。