黑马程序员技术交流社区

标题: 斐波那契数列的递归问题的三种算法 [打印本页]

---

作者: 王盟    时间: 2015-9-1 21:14
标题: 斐波那契数列的递归问题的三种算法
斐波那契数列：1,1,2,3,5,8,13,21
第一种算法：递归算法
        public static void main(String[] args) {
                System.out.println(feiBo(20));
        }
        public static int feiBo(int n) {
                if (n == 1 || n == 2) {
                        return 1;
                } else {
                        return feiBo(n - 1) + feiBo(n - 2);
                }
        }
第二种算法（我戏称为螃蟹走路法）：
        public static void main(String[] args) {
                // 螃蟹走路算法
                int a = 1;
                int b = 1;
                int c = 0;
                for (int x = 3; x <= 20; x++) {// 循环从3开始，以所求的数列索引为循环结尾。
                        c = a + b;
                        a = b;
                        b = c;
                }
                System.out.println(c);// c是最终的结果
        }
第三种算法（我戏称为数组地毯式推进法）：
        public static void main(String[] args) {
                // 数组地毯式推进法
                int[] arr = new int[20];
                arr[0] = 1;
                arr[1] = 1;
                for (int x = 2; x <= arr.length - 1; x++) {
                        arr[x] = arr[x - 1] + arr[x - 2];
                }
                System.out.println(arr[19]);
        }

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2