公式如下：
递归的解法我就不写了，贴一个递推的。
long long Fibonacci(unsigned int n) { if (n <= 0) return 0; if (n == 1) return 1; long long a = 0; long long b = 1; long long res; for (int i = 2; i <= n; ++i) { res = a + b; a = b; b = res; } return res; }
相似问题1：
一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
相似问题2：
某年夏天,位于希格玛大厦四层的微软亚洲研究院对办公楼的天井进行了一次大 规模的装修.原来的地板铺有 N×M 块正方形瓷砖,这些瓷砖都已经破损老化了,需要予以 更新.
装修工人们在前往商店选购新的瓷砖时,发现商店目前只供应长方形的瓷砖,现在的 一块长方形瓷砖相当于原来的两块正方形瓷砖, 工人们拿不定主意该买多少了。
读者朋友们 请帮忙分析一下:能否用 1×2 的瓷砖去覆盖 N×M 的地板呢?
原文：http://www.cnblogs.com/gattaca/p/4646419.html