一只青蛙一次可以跳上1级台阶，也可以跳上2级，求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路：

1.找规律 f(1)=1 f(2)=2 f(3)=3 f(4)=5 f(n)=f(n-1)+f(n-2)这是一个斐波那契数列

2.因为调到第n个台阶时，倒数第一个台阶可以一步跳过来，倒数第二个台阶也可以一步就跳过来

非递归版本：

1. JumpFloor(target) 
2.  
3.   if target==1 || target==2 return target 
4.  
5.   jumpSum=0 
6.  
7.   jump1=1 
8.  
9.   jump2=2 
10.  
11.   for i=3;i<target;i++ 
12.  
13.     jumpSum=jump1+jump2 
14.  
15.     jump1=jump2 
16.  
17.     jump2=jumpSum 
18.  
19.   return jumpSum 
20.  
21. function jumpFloor($number) 
22.  
23. { 
24.  
25.     if($number==1 || $number==2){ 
26.  
27.         return $number; 
28.  
29.     }   
30.  
31.     $jumpSum=0; 
32.  
33.     $jump1=1; 
34.  
35.     $jump2=2; 
36.  
37.     for($i=3;$i<=$number;$i++){ 
38.  
39.         $jumpSum=$jump1+$jump2; 
40.  
41.         $jump1=$jump2; 
42.  
43.         $jump2=$jumpSum; 
44.  
45.     }   
46.  
47.     return $jumpSum; 
48.  
49. } 
50.  
51. $res=jumpFloor(10); 
52.  
53. var_dump($res);

Tags: php青蛙跳台阶

分享到：