给定fibonacci数列的一项，如何求得它在数列中的项数
1，1，2，3，5，8，13，21，34，55，。。。比如我给出21，那么他在数列中的项数为8
不要说一一计算，再对比：） fibonacci 数列是有通项公式的，见下，解出这个方程即可
a_n= sqrt(5)/5( (1+sqrt(5))/2)^n- sqrt(5)/5( (1-sqrt(5))/2)^n 通项公式 解这个方程的最简单，但不是最好的方法。是2分法。因为这个序列是单调递增的，使用类似2分查找的算法，复杂度是log2(n)
结果可能不唯一
比如 Fib(1) = Fib(2) = 1，以及有 $Fib(-n)=(-1)^(n+1) * Fib(n) \quad (n in ZZ )$ 忘了说了，2楼的公式中，n是大于等于1的整数。 设fibonacci序列中某项的值为x，那么，
1）：若x==1,则序号是1或者2。
2）：否则，它的序号是:log(x*5/sqrt(5))/log((sqrt(5)+1)/2)的四舍五入的整数。 to liangbch：二分法，你现在没有数列的表，怎么查找？计算出来一一查找的话，时间复杂度不小啊
to medie2005：log(x*5/sqrt(5))/log((sqrt(5)+1)/2)你这个公式是怎么算出来的？ medie2005的方法就是利用通项公式计算的 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附近查找就可以了。
页:
[1]
2