Description：

给出一个正整数 $x$ ，问 $x$ 最少能由多少个 $Fibonacci$ 数加减算出。

$1\leqslant q \leqslant 10,1\leqslant n \leqslant 10^7$

Solution：

贪心，每次二分查出它前面和它后面的斐波那契数，做差选较小的一个，之所以这样做是正确的是因为由斐波那契数列 $f[i]=f[i-1]+f[i-2]$ 可得斐波那契数列具有天然的决策包含性，也就是说大的一定包含小的，于其选小的不如选大的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int q;

typedef long long ll;

ll f[90];

ll n;

int main()

{

	scanf("%d",&q);

	f[1] = f[2] = 1;

	for(int i = 3;i < 90;++i)

	{

		f[i] = f[i - 1] + f[i - 2];

	}

	for(int i = 1;i <= q;++i)

	{

		int res = 0;

		scanf("%lld",&n);

		while(n > 0)

		{

			int p = upper_bound(f + 1,f + 90,n) - f;

			n = min(f[p] - n,n - f[p - 1]);

			++res;

		}

		printf("%d\n",res);

	}

	return 0;

}