题目链接
题目描述
Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, ...，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 36;
int num[maxn]; 
int fib(int i);
int main()
{
    memset(num,0,sizeof(num));
    fib(35);
    int n;
    while(cin>>n)
    {
        int ans;
        int *a;
        a=lower_bound(num,num+36,n);
        ans=(*a)-n<(n-*(a-1))?(*a)-n : (n-*(a-1));
        cout<<ans<<endl;
    }
    return 0;
}
int fib(int i)
{
    if(num[i]==0)
    {
        if(i==1 || i==2)
        {
            num[i]=1;
            return 1;
        }else 
        {
            num[i-1]=fib(i-1);
            num[i-2]=fib(i-2);
            return num[i]=num[i-1]+num[i-2];
        }        
    }
    else return num[i];
}