きままにブログ

プログラミングを主とした私のメモ帳です。寂しいのでコメントください笑

Project Euler Problem 2

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

Project Euler Problem 1の追記で示したように、Rangeオブジェクトは++演算子と<=演算子さえあれば全てのオブジェクトに対してfilter, reduce可能である。そこで、reduceの結果を元の方と異なってもいいように変更した上で、

Range<Fibonacci> range(Fibonacci(0, 1), Fibonacci(400 * 10000));
auto ret = range
	.filter([](const Fibonacci& it) {
	return it % 2 == 0;
})
	.reduce<int>(
	[](const Fibonacci& left, const Fibonacci& right) {
	return left + right;
});
printf("\nsum = %d", ret); // 4613732

このように書けるようにした。

実装

struct Fibonacci {
	Fibonacci(int value) : value(value) {  }
	Fibonacci(int m, int n) : before1(n), before2(m), value(m + n) {  }
	Fibonacci(const Fibonacci& it) : value(it.value),
	before1(it.before1), before2(it.before2) { }
	Fibonacci& operator=(const Fibonacci& it) {
		value = it.value;
		before1 = it.before1;
		before2 = it.before2;
	}
	bool operator <=(const Fibonacci& it) const {
		return value <= it.value;
	}
	operator int() const { return value; }
	Fibonacci& operator++() {
		before2 = before1;
		before1 = value;
		value = before1 + before2;
		return *this;
	}
	Fibonacci operator++(int) {
		Fibonacci ret = *this;
		operator++();
		return ret;
	}
private:
	int value;
	int before1;
	int before2;
};

template <typename SELF, typename T>
struct Filter_t {
	Filter_t() : filter_function([](const T&) { return true; }) { }
	SELF& filter(function<bool(const T&)> filter_function) {
		this->filter_function = filter_function;
		return *static_cast<SELF*>(this);
	}
	bool operator()(const T& it) const { return filter_function(it); }
protected:
	function<bool(const T&)> filter_function;
};

template <typename T>
class Range : public Filter_t<Range<T>, T> {
public:
	Range(T m, T n) : m(m), n(n) { }
	
	template <typename S>
	S reduce(function<S(const T&, const T&)> func) const {
		S ret;
		T value = m;
		for(; value <= n; ++value) {
			if(filter_function(value)) {
				ret = value;
				break;
			}
		}
		for(++value; value <= n; ++value) {
			if(filter_function(value)) {
				ret = func(ret, value);
			}
		}
		return ret;
	}
private:
	T m;
	T n;
};