TopCoder SRM 298 Div1 Easy FibonacciPositioning

問題

フィボナッチ数は、F1=1, F2=1, Fn=Fn-1+Fn-2で定義される数列である。
1以上の整数について、fibonacci positionというものを考える。
1のfibonacci positionは2である。
nのfibonacci positionはFi=nとなるiがあるとき、iである。
ないとき、Fi＜nとなる最大のiを使って、i+(n-Fi)/(Fi+1-Fi)である。

与えられた整数に対してfibonacci positionを求めよ。

制約条件

n≦10^8

方針

定義にしたがって計算する。
n=1の場合だけ場合わけ。

ソースコード

struct FibonacciPositioning{
	double getFPosition(int n){
		if(n==1)return 2;
		
		int a=1, b=1, k=1;
		while(b<n){
			int t=a+b;
			a=b; b=t;
			k++;
		}
		return k+(n-a)*1.0/(b-a);
	}
};