我们经常看到很多斐波那契数列的问题。我个人非常讨厌它们,甚至可以说是非常非常讨厌。我认为如果我们能够使其无法再被用作面试题,那将会很有意义。让我们看看我们能够实现多接近 O(1) 的斐波那契数列。
以下是我从维基百科借鉴的代码,当然还有很大的提升空间。重要的是,这个解决方案对于任何特别大的斐波那契数都会出错,并且其中使用了相对简单的 power 函数,最坏情况下它的时间复杂度为 O(log(n)),如果你的库不好的话。我怀疑我们是否可以摆脱 power 函数,或者至少专门化它。有没有人愿意帮忙?除了使用查找表的有限*解决方案之外,是否存在真正的 O(1) 解决方案?
#include <iostream>
#include <math.h>
using namespace std; // would never normally do this.
int main() {
int target = 10;
cin >> target;
// should be close enough for anything that won't make us explode anyway.
float mangle = 2.23607610;
float manglemore = mangle;
++manglemore; manglemore = manglemore / 2;
manglemore = pow(manglemore, target);
manglemore = manglemore/mangle;
manglemore += .5;
cout << floor(manglemore);
}
*我知道,我知道,斐波那契数列在实际应用中几乎没有任何作用。
FLT_MAX
之间没有太多的斐波那契数。;-) - Paul R