How many Fibs?

How many Fibs?

时间： 1ms        内存：64M

描述：

Recall the definition of the Fibonacci numbers:

f1 := 1 

f2 := 2 

fn := fn-1 + fn-2     (n>=3) 

Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b].

输入：

The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a<=b<=10¹⁰⁰. The numbers a and b are given with no superfluous leading zeros.

输出：

For each test case output on a single line the number of Fibonacci numbers f _i with a<=f_i<=b.

示例输入：

10 100
1234567890 9876543210
0 0

示例输出：

5
4

提示：

参考答案（内存最优[1272]）：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// F_n = 1/sqrt(5) * ((1/2 + sqrt(5)/2)^n - (1/2 - sqrt(5)/2)^n) <= 2^n+1
// therefore there aren't too many (less than 2*2*log(10^100) approx. 800) fibs

typedef vector <string> tVec;



string add(string s1, string s2) {
  string r(101u, '0');
  int carry = 0;
  for (int i=100; i >= 0; i--) {
	int next = carry + (s1[i]-'0') + (s2[i]-'0');
	r[i] = (next % 10) + '0';
        carry = next / 10;
  }
  return r;
}

int main() {
  string s(101u, '0');
  tVec   v;
  s[100] = '1';
  v.push_back(s);
  s[100] = '2';
  v.push_back(s);
  while (1) {
     s = add(v[v.size()-2], v[v.size()-1]);  
     if (s > "10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")
       break;
     v.push_back(s);
  }

  while (1) {
    string a, b;
    cin >> a >> b;
    if (b == "0")
      break;
    while (a.length() < 101) a = "0" + a;
    while (b.length() < 101) b = "0" + b;
    int pos;
    for (pos = 0; pos < v.size() && v[pos] < a; pos++);
    int counter = 0;
    for ( ; pos < v.size() && v[pos] <= b; pos++, counter++);
    cout << counter << endl;  	    
  }

  return 0;
}  

参考答案（时间最优[28]）：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// F_n = 1/sqrt(5) * ((1/2 + sqrt(5)/2)^n - (1/2 - sqrt(5)/2)^n) <= 2^n+1
// therefore there aren't too many (less than 2*2*log(10^100) approx. 800) fibs

typedef vector <string> tVec;



string add(string s1, string s2) {
  string r(101u, '0');
  int carry = 0;
  for (int i=100; i >= 0; i--) {
	int next = carry + (s1[i]-'0') + (s2[i]-'0');
	r[i] = (next % 10) + '0';
        carry = next / 10;
  }
  return r;
}

int main() {
  string s(101u, '0');
  tVec   v;
  s[100] = '1';
  v.push_back(s);
  s[100] = '2';
  v.push_back(s);
  while (1) {
     s = add(v[v.size()-2], v[v.size()-1]);  
     if (s > "10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")
       break;
     v.push_back(s);
  }

  while (1) {
    string a, b;
    cin >> a >> b;
    if (b == "0")
      break;
    while (a.length() < 101) a = "0" + a;
    while (b.length() < 101) b = "0" + b;
    int pos;
    for (pos = 0; pos < v.size() && v[pos] < a; pos++);
    int counter = 0;
    for ( ; pos < v.size() && v[pos] <= b; pos++, counter++);
    cout << counter << endl;  	    
  }

  return 0;
}  

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。