假设你需要走n 阶楼梯才能到达楼顶,走楼梯的方式有两种,一次走1个台阶或者一次走2个台阶,问有多少种不同的方法可以走完这n阶楼梯？...先穷举几个n值分析下:
n=1,共1种;
{1}
n=2,共2种;
{1,1},{2}
n=3,共3种
{1,2},
{1,1,1},{2,1}
n=4,共5种
{1,1,2},{2,2},
{1,2,1...}
可以看到,除了n=1和n=2两种情况,是固定的走法外;
走n阶台阶时,可以在n-2个台阶的基础上一次走2个台阶,也可以在n-1个台阶的基础上走1个台阶;也就是f(n)=f(n-1)+f(n-2),这个公式就是著名的斐波那契数列...,却不是算法上最优的.明显在计算n时,会计算两次n-2,时间复杂度是O(n^n),效率相当低的算法了....简单分析下:
容易得出如下结论:
f(1) =1
f(2)=1
f(n)=f(n-1)+f(n-2)
在看一下称为黄金分割数列的原因,随着n趋向于无穷大,f(n)/f(n+1)的值越趋近于0.618.
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
