斐波那契数列也被称之为黄金分割数列，费波那契数列由0和1开始，之后的费波那契系数就由之前的两数相加，
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
算法实现起来也比较简单:
func fibonacci(n:NSInteger)->NSInteger{
if n<=0 {
return 0
}
if n==1 || n==2 {
return 1
}
return fibonacci(n-1)+fibonacci(n-2)
}
for index in 0...13 {
print("FlyELephant-第\(index)项的值:\(fibonacci(index))")
}
上面的递归，如果设置为50就会感觉运行特别慢，所以斐波那契数列通过递归实现并不是特别好，还好可以循环来解决:
//0、1、1、2、3、5、8、13、21、34
func fibonacci(n:Int) -> Int {
if n <= 0 {
return 0
}
if n == 1 {
return 1
}
var firstNum:Int = 0
var secondNum:Int = 1
var result:Int = 0
for _ in 2...n {
result = secondNum + firstNum
firstNum = secondNum
secondNum = result
}
return result
}
for index in 0...10 {
print("第\(index)项结果:\(fbonacciLoop(index))")
}
青蛙与台阶
一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。青蛙跳上一个n级的台阶总共有多少种跳法，这是简单的斐波那契数列:
func jumpFloor(n:NSInteger)->NSInteger {
if n<=0 {
return 0
}
if n==1 {
return 1
}
if n==2 {
return 2
}
return jumpFloor(n-1)+jumpFloor(n-2)
}
for index in 1...10 {
print("\(index)级台阶的跳法:\(jumpFloor(index))")
}
上面的题目还有一个变通问题，一只青蛙一次可以跳上1级台阶，也可以跳上2 级……也可以跳上n 级，青蛙跳上一个n级的台阶总共有多少种跳法？
简单的分析一下假设F(0)=1，那么
F(1)=1
F(2)=F(1)+F(0)
F(3)=F(2)+F(1)+F(0)
F(n-1)=F(n-2)+...+F(0)
F(n)=F(n-1)+F(n-2)+..F(0)
F(n)=2*F(n-1)
代码实现:
func jumpLoopFloor(n:NSInteger)->NSInteger {
if n<=0 {
return 0
}
if n==1 {
return 1
}
return 2*jumpLoopFloor(n-1)
}
for index in 1...10 {
print("\(index)级台阶跳法:\(jumpLoopFloor(index))")
}
