编程之邦第二章斐波那契

子午书屋>编程之邦 > 第二章斐波那契（第1页）

第二章斐波那契

神圣罗马帝国皇室图书馆，海量的书架井然有序。

一位头戴王冠的中年男子和一位学者在这里促膝长谈。

此时夜深人静，牛油烛散发出柔和的光芒，勉强能照亮小块区域。

“斐波那契，你这兔子问题，寡人想了很久都没有头绪”，中年男子挠了挠头。

腓特烈二世生平最大的业余爱好便是研究数学，而他眼前这位学者，便是他的座上客，大名鼎鼎的斐波那契。

“兔生二月便能繁衍，每月每对兔可生一对幼兔，则一年可得兔几何？”，腓特烈自言自语道。

“二月之后可新生一对兔，故三月为两对兔，四月幼兔不足两月，故为三对兔，以此类推...”，斐波那契耐心地解答。

“哈哈哈哈！爱卿果然才思敏捷！”，腓特烈二世竖起了大拇指，眼中满是赞赏之色。

“孤欲编纂《算书》，卿可为之”，说完，君臣两人离席。

斐波那契走在回住所的路上，脑海中却在回想刚才谈话的内容，似乎有所明悟。

“何不将该类问题，阐述为通项公式？”，他喃喃自语。

回到住所，斐波那契赶紧打开一个小册子，拿起鹅毛笔蘸了蘸墨水，写下刚才的想法。

“若有f0为0，f1为1，则fn为fn-1与fn-2之和”。

斐波那契抬头看了看窗外的月光，那树梢之上，停留着一只枯叶蝶，那蝴蝶似乎有所感应，循着灯光，翩翩飞舞。

斐波那契还在专注地思考着，根本没有察觉这只蝴蝶正朝着他飞过来。

第二章斐波那契

那蝴蝶飞过了窗台，然后轻轻地落在了斐波那契的肩头。

下一刻，蝴蝶消失了，杨成的意识出现在了斐波那契脑海中。

“哇！”，杨成惊讶地看着自己这身古欧洲的学者服饰，然后摸了摸下巴。

他感觉自己的体貌特征来了个180度大转变。

眼前的小册子在烛光下浮现出一行行字，顿时吸引了杨成的注意力。

“已知斐波那契通项公式fn=fn-1+fn-2，编写求第N项斐波那契数的函数，N在100以内”。

杨成瞪大了眼睛，这里电脑都没有，只有一枝鹅毛笔，怎么写啊？

手写？似乎问题也不是很大，求100项以内的斐波那契数，完全可以用简单的递归啊！

杨成回忆了一下，然后用鹅毛笔蘸了蘸墨水，在小册子上写了寥寥几行。

这是一种“教科书式”的分治法求解，要求第N项，那么就分解为求第N-1项和第N-2项，那N-1项又可以分解为求N-2和N-3项，以此类推，直到N为0，返回0，N为1，返回1.

但这种分治法之所以被称作“教科书式”，一是因为通俗易懂，二是因为效率低下。求重复的项数太多了，或者说重复计算太多了。

杨成很清楚这种方法的弊端，但应付100以内的，绰绰有余！

果不其然，在杨成写完最后一个括号后，手中的小册子绽放出一道金光。

小册子犹如脱离了重力的束缚一般，慢慢浮空，然后一页接一页地自动翻页，就好比有人在翻阅一般。

请勿开启浏览器阅读模式，否则将导致章节内容缺失及无法阅读下一章。