[POI 19 Stage 2] Fibonacci Representation

作法：

大概可以想的到是某種貪心。當給定一個 n 時，若 n 是某個 F_x ，那麼答案當然是 1 。否則令 F_x < n < F_(x+1) ，那麼最佳的取法就是取 +F_x 或是 +F_(x+1) ，這樣就只需湊出 n - F_x 或是 F_(x+1) - n ，取兩者之中比較小的那個一直做下去就可以了。

這個作法看起來很合理，這裡給一個大概的證明：

之後的證明會用到以下幾個引理：
1. 最佳的取法中不會出現 +F_x 和 +F_(x+1) 。2. 最佳的取法中不會出現 +F_x 和 -F_(x-1) 。
3. 最佳的取法中不會出現 +F_x 和 -F_(x-2) 。

4. F_x >= F_(x-1) + F_(x-3) + ... 。

其中 1~3 是顯然的，而 4 可以把 F_(x-1) 搬到左邊消掉然後數歸下去。

第一個要證明的是為什麼取 +F_x 或是 +F_(x+1)是最好的。如果取 +F_(x+2) 的話，由前面的引理知道不會取 +F_(x+1) 或是 -F_(x+1) ，也不會取 -F_x，這樣一來能得到的最小數就會是 F_(x+2) - F_(x-1) - F_(x-3) - ... >= F_(x+2) - F_x = F_(x+1) > n ，矛盾。如果取的是 > F_(x+2) 的數的話一樣可以推到矛盾。又如果取的是 F_(x-1) 或更小的數的話，能得到的最大樹就會是 F_(x-1) + F_(x-3) + ... <= F_x < n ，矛盾。所以取 F_x 或是 F_(x+1) 會是最好的。

再來則是為什麼 n - F_x 和 F_(x+1) - n 之中比較小的那個數可以用比較少個 F 湊出來。注意到這兩數相加 = F_(x-1) ，所以這件事會等價於：有兩個數 n , m ，滿足 n +m = F_k  且 n < m，則 n 可以用比較少個 F 湊出來。這只要注意到：因為 2*m > F_k = F_(k-1) +F_(k-2) > 2*F_(k-2) ，所以 m > F_(k-2) ，也就是組成 m 的最大的 F 值只可能是 F_(k-2) , F_(k-1) 或 F_k ，那麼考慮把 m 的組成直接用 F_k 減掉，並且如果 m 最高位是 F_k 的話直接消掉，如果不是的話就把 F_k 改成 F_(k-1) + F_(k-2) 根其中一個消掉，這樣我們得到了 n 的一個拆法，它拆出來的個數會 <= m 拆出來的個數，得證。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
LL F[100] ;
main()
{
    F[1]=F[2]=1 ;
    for(int i=3;i<100;i++) F[i]=F[i-1]+F[i-2] ;
    int T; scanf("%d",&T) ;
    while(T--)
    {
        LL x ; scanf("%lld",&x) ;
        int ans=0 ;
        while(x)
        {
            int i ;
            for(i=1;F[i]<x;i++) ;
            ans++ ; x=min(F[i]-x,x-F[i-1]) ;
        }
        printf("%d\n",ans) ;
    }
}