在十進制轉二進制的時候，先找到比它小的最大的一個base即為那個二進制數的最高位，再對剩下的位做同樣的事情，確定每一位。
基本介紹
- 中文名：斐波那契編碼
- 外文名：Fibonacci Codes
記得以前看達文西密碼的時候看到說φ這個東西非常神奇。很多大自然裡面的東西都有φ的比例，像蝴蝶翅膀長寬比，蝸牛殼螺旋的直徑比等等。當東西具有φ的特徵的時候就會讓人感覺特別自然的美感。就像達文西的很多作品，都蘊含著φ。算法裡面二分的時候分成長度比為φ的兩段二分效率最高。而且斐波那契數列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)的數。
*根據上面兩條可以得到斐波那契進制數的減法法則，即100 -> 011的退位。特別地，1000...0 - 1 = 1010...1或1010...0，就是上面那條倒過來用。
*其他還有蠻多結論的，這裡也敘述不清楚了。
所謂斐波那契編碼呢，就是把這個斐波那契進制數倒過來寫，然後在末尾追加一個1。
很神奇的東西吧。但是我也敘述不清楚。
然後是黃金進制。它的base是φ的次冪，也就是說用φ的若干次冪表示一位，同樣用01表示。
φ是一個無理數，卻能通過這個方式用有限小數形式表示每一個非負整數。
它的性質很顯然：φ^2 = φ + 1。
通過這個式子就能推導出φ進制的一些規律，其中第一條就和斐波那契進制一樣011 = 100。顯然的對不對；
然後假設在計算過程中出現了2，則0200 = 1001。因為2 * φ^2 = φ^2 + φ + 1 = φ(φ + 1) + 1 = φ^3 + 1；
假設計算過程中出現了-1（用1表示），則010 = 101。因為 -φ = -φ^2 + 1；
這樣我們就可以把一個不標準的φ進制數化成標準的φ進制數。轉化過程在wikipedia裡面很詳細介紹了這裡就不贅述了。
十進制整數化成φ進制數和普通進制轉換是同樣的方法，但由於它是無理數所以過程稍顯麻煩，但是如果已知一個數求另一個數就可以用φ進制的加減法來做了。加減法在wikipedia也有舉例，難倒是不難，就是感覺有些亂挺容易弄糊塗的。
