The Stern-Brocot Number System

PC/UVa IDs: 110507/10077

分析:Stern-Brocot树的每个节点(包括根节点)都是由两个分数生成的,分别记其为left, right。生成规则为:
mid.numerator = left.numerator + right.numerator
mid.denominator = left.denominator + right.denominator
且有:
left < mid < right
根据规则,一边生成节点一边二分查找即可。

#include <iostream>
#include <vector>

using namespace std;

typedef long long llt;

class Fraction {
public:
  Fraction(unsigned int a, unsigned int b) : _n(a), _d(b) {}

  Fraction(const Fraction & f) : _n(f._n), _d(f._d) {}

  Fraction & operator =(const Fraction & f) {
    _n = f._n;
    _d = f._d;
    return *this;
  }

  bool operator <(const Fraction & f) const {
    return (llt)_n * f._d - (llt)_d * f._n < 0;
  }

  bool operator !=(const Fraction & f) const {
    return !(_n == f._n && _d == f._d);
  }

  Fraction middle(const Fraction & f) const {
    return Fraction(_n + f._n, _d + f._d);
  }

private:
  unsigned int _n; //numerator
  unsigned int _d; //denominator
};

vector<char> stern_brocot_path(const Fraction & f) {
  vector<char> path;
  Fraction mid(1, 1);
  Fraction left(0, 1);
  Fraction right(1, 0);
  while (f != mid) {
    if (f < mid) {
      right = mid;
      mid = mid.middle(left);
      path.push_back('L');
    }
    else {
      left = mid;
      mid = mid.middle(right);
      path.push_back('R');
    }
  }
  return path;
}

int main() {
  unsigned int a, b;
  while ((cin >> a >> b) && !(a == 1 && b == 1)) {
    vector<char> path = stern_brocot_path(Fraction(a, b));
    for (int i = 0; i < path.size(); i++)
      cout << path[i];
    cout << endl;
  }
  return 0;
}

《The Stern-Brocot Number System》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

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

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