题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。
求总共有多少总跳法,并分析算法的时间复杂度。
首先对题目进行分析:
台阶一共有n级
因此当n = 1时——只有一种跳法
当n = 2时——有1、1 或者 2 两种跳法
当n = 3时——有 1、1、1 或者2、1或者1、2三种跳法
。。。。。。。。。。。。。。。。。。。。。。。。。
因此
当n = k时——
有 f(k-1)+f(k-2)种跳法
分析到这里,程序用哪种方式设计便一目了然——递归
//*************************************************//
func jump(var n:Int)->Int{
//若只有一个台阶,返回1(表示一种跳法)
if(n == 1){
return 1
}
//若有两个台阶,返回2(表示两种跳法)
if(n == 2){
return 2
}
else{
var temp = jump(n - 1) + jump(n - 2) //递归
return temp
}
}
//*************************************************//