1. /**
    2.  * 面试题10：斐波那契数列
    3.  * 题目一：求斐波那契数列的第n项
    4.  * 写一个函数，输入n，求斐波那契数列的第n项
    5.  * Fibonacci数列定义如下：
    6.  * f(n)={
    7.  *     0   n=0
    8.  *     1   n=1
    9.  *     f(n-1)+f(n-2)  n>1
    10.  * }
    11.  */
    12. public class No10 {
    13.     public static void main(String[] args) {
    14.         //构建测试用例
    15.         //（1）功能测试（正常输入）
    16.         //（2）边界值测试（0，1，2等）
    17.         //（3）性能测试（输入较大的数字）
    18.         int[] test = {0,1,2,3,6,9,15};
    19.         System.out.println("递归结果");
    20.         for(int i:test){
    21.             System.out.print(fibonacci1(i)+"  ");
    22.         }
    23.         System.out.println();
    24.         System.out.println("循环结果");
    25.         for(int j:test){
    26.             System.out.print(fibonacci2(j)+"  ");
    27.         }
    29.     }
    31.     //原始递归方法
    32.     public static int fibonacci1(int n){
    33.         if(n<=0){
    34.             return 0;
    35.         }
    36.         if(n==1){
    37.             return 1;
    38.         }
    39.         return fibonacci1(n-1)+fibonacci1(n-2);
    40.     }
    42.     //循环解决
    43.     public static long fibonacci2(int n){
    44.         if(n<=0){
    45.             return 0;
    46.         }
    47.         if(n==1){
    48.             return 1;
    49.         }
    51.         long pre0 = 0;
    52.         long pre1 = 1;
    53.         long result = 0;
    55.         for (int i = 2; i <= n; i++) {
    56.             result = pre0 + pre1;
    57.             pre0 = pre1;
    58.             pre1 = result;
    59.         }
    60.         return result;
    61.     }
    63.     //TODO:特殊数学公式解决
    66. }
    1. /**
    2.  * 面试题10：斐波那契数列
    3.  * 题目二：青蛙跳台阶问题
    4.  * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，求该青蛙跳上一个n级台阶总共有多少种跳法
    5.  * 拓展:青蛙也可以跳上n级台阶时,可证明公式为f(n)=2^(n-1)
    6.  * 拓展:小矩形重叠大矩形,分析可知仍为斐波那契数列
    7.  */
    8. public class No10etc {
    9.     public static void main(String[] args) {
    10.         //构建测试用例
    11.         //功能测试（输入5，9等正常值）
    12.         //边界值测试（输入0，1，2等）
    13.         //性能测试（输入较大的数字）
    14.         //异常值测试（输入负值等）
    15.         int[] test = {5,9,0,1,2,23,-5};
    16.         for(int element: test){
    17.             System.out.print(element+"级台阶"+goUp1(element)+"---");
    18.         }
    19.         System.out.println();
    20.         for (int element:test){
    21.             System.out.print(element+"级台阶"+goUp2(element)+"---");
    22.         }
    23.     }
    25.     //递归老办法解决
    26.     public static int goUp1(int n){
    27.         if(n<=0){
    28.             return 0;
    29.         }
    30.         if(n==1||n==2){
    31.             return n;
    32.         }
    33.         return goUp1(n-1)+goUp1(n-2);
    34.     }
    36.     //循环解决
    37.     public static long goUp2(int n){
    38.         if(n<=0){
    39.             return 0;
    40.         }
    41.         if(n==1||n==2){
    42.             return n;
    43.         }
    44.         long pre = 1;
    45.         long post = 2;
    46.         long result = 0;
    47.         for(int i=3;i<=n;i++){
    48.             result = pre + post;
    49.             pre = post;
    50.             post = result;
    51.         }
    52.         return result;
    53.     }
    54. }