Problem 155 再び(C++)

Haskellが遅かった．

1分以上．

そこで，単純な全探索を少し工夫して，しかも，C++で実装したら，

5秒未満になった．

#include <iostream>
#include <vector>
#include <boost/rational.hpp>
#include <boost/foreach.hpp>
#define FOREACH BOOST_FOREACH
using namespace std;
typedef boost::rational<int> rat;
static const int n = 18;
int fib(int n) {
int p = 1, q = ;
for (int i = ; i < n; i++, p += q, q = p - q) ;
return p;
}
int main(){
vector< vector<bool> > u(fib(n) + 1, vector<bool>(fib(n) + 1));
vector< vector<rat> > cs(n + 1, vector<rat>());
cs[1].push_back(rat(1)); u[1][1] = true; long long c = ;
for (int i = 1; i <= n; c += cs[i++].size())
for (int j = 1; j <= i / 2; j++)
FOREACH (rat c1, cs[j]) FOREACH (rat c2, cs[i-j]) {
rat t = c1 + c2;
if (u[t.numerator()][t.denominator()]) continue;
cs[i].push_back(t); cs[i].push_back(1 / t);
u[t.numerator()][t.denominator()] = u[t.denominator()][t.numerator()] = true;
}
cout << c << endl;
}

boost使ってみた．

fibがでてくるのは観察から，多分正しい（少なくとも n が18以下では正しい）．

証明はまだ，ない．