Go语言视频零基础入门到精通

黑乌乌

C语言趣味程序百例精解之java实现(94)兔子产子这个是学递归的入门程序：
                  
/**  
* 裴波那契数列（递归）  
* @param n  
* @return  
*/  
public int fib(int n) {   
    if (n < 1) {   
        return 0;   
    }   
    if (n == 1 || n == 2) {   
        return 1;   
    }   
    return fib(n - 1) + fib(n - 2);   
}  
当n=5时，fib(5)的计算过程如下:

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
由上面可以看出，这种算法对于相似的子问题进行了重复的计算，因此不是一种高效的算法。实际上， 该算法的运算时间是指数级增长的。 改进的方法是，我们可以通过一个数组保存已经算出的子问题的解来避免重复计算。（动态规划）

public class Fibonacci {   
        
    /*输出斐波那契数*/
    public static void printFibonacciNumber(long f1,long f2,int n){  
        for(int i = 1;i <= n;i++){   
            System.out.print(f1+" "+f2+" ");//先输出前两个数   
            if(i % 5 == 0)System.out.print("\n"); //换行   
            f1 = f1+f2;   //计算下两个数
            f2 = f1+f2;   
        }   
            
        /*后数除前数为黄金分割点*/   
        System.out.print("\n"+"-------------------------------------"+"\n");   
        System.out.println((double)f2/f1);//越到后边，后数除前数越接近黄金分割点   
            
            
    }   
        
    /*输出斐波那契数组*/   
    public static void printFibonacciArray(long f1,long f2,int n){   
        long f[] = new long[n];   
        f[0]=f1;   
        f[1]=f2;   
        for(int i =2;i < n;i++){  
            f=f[i-2]+f[i-1]; //数组的第三个数开始为前两个数的和   
        }   
        System.out.println("-------------------------------------"+"\n");   
        System.out.println(java.util.Arrays.toString(f)); //把数组转化成String输出   
            
    }   
   
    /**   
     * main method   
     * @param args   
     */   
    public static void main(String[] args) {   
        Fibonacci.printFibonacciNumber(0, 1, 10);  
        Fibonacci.printFibonacciArray(0, 1, 20);   
    }   
   
}   
                        
输出结果：

0 1 1 2 3 5 8 13 21 34
55 89 144 233 377 610 987 1597 2584 4181

-------------------------------------
1.6180339985218033
-------------------------------------

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]


小知识(摘录):

    斐波那契是意大利的数学家。他是一个商人的儿子。儿童时代跟随父亲到了阿尔及利亚，在那里学到了许多阿拉伯的算术和代数知识，从而对数学产生了浓厚的兴趣。
长大以后，因为商业贸易关系，他走遍了许多国家，到过埃及、叙利亚、希腊、西西里和法兰西。每到一处他都留心搜集数学知识。回国后，他把搜集到的算术和代数材料，进行研究、整理，编写成一本书，取名为《算盘之书》，于1202年正式出版。
这本书是欧洲人从亚洲学来的算术和代数知识的整理和总结，它推动了欧洲数学的发展。其中有一道“兔子数目”的问题是这样的：一个人到集市上买了一对小兔子，一个月后，这对小兔子长成一对大兔子。然后这对大兔子每过一个月就可以生一对小兔子，而每对小兔子也都是经过一个月可以长成大兔子，长成大兔后也是每经过一个月就可以生一对小兔子。那么，从此人在市场上买回那对小兔子算起，每个月后，他拥有多少对小兔子和多少对大兔子？
这是一个有趣的问题。当你将小兔子和大兔子的对数算出以后，你将发现这是一个很有规律的数列，而且这个数列与一些自然现象有关。人们为了纪念这位兔子问题的创始人，就把这个数列称为“斐波那契数列”。

又找到了这么一段话:

规律表:

月数 小兔 中兔 老兔 总数
1    1    0    0    1
2    0    1    0    1
3    1    0    1    2
4    1    1    1    3
5    2    1    2    5
6    3    2    3    8
7    5    3    5   13

    在计算每一行时，大兔数为上月的大兔数加上月的中兔数，中兔数为上月的小兔数，小兔数为本月的大兔数，算总数为本月的小兔数加本月的中兔数加本月的大兔数。在观察总数的过程中找出了规律：总数的第一、二月都是1，以后的每一月是前两月的和。数列为1，1，2，3，5，8，13，21，34，55，……

    当n=50时，后项与前项的比是1.61803398874989，而前项与后项的比是0.61803398874989，即b/a的值与a/b的值相差1，假设后项与前项的比是φ，则有（φ-1）/φ=1，解这个方程得：φ= (√5+1) /2，这就是黄金分割。
    当n充分大时，斐波纳契数列后前项的比值，与前后项的比值，相差1，它们的比值是黄金分割！黄金分割是一个十分有用的无理数。据此，把黄金分割可用一个有理数近似表示，如斐波纳契数列的第七项与斐波纳契数列的第六项的比13/8，斐波纳契数列的第九项与斐波纳契数列的第八项的比34/21等都可以近似地表示为黄金分割，当然项数越后越精确。