fibonacci数列二进制转换的问题

问题：

Just as numbers can be represented in a positional
notation as sums of multiples of the powers of ten
(decimal) or two (binary); all the positive integers
can be represented as the sum of one or zero times
the distinct members of the Fibonacci series.
Recall that the first six distinct Fibonacci numbers
are: 1, 2, 3, 5, 8, 13.
The decimal number eleven can be written as
0 * 13 + 1 * 8 + 0 * 5 + 1 * 3 + 0 * 2 + 0 * 1
or 010100 in positional notation where the columns
represent multiplication by a particular member of the
sequence. Leading zeroes are dropped so that eleven
decimal becomes 10100.
10100 is not the only way to make eleven from the
Fibonacci numbers however;
0 * 13 + 1 * 8 + 0 * 5 + 0 * 3 + 1 * 2 + 1 * 1
or 010011 would also represent decimal 11. For a true
Zeckendorf number there is the added restriction that
no two consecutive Fibonacci numbers can be used which
leads to the former unique solution.
In this problem, your task is to change decimal numbers (D) to Zeckendorf number (Z).

将十进制数转成fibonacci数的二进制

image.png

问题分析：

左边的数通过对fibonacci的1和0变换来进行对十进制数的表示。分析下二进制转十进制的变换
b2^n+....+ b2^3 + b2^2 + b2^1 =f(n)(b=1或b=1)，将2^n变为fibonacci函数即可

代码

 /**
     * fibonacci数列 f(n)=f(n-1)+f(n-2) n>=3；从1，2，3，5开始，
     *
     * @param n
     * @return
     */
    public static long fibonacci(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        n = n + 1;
        long arr[] = new long[n + 1];
        arr[0] = 0;
        arr[1] = 1;           //n不能为0，因为n为0时，arr大小为1，arr[1]越界。
        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

  /**
     * 转换函数（从高位用fibonacci除再转二进制）
     *
     * @param n
     * @return
     */
    public static String specialDToBinary(int n) {
        String str = "";
        long left = n;
       // 去零标志位
        boolean beginNum = false;
        while (left > 0) {
            // 从高位往下走
            for (int i = n; i > 0; i--) {
                // 除以fibonacci数，看是否大于2
                long sub = left / fibonacci(i);
                long locNum = sub % 2;
                if (locNum > 0) {
                    beginNum = true;
                    left = left - fibonacci(i);
                }
                if (beginNum)
                    str = str + locNum;
            }
        }
        return str;
    }

测试

  public static void main(String[] args) {
        for (int i = 1; i <= 20; i++) {
            System.out.println(i + "经过转换为:" + specialDToBinary(i));
        }
    }

程序转换成功

image.png