黑马程序员技术交流社区

标题: 关于递归的算法? [打印本页]
作者: 122125241    时间: 2015-7-2 10:43
标题: 关于递归的算法?
  1. <div class="blockcode"><blockquote>        public static int fib(int n) {
  2.                 if (n == 1 || n == 2) {
  3.                         return 1;
  4.                 } else {
  5.                         return fib(n - 1) + fib(n - 2);
  6.                 }
  7.         }
复制代码

为什么上面这个算法能得到结果?我今天看到这  觉得这个循环调用也没有调用运算,到底是怎么个结果得到的,你要是拆开的话下面我是可以看明白的,但是上面这段就几句话  想不通.............
package cn.itcast_02;

/*
* 有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第二十个月的兔子对数为多少？
* 分析：我们要想办法找规律
*                         兔子对数
* 第一个月：         1
* 第二个月：        1
* 第三个月：        2
* 第四个月：        3       
* 第五个月：        5
* 第六个月：        8
* ...
*
* 由此可见兔子对象的数据是：
*                 1,1,2,3,5,8...
* 规则：
*                 A:从第三项开始，每一项是前两项之和
*                 B:而且说明前两项是已知的
*
* 如何实现这个程序呢?
*                 A:数组实现
*                 B:变量的变化实现
*                 C:递归实现
*
* 假如相邻的两个月的兔子对数是a,b
* 第一个相邻的数据：a=1,b=1
* 第二个相邻的数据：a=1,b=2
* 第三个相邻的数据：a=2,b=3
* 第四个相邻的数据：a=3,b=5
* 看到了：下一次的a是以前的b，下一次是以前的a+b       
*/
public class DiGuiDemo2 {
        public static void main(String[] args) {
                // 定义一个数组
                int[] arr = new int[20];
                arr[0] = 1;
                arr[1] = 1;
                // arr[2] = arr[0] + arr[1];
                // arr[3] = arr[1] + arr[2];
                // ...
                for (int x = 2; x < arr.length; x++) {
                        arr[x] = arr[x - 2] + arr[x - 1];
                }
                System.out.println(arr[19]);// 6765
                System.out.println("----------------");

                int a = 1;
                int b = 1;
                for (int x = 0; x < 18; x++) {
                        // 临时变量存储上一次的a
                        int temp = a;
                        a = b;
                        b = temp + b;
                }
                System.out.println(b);
                System.out.println("----------------");

                System.out.println(fib(20));
        }

       


作者: 燃烧的灵魂    时间: 2015-7-2 22:20
正解……:lol
作者: 冷雨敲窗被未温    时间: 2015-7-3 00:30
这个真心不错 ，不用递归都搞出两种算法，看来你学得比较深呀！我当初就没想出来555555



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