b837 北二104之1 費氏數列

/* b837 1．費氏數列 (104北二區 桃竹苗 )  問題描述
費氏數列(Fibonacci sequence)是以遞迴(Recursive)的方法來定義，如下：
F(0)=0 、 F(1)=1 、 F(n)=F(n-1)+F(n-2) for n>=2
用文字來說，費氏數列是由0和1開始，之後的就由之前的兩數相加。前面幾個費氏數為：0,1,1,2,3,5,13,21,34,55,89,144,233, ……
現在，你一個任務就是寫一個程式來輸出一範圍內的費氏數列以及其數量。
輸入說明 ：
第1列有一正整數t(<10000)表示有t組資料，接著t列，每組包含兩個正整數A,B (0<=A,B<=1000000)，用空格字元做間隔，代表所求費氏級數的範圍。
輸出說明 ：
對於每組測試資料，請輸出所求範圍內(即A<=F(i)<=B 或 B<=F(i)<=A)的所有費氏數F(i)以及數量。若沒有任何符合範圍的費氏數，則輸出0。
兩組資料之間以一列 6 個減號( ------ ) 隔開，請注意：1有兩個 。
例如：第1組 55~220之間有三個費氏數55,89,144、而第2組90~140之間沒有、第3組0是第1個也算1個、第4組1~2之間為1,1,2共三個。
印出費氏數列 vector<int> f
1:0
2:1
3:1
4:2
5:3
6:5
7:8
8:13
9:21
10:34
11:55
12:89
13:144
14:233
15:377
16:610
17:987
18:1597
19:2584
20:4181
21:6765
22:10946
23:17711
24:28657
25:46368
26:75025
27:121393
28:196418
29:317811
30:514229
31:832040
32:1346269
*/
程式碼參考：
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int MaxN = 1000000;
vector<int>f;
void genfib()
{
f.clear();
   f.push_back(0); f.push_back(1);
   int fn=f[0]+f[1];
   int i,j,k;
   for( i=2; fn<=MaxN; ++i)
{
f.push_back(fn);
fn +=f[i-1] ;
}
f.push_back(fn);
k = f.size()-1;
  // for(i=0;i<=k; ++i) cout << i+1 << ':' << f[i] << endl; 
}
int main( )
{
   int t , a,b,c ,i,j;
int lt,lt2,rt;
   genfib();
   cin >> t;
   bool first = true;
   for( i=0; i<t; ++i)
   {
cin >> a >> b;
if(a>b) { c=a; a=b; b=c; }
for(lt=0; f[lt]<=a; ++lt ) if(f[lt]==a) break; 
if (first) first=false; else cout <<"------\n";
  for(j=lt; f[j]<=b; ++j) cout <<f[j]<<endl;
cout << j-lt << endl;
}
   return 0;
}

/*
範例輸入：
6
55 200
90 140
0 0
1 2
2 5
3 0
範例輸出：
55
89
144
3
------
0
------
0
1
------
1
1
2
3
------
2
3
5
3
------
0
1
1
2
3
5
*/