一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)
解法一:(下台阶)
1 2 3 4 5 6 7 8 9 10 11 12 13
|
public class {
public int JumpFloor(int target) { if(target<=0) return 0; if(target==1) return 1; if(target==2) return 2; else return JumpFloor(target-2)+JumpFloor(target-1); } }
|
解法二:
规律:JumpFloor(target)= JumpFloor(target-2)+JumpFloor(target-1))
可得数列JumpFloor(1)、JumpFloor(2)、… JumpFloor(n)
为“斐波那契数列”(0除外)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
public class {
public int JumpFloor(int target) { if(target<=0) return 0; if(target==1) return 1; if(target==2) return 2; else { int j1=1,j2=2; int j3=0; while(target>=3){ j3 = j1 + j2; j1 = j2; j2 = j3; target--; } return j3; } } }
|
近期评论