111qqz的小窝

老年咸鱼冲锋!

Fibonacci number’s ratio (the hard version)

Problem C. Fibonacci number’s ratio (the hard version)
Input file:
Output file:
Time limit:
Memory limit:
stdin
stdout
2s
512 Mb
Fibonacci numbers have many remarkable properties. For example, the ratio of two successive Fibonacci numbers
tends to the golden ratio:

F n+1
1+ 5
lim
=
.
n→∞ F n
2
You are going to test this property for generalized Fibonacci numbers
G n = aG n−1 + bG n−2 ,
n ≥ 2.
For given a, b, G 0 and G 1 calculate the limit
G n+1
,
n→∞ G n
lim
if it exists.
Input
The first line contains four integers a, b, G 0 , G 1 from −1000 to 1000.
Output
Print “YES” in the first line, if the limit exists, and “NO” otherwise. In the case of the positive result, print the
limit itself in the second line. Absolute or relative error must not exceed 10 −6 .
Examples
stdin
1 1 1 1
0 0 1 1
stdout
YES
1.6180339887
NO
Note
If the sequence G n contains an infinite number of zeros, the limit does not exist.

 

求极限。

细节比较坑,主要是可能为0

为不乱,可以把a,b,g0,g1为0 的情况分别列出来。

g[n]=a*g[n-1]+b*g[n-2];

g[n]/g[n-1] = a + b *(g[n-2]/g[n-1])

假设 g[n]/g[n-1]的极限存在,社为k

那么有 k = a + b * (1/k)

k*k-a*k-b=0;

delta = sqrt(a*a+4(b)

lim = (1+delta)/2.0  or (1-delta)/2.0;

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363