简介

记得以前看达芬奇密码的时候看到说φ这个东西非常神奇。很多大自然里面的东西都有φ的比例，像蝴蝶翅膀长宽比，蜗牛壳螺旋的直径比等等。当东西具有φ的特征的时候就会让人感觉特别自然的美感。就像达芬奇的很多作品，都蕴含着φ。算法里面二分的时候分成长度比为φ的两段二分效率最高。而且斐波那契数列1,1,2,3,5,8,13...到后面很多很多项的时候后一项与前一项的比值越来越接近φ。或许这个性质决定了斐波那契编码和黄金进制联系紧密。

斐波那契进制和斐波那契编码的表示略有不同，但是原理是一样的。就像二进制里面每一位都有对应的二的次幂（我喜欢叫它base），斐波那契进制的每一位的base就是斐波那契数列的每一个数，在进制转换的时候就可以按照一样的方法转换。在十进制转二进制的时候，先找到比它小的最大的一个base即为那个二进制数的最高位，再对剩下的位做同样的事情，确定每一位。十进制转斐波那契进制的时候也是同样的道理:

base:

1(10) = 1(fib);

2(10) = 10(fib);

3(10) = 100(fib);

5(10) = 1000(fib);

8(10) = 10000(fib);

...

e.g.

4(10) = 3(10) + 1(10) = 101(fib);

6(10) = 5(10) + 1(10) = 1001(fib);

7(10) = 5(10) + 2(10) = 1010(fib);

12(10) = 8(10) + 3(10) + 1(10) = 10101(fib);

...

根据斐波那契进制的本质和定义，可以得出一些结论：

*得到的斐波那契进制数中不会出现"11"的情况，因为base的特点是base[i] = base[i - 1] + base[i - 2]。即斐波那契数列的性质。因此011(fib) = 100(fib)。

*p位数的斐波那契进制数中，最大的一个必定是101010...1(p % 2 == 1)或者101010...0(p % 2 == 0)。根据上面的那条也很显然。这类数一旦加一，就会通过多次011 -> 100 的进位转化成1000...0(p个0)的数。