torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, SRM 622, Division 2, Level 1 : FibonacciDiv2

問題概要

 正整数 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 );
	}
};