問題概要
正整数 N が与えられる。N との差が最も小さいフィボナッチ数と N との差(の絶対値)を求めよ。
解法
N がフィボナッチ数であるか否かに関わらず、解候補となるフィボナッチ数は、N 以下のフィボナッチ数の内最大のものと、N を超えるフィボナッチ数の内最小のものの二つのみです。従って、a, b を連続する二つのフィボナッチ数として、b <= N である間、a, b を次の項へ進めるループを回すことで、解候補となるフィボナッチ数二つを生成できます。後は、N - a と b - N の内小さい方を return すれば okay です。
コード
class FibonacciDiv2 { public: int find(int N) { int a = 0, b = 1; while ( b <= N ) { const int c = a + b; a = b; b = c; } return min( N - a, b - N ); } };