#21. [语言题]斐波那契数列

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: admin

题目描述

斐波那契数列的定义如下:

f(1) = 1

f(2) = 1

f(n) = f(n-1) + f(n-2) (n >= 2)

现在给你两个整数a和b,问你有多少个n使得a <= f(n) <= b

背景:斐波那契在《算盘书》中提出了一个有趣的兔子问题

一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔都不死,那么一年以后可以繁殖多少对兔子?

我们不妨拿新出生的一对小兔子分析一下:

第一个月小兔子没有繁殖能力,所以还是一对;

两个月后,生下一对小兔总数共有两对;

三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对;

……

依次类推1,1,2,3,5,8,13,21,34,55,89,144,233。。。---构成了一个序列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。

这个数列是意大利中世纪数学家斐波那契在《算盘书》中提出的,这个级数的通项公式,除了具有an+2=an+an+1的性质外,还可以证明通项公式为:an=1/√5 (1/2+√5/2)^ n-(1/2-√5/2)^n(√5表示根号 5)。

这个通项公式中虽然所有的an都是正整数,可是它们却是由一些无理数表示出来的。

即在较高的序列,两个连续的"斐波纳契数"的序列相互分割将接近黄金比例(1.618:1或1:0.618)。

例如:233/144,987/610……

斐波那契数列还有两个有趣的性质

⒈斐波那契数列中任一项的平方数都等于跟它相邻的前后两项的乘积加1或减1;

⒉任取相邻的四个斐波那契数,中间两数之积(内积)与两边两数之积(外积)相差1。

输入格式

一行两个整数a和b

输出格式

一个整数,为有多少个f(n)满足,a <= f(n) <= b

样例

####样例输入

3 9

####样例输出

3

####样例解释 斐波那契数列为1, 1, 2, 3, 5, 8, 13...,其中3,5,8在3到9的范围内,有3个数字

数据范围与提示

对于全部的数据0 <= a, b <= 1000000