The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ……..
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
with seed values
Write a functionint fib(int n)that returns.
For example, ifn= 0, thenfib()should return 0. If n = 1, then it should return 1. For n > 1, it should return
Following are different methods to get the nth Fibonacci number.
http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
斐波那契数列大家都很熟悉了,递归和动态规划法这里就不讲了。
原来有一个更加优化的方法,时间效率为O(lgn)。
Method 4 ( Using power of the matrix {{1,1},{1,0}} )
This another O(n) which relies on the fact that if we n times multiply the matrix M = {{1,1},{1,0}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.
The matrix representation gives the following closed expression for the Fibonacci numbers:
通过这个矩阵相乘的方法,得到的时间复杂度依然是O(n),但是可以进一步使用二分法,把复杂度降低到O(lgn)。
Method 5 ( Optimized Method 4 )
The method 4 can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the prevous
method (Similar to the optimization done inthispost)
下面是Method4 和5的程序:
void mulMatrix(int F[2][2])
{
int a = F[0][0];
int b = F[1][0];
F[0][0] = a+b;
F[0][1] = a;
F[1][0] = a;
F[1][1] = b;
}
void powMatrix(int F[2][2], int n)
{
for (int i = 2; i < n; i++)
mulMatrix(F);
}
int fib(int n)
{
if (n == 0) return 0;
int F[2][2] = {{1,1},{1,0}};
powMatrix(F, n);
return F[0][0];
}
class OptiFib
{
public:
void mulOneMatrix(int F[2][2])
{
int a = F[0][0];
int b = F[1][0];
F[0][0] = a+b;
F[0][1] = a;
F[1][0] = a;
F[1][1] = b;
}
void pow2Matrix(int F1[2][2])
{
int a = F1[0][0];
int b = F1[0][1];
int c = F1[1][0];
int d = F1[1][1];
F1[0][0] = a*a+b*c;
F1[0][1] = a*b+b*d;
F1[1][0] = c*a+c*d;
F1[1][1] = c*b+d*d;
}
void powMatrix(int F[2][2], int n)
{
if (n < 2) return;
int mid = n>>1;
powMatrix(F, mid);
pow2Matrix(F);
if (n%2 == 1) mulOneMatrix(F);
}
int fib(int n)
{
if (n == 0) return 0;//注意:不要遗漏这个特例!
int F[2][2] = {{1,1},{1,0}};
powMatrix(F, n-1);
return F[0][0];
}
};
分享到:
相关推荐
2022最新版:GEEKS V1.0.10主题:在线学习市场WordPress主题.rar
geeks-for-geeks-solutions:有关Geeks-for-Geeks的问题的解决方案。解决方案可用于C ++
Geeks2TheRescue:使用MERN的Web App,旨在连接雄心勃勃的开发人员
geeks_algorithms 极客算法编码问题
带有React JS的WebApp样板 要求: 确保您使用的是节点版本10 ... 注意(新更改) :组件已转换为功能,以支持钩子的使用: 我们使用的是const函数,而不是类组件。 类的constructor和state已由useState()钩子
夏季极客提交 这个Web应用程序被配制成在Innnovaccer SDE实习分配的一部分,使用的NodeJS,MongoDB的,NodeMailer的电子邮件和Nexmo的手机信息,根据。 预习 报到表格 结帐电子邮件 使用的技术 ...
欢迎来到4Geeks学院 <\编码时间>内容关于。创始人。团队。奖项。校友关于4Geeks是一家大公司,感觉就像一家小公司;每个人都可以访问,我们喜欢与人接触,我们相信量身定制的教育,而不会离开您的工作,并且100%...
geeks for geeks上的资源,大家下载下,我攒点几分,呵呵。
:sparkles: gloomhaven-geeks :sparkles: 这是一个使用Git作为的网站。 它是在不到一分钟的时间内使用创建的。 您可以像这样,或探索一些变体。 如何不同: :artist_palette: 看 :pencil: 内容管理系统 :gear: 静态...
极客换极客 Geeks-For-Geeks 实习文章 使用 scapy 嗅探数据包 - 使用 Javascript 和 DOM 创建棋盘模式 - 如何将链接从一个 iframe 加载到另一个 iframe -
1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好做。 2 使用一个数组记录当前顶点在堆中的位置,相当于一个...
Geeks for Geeks的DSA练习: :
Geeks3D Furmark(OpenGL显卡基准测试工具)V1.17.1 中文官方版
Hardware Hacking Projects for Geeks 英文chm 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
geek极客们都用什么神器,这篇文章给了你答案。
Mac OS X For Unix Geeks 2003
Ubuntu for Non-Geeks (Fourth Edition)
Cooking.for.Geeks, hope all programer have good food
A HashMap for Geeks and normal programmers.
Mac.OS.X.for.Unix.Geeks 这本书非常棒,通过 unix 的视角审视 OSX 真的很不错 E文的哦,喜欢一分