How Many Fibs?

PC/UVa IDs: 110601/10183

分析:6.4节《其他计数序列》里给出了Fibonacci数列的封闭形式,提示里也说“能否借助封闭形式来避免高精度算数”,但高精度算数还是无法避免。理由如下:
F(n) = (a ^ n – b ^ n) / c
其中a,b,c为常数:
a = (1 + 5 ^ (1 / 2)) / 2
b = (1 – 5 ^ (1 / 2)) / 2
c = 5 ^ (1 / 2)
因为abs(b) < 1,所以当n比较大时可以忽略b ^ n,直接用:
(a ^ n) / c
来估计F(n),误差在正负1之间。
另一方面,当输入数字比较大时,如10 ^ 100,即使用80位的long double(其中精度可达64位),也不能精确表示它,更不要说区分正负1的误差了。
综上,高精度算数是唯一选择。当然这对C/C++比较痛苦,因为没有现成的标准库可以用。以下“bigint.h”为笔者自创。
解法:根据输入范围先算好一个Fibonaaci数列的子序列,然后对输入的数在该序列中进行二分查找。

#include <iostream>
#include <vector>
#include "bigint.h"

using namespace std;

vector<BigInt> fib;

void init() {
  fib.reserve(501);
  fib.push_back(0);
  fib.push_back(1);
  fib.push_back(2);
  for (int i = 0; i < 498; i++) {
    int l = fib.size() - 1;
    fib.push_back(fib[l] + fib[l - 1]);
  }
}

int bsearch(const BigInt & v, int s/* start */, int e/* end */) {
  int i;
  int mid = (s + e) / 2;
  int r = v.compare(fib[mid]);
  if (!r) {
    i = mid;
  }
  else if (r < 0) {
    if (s == mid)
      i = s - 1;
    else
      i = bsearch(v, s, mid);
  }
  else {
    if (e == mid + 1)
      i = mid;
    else
      i = bsearch(v, mid + 1, e);
  }
  return i;
}

inline int fibs(const BigInt & a) {
  return a.zero() ? 0 : bsearch(a, 0, fib.size());
}

inline int fibs(const BigInt & a, const BigInt & b) {
  return a.zero() ? fibs(b) : fibs(b) - fibs(a - 1);
}

int main() {
  init();
  BigInt a, b;
  while (cin >> a >> b && !(a.zero() && b.zero())) {
    cout << fibs(a, b) << endl;
  }
  return 0;
}

《How Many Fibs?》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>