1133. Fibonacci Sequence
Time limit: 1.0 second
Memory limit: 64 MB
is an infinite sequence of integers that satisfies to Fibonacci condition Fi + 2 = Fi + 1 + Fi for any integer i. Write a program, which calculates the value of Fn for the given values of Fi and Fj.
Input
The input contains five integers in the following order: i, Fi, j, Fj, n.
−1000 ≤ i, j, n ≤ 1000, i ≠ j,
−2·109 ≤ Fk ≤ 2·109 (k = min(i, j, n), …, max(i, j, n)).
Output
The output consists of a single integer, which is the value of Fn.
Sample
| input | output |
|---|---|
| |
Hint
In the example you are given: F3 = 5, F−1 = 4; you asked to find the value of F5. The following Fibonacci sequence can be reconstructed using known values: …, F−1 = 4, F0 = −1, F1 = 3, F2 = 2, F3 = 5, F4 = 7, F5 = 12, … Thus, the answer is: F5 = 12. Problem Source: Quarterfinal, Central region of Russia, Rybinsk, October 17-18 2001
Tags: number theory ( hide tags for unsolved problems )
Fibonacci數列是我從高中開始就接觸,并喜歡上的數列. 經典的遞歸. 動态規劃類涉及題目.
這裡更特殊一點, 不過是在原有的Fibonacci作了變動.
試想 j 是一個比i大一些數. F(i+2) = F(i)+F(i+1) = > 将 F(i+1) , F(i) 記作向量 FF. f[i] 表示正規Fibonacci數列 f1=1 f2=1 f3=2, .... 是以左側等式都可以寫成一個系數向量與FF内積的形式 = (f2,f1) FF F(i+3) = 2F(i+1)+F(i) =(f3,f2) FF F(i+4) = 3F(i+1) + 2F(i) =(f4,f3) FF F(i+5) = 5(i+1) + 3F(i) =(f5,f4) FF ... ... F(i+d) = .. =(fd,f(d-1))* FF
是以當 j與i差距較大時, F(i)與F(j)它們的遞歸關系可以用兩個連續的Fibonacci系數内積來表示.
>> 實際上 如果用高等代數歐氏空間去了解, FF = (F(i+1), F(i) ) 可以視作是此二維空間的一個 基. 此空間中所有的數值都可以用這個基來表示, 表示向量 (a,b) 實際上 可表達為( a= f(k+1), b=f(k) ) 是以表示向量是Fibonacci 數列中的項數k的函數.
j - i 差距 用d來表示 ( 如果輸入的 i 為較大者 交換兩對數值順序)
1<=d < = 3
d = 1, i,j | Fi, Fj 本身就是空間中的基, Fn 可直接由其表示; d = 2\3, i j | Fi, Fj 可簡單推導出 Fi F(i+1)
d > 3
首先 計算好待用的Fibonacci系數. 原題中對i j 大小限制為 : -1000, 1000 是以d上限為2000. 是以 準備的第一個數組f 為 f = Array.new(2001,0) ; f[1]= 1 f[2] = 1 3.upto(d).each {|k| f[k] = f[k-1]+ f[k-2] }
Fj = F(i+d) , Fj - Fi * f(d-1) = F(i+1) * fd , 目的是求 F(i+1) ==>
b = ( ( Fj - f[d-1] *Fi)/f[d] ).floor ( 确定為整數) 實際上 上述所做努力就是為了得到這組基:
F(i) F(i+1)
接下來對n進行分類讨論 用另一組數組 a[] 來計算 存儲結果. a[i] = F(i) a[i+1] = F(i+1)
n > i 從i到n 增向循環, 計算 a[n]
n < i 從n到i 減向循環, 計算 a[n]
