TopCoder 練習 FibonacciPositioning(SRM298 Div1 Easy)

ニコ生にて，診断人さんがTopCoderの問題を解きまくっていたので，途中から便乗参加．

FibonacciPositioning(SRM298 Div1 Easy)

■問題
Fibonacci positionという値を定義する．n番目のFibonacci数をF_n，Fibonacci positionをFP_nとする時，FP_nは以下の通り．

FP₁=2
F_i=nの時，FP_n=i
F_i<n<F_i+1の時，FP=i+(n-F_i)/(F_i+1-F_i)

FP_nを求めよ．

■解法
問題の通り愚直に実装すればOK．

view plainprint?

1. public class FibonacciPositioning{  
2.  public double getFPosition(int n){  
3.   if(n==1) return 2.0;  
4.   long a=1,b=1;  
5.   for(int i=1;;i++){  
6.    if(n==a)  
7.     return i;  
8.    if(a<n&&n<b)  
9.     return i+(double)(n-a)/(b-a);  
10.    a+=b;  
11.    long t=a; a=b; b=t;  
12.   }  
13.  }  
14. }  

public class FibonacciPositioning{
 public double getFPosition(int n){
  if(n==1) return 2.0;
  long a=1,b=1;
  for(int i=1;;i++){
   if(n==a)
    return i;
   if(a<n&&n<b)
    return i+(double)(n-a)/(b-a);
   a+=b;
   long t=a; a=b; b=t;
  }
 }
}