3.1 “Fibonacci数列和杨辉三角形求值”实例
【实例说明】
斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1，1，2，3，5，8，13，21，…在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn−1+Fn−2（n≥2，n∈N*）。在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从20世纪60年代起出版了《斐波纳契数列》季刊，专门刊载这方面的研究成果。
杨辉三角形，又称贾宪三角形、帕斯卡三角形，是二项式系数在三角形中的一种几何排列。二项式定理与杨辉三角形是天然的一对，它把数形结合带进了计算数学。求二项式展开式系数的问题，实际上是一种组合数的计算问题。用系数通项公式来计算，称为“式算”；用杨辉三角形来计算，称作“图算”。其实，中国古代数学家在数学的许多重要领域中处于遥遥领先的地位。中国古代数学史曾经有自己光辉灿烂的篇章，而杨辉三角的发现就是十分精彩的一页。
本实例分别通过一维数组实现Fibonacci数列前32项的求值并将序列打印输出，通过二维数组实现杨辉三角形前10行的求值并打印输出，程序运行界面如图3.1所示。
图3.1 Fibonacci数列和杨辉三角形求值
【实例目的】
（1）熟悉并掌握定义和初始化一维数组、二维数组的方法以及引用数组元素的方法。
（2）熟练掌握利用数组分别求解Fibonacci数列前n项的具体方法以及求解杨辉三角形前n行数据的具体方法。
【技术要点】
（1）利用一维数组求Fibonacci数列的前n项
该数列的初值及递推公式表示如下：
（2）利用二维数组求解杨辉三角形前n行的数据
杨辉三角形可以看作n×n方阵的下三角，各行的数值分布有如下规律：
①数组的第0列和对角线元素为1。
②数组的其余各元素是上一行同列和上一行前一列的两个元素之和。
例如，案例中存放杨辉三角形数据的二维数组赋值方法如下：
【相关知识及注意事项】
3.1.1 一维数组
数组是相同类型的数据按顺序组成的一种复合数据类型。通过数组名加数组下标来使用数组中的数据。下标从0开始。Java中的数组实际上属于系统定义的类Array，其中定义了一些数据成员和方法。
一维数组是最简单的数组，在Java中，数组是作为数组类的一个实例来处理的，故可以用new运算符来建立一个数组。由于数组中每一个元素都作为一个单独的对象来考虑，因而必须逐一建立，所以定义的时候，必须显式或隐含地指明数组中对象的数目。
1.一维数组的声明和创建
（1）一维数组的声明
数组变量在使用之前要事先声明，其数组元素的类型可分为三类，第一类是Java的基本数据类型；第二类是Java类和接口类型（引用类型）；第三类是数组类型。声明一维数组有以下两种格式：
数组元素类型 数组名字[]；
或
数组元素类型[] 数组名字；
以上两种定义方式完全等价。
例如，案例中一维数组Fibonacci的声明如下：
int Fibonacci[]；
该声明也可以用以下方式进行：
int[] Fibonacci；
（2）一维数组的创建
声明数组仅仅是给出了数组名字和元素的数据类型，要想真正地使用数组，还必须为它分配内存空间，即创建数组。在为数组分配内存空间时必须指明数组的长度。
为一维数组分配内存空间的格式如下：
数组名=new 数组元素类型[数组元素的个数]；
例如：本案例中为Fibonacci数组分配空间，代码如下：
Fibonacci=new int[32]；
声明数组和创建数组可以一起完成，例如：
int Fibonacci[]=new int[32]；
2.一维数组的初始化
所谓初始化，就是在为数组的元素分配内存空间的同时，为每个数组元素赋初始值。Java数组必须先初始化，然后才能使用。初始化的方式有静态初始化和动态初始化两种：
（1）静态初始化
静态初始化是由程序员显式地指定每个数组元素的初值，由系统决定数组的大小。使用静态初始化方式进行数组的初始化时只指定数组元素的初始值，不指定数组长度。例如：
int Fibonacci[]=new int[]{1，1，2，3，5，8，13，21，34，55}；
也可以简化初始化方式：
int Fibonacci[]={1，1，2，3，5，8，13，21，34，55}；
上述语句相当于：
在这种情况下，数组的存储空间不需要再用new运算符来分配。
（2）动态初始化
数组的动态初始化是指程序员仅指定数组长度，由系统为每个数组元素分配一个默认的初始值，如float型的默认值是0.0。在声明数组的同时也可以给数组元素一个初始值，例如本案例中为Fibonacci数组进行初始化如下所示。
Fibonacci=new int[32]；
该案例中，系统为Fibonacci数组中的每个数组元素都分配一个默认的初始值0。
系统按如下规则指定初值：
● 整数类型（byte、short、int和long）数组元素的值为0。
● 浮点类型（float、double）数组元素的值是0.0。
● 字符类型char的数组元素值是ASCII码值为0的字符，即'\u0000'。
● 布尔类型boo1ean数组元素的值是false。
● 类、接口和数组等对象类型，其数组元素的值是null。
注意：不要静态初始化和动态初始化同时使用，也就是说不要在进行数组初始化时既指定数组的长度，也为每个数组元素分配初始值。
例如，下列初始化就是错误的：
int Fibonacci[]=new int[10]{1，1，2，3，5，8，13，21，34，55}； //错误
这行代码编译的时候是通过不了的，会提示编译错误。
3.一维数组元素的引用
在Java中，可以通过数组名加下标的方式使用数组元素。需要注意的是，下标从0开始。
引用一维数组元素的方式为：
数组名[下标]
例如本案例访问并输出Fibonacci数组元素的值，程序代码如下：
在Java中，每个一维数组都有一个属性length指明它的长度。例如上述案例代码中的Fibonacci.length是指明数组Fibonacci的长度。
3.1.2 多维数组
数组元素有多个下标的数组就是多维数组。多维数组是一种数组的数组，例如，当数组的元素又是一维数组时，该数组就是一个二维数组。在Java程序中，可以有三维数组，或四维数组等。由于多维数组中用得较多的还是二维数组，因而以下以二维数组为例说明多维数组声明、创建和引用的方法，其他多维数组可以依此类推。
1.二维数组的声明和创建
（1）二维数组的声明
声明二维数组的一般形式有以下3种：
数组元素类型 数组名[][]；
或
数组元素类型[][] 数组名；
或
数组元素类型[] 数组名 []；
类似的代码可以声明多维数组。
如案例中二维数组TriangleYH的声明如下：
int[][] TriangleYH；
以上声明也可以用以下方式进行：
int TriangleYH[][]；
或者以如下方式声明：
int[] TriangleYH[]；
（2）二维数组的创建
创建二维数组对象的方法以下几种：
①直接分配（平衡二维数组—矩阵）。
数组名=new 数组元素类型[行数][列数]；
或者，声明和创建一起完成：
数组元素类型 数组名[][]=new 数组元素类型[行数][列数]；
例如：本案例中为Fibonacci数组分配空间，代码如下：
TriangleYH=new int[10][10]；
声明和创建一起完成的话，程序代码如下：
int TriangleYH=new int[10][10]；
Java要求在编译时（即在源代码中）二维数组至少有一维的尺度已确定，其余维的尺度可以在以后分配。
②从最高维开始，分别对每一维分配不等长的空间（非平衡数组）。
以二维数组为例，先指定第一维，创建有指定子数组个数的二维数组然后，依次对每个子数组确定元素个数，并创建子数组。
例如，本案例中的二维数组TriangleYH，前3个子数组，第一个子数组有1个元素，第2个子数组有2个元素，第3个子数组有3个元素，创建这样一个二维数组，其声明和创建代码如下：
③直接赋值创建。声明二维数组，同时直接给出各子数组的元素。如果子数组的元素个数不同，则创建是一个非平衡的二维数组。例如，创建本案例中存储杨辉三角的前三行的数组代码如下：
2.二维数组的初始化
二维数组的初始化同一维数组初始化类似，同样可以使用"{}"大括号完成二维数组的初始化，不同的是每个一维数组的元素使用大括号定义新的一维数组，即一维数组的每个元素又是一个新的一维数组。
语法：
数组数据类型 数组名称[][]={{value1，value2…valuen}，{value1，value2，…，valuen}…}；
value：数组中各元素的值。
例如：初始化二维数组的实例代码如下所示。
int myarr[][]={{12，0}，{45，10}}；
初始化二维数组后，要明确数组的下标都是从0开始。如上面的代码中myarr[1][1]的值为10。
int型二维数组是以int myarr[][]来定义的，所以可以直接给myarr[x][y]赋值。例如：给myarr[1]的第2个元素赋值的语句如下所示。
myarr[1][1]=20；
3.二维数组元素的引用
对二维数组进行了初始化后，就可以在程序中引用数组的元素。二维数组元素的引用同一维数组的引用类似，也是通过数组名和下标值来进行的，引用二维数组元素的方式为：
数组名 [下标1] [下标2]
其中，下标1为数组元素的高维下标；下标2为数组的低维下标。二维数组中，下标同样是一个int类型数，也可以使用与int类型进行自动类型转换的类型，如short、byte、char类型（使用时转换成int类型），但下标不能是long类型的数。如果非得用long类型的数定义数组的下标，则须强制转换。
熟悉C/C++的读者知道，在C/C++使用二维数组的时候，要求每一维的长度必须一致，例如在C中有如下的定义：“int array[3][]；”其对应的二维表如表3.1所示。
表3.1 C/C++中二维数组存储格式
在Java中，却并不要求多维数组的每一维长度相同。例如，当在Java有如下的定义：
int array[3][]=new int[3][]；
其对应的二维表如表3.2所示。
表3.2 Java中二维数组存储格式
表3.2中并不要求n=m=k，实际应用中有可能n≠m≠k。
注意：Java的主要目标之一是安全性。许多在C/C++中困扰人们的问题，Java都不再重蹈覆辙。Java保证数组一定会被初始化，并对数组提供了下标越界检查机制，即所有下标必须大于等于0且小于等于数组长度减1。若越界使用元素，将产生异常信息：
ArrayIndexOut OfBoundsExccption
4.多维数组赋初值嵌套循环语句
循环可以进行多层嵌套，即循环语句中还包含循环语句。多维数组赋初值往往利用嵌套循环语句进行。例如：案例中可以用嵌套循环语句给存放杨辉三角形数据的二维数组赋值，方式如下所示。
3.1.3 关于args[]数组
main（）方法是Java应用程序的入口，也就是说，程序在运行时，第一个执行的方法就是main（）方法，这个方法不同于其他的方法，它不能由其他方法调用和传递参数，而只能由应用程序在启动运行时传递参数。所以在Java应用程序中main（）方法的方法头都是以如下形式出现：
public static void main（String[] args）
在DOS环境下执行Java应用程序的时候，使用“java className arg1 arg2 arg3…argn”的形式运行该Java应用程序，命令行的参数之间用空格隔开，命令行上的第1个参数保存在args[0]中，第2个参数保存在args[1]中，依此类推，参数的个数是多少，main（）方法中args[]数组的长度就是多少；没有参数传入时，args[]数组的长度就是0。
例如，使用Test.java文件的程序代码打印运行该Java应用程序时命令行上的参数：
该程序代编译、运行界面如图3.2所示。
图3.2 程序运行界面
运行该应用程序时的java命令如下：
java Test
程序运行结果为：
命令行没有传入参数！
如果输入的java命令如下：
java Test Hello Java！
程序运行结果为：
由此可知，args[0]中保存了第1个参数的值“Hello”，args[1]中保存了第2个参数“Java！”的值。
如果输入的Java命令如下：
java Test I am a student！
程序运行结果为：
该应用程序通过args传入的参数有：
程序运行结果显示，args数组中从下标位置为0的元素起，依次保存了命令行上的4个参数。
【代码及分析】
程序解释及常见问题如下：
（1）语句“int Fibonacci[]；”和“Fibonacci=new int[32]；”分别定义和创建了一个一维数组。此数组的数据类型为整型，数组大小为32。需注意的是：创建数组时，一定要规定数组的大小，否则将会出错，其出错信息为：“array dimension missing”，大体意思为：数组失去度，即数组没有大小。
（2）使用“Fibonacci[i]=Fibonacci[i-1]+Fibonacci[i-2]；”语句时，要特别注意i的取值是否合法。访问数组时，数组元素的下标从0开始，到数组元素的个数减1。如果超过此范围，在解释运行Java应用程序时系统会给出错误信息“ Exception in thread"main"java.lang.ArrayIndexOutOfBoundsException at ArrayDemo.main”，大体意思为：数组的下标越界，在ArrayDemo文件的main（）方法中。
【应用扩展】
（1）求解Fibonacci数列的前n项，除了应用一维数组解决外，还可以应用典型的迭代算法进行处理。例如，程序段的核心代码如下。
（2）求解杨辉三角形前n行的数据，除了可以应用二维数组解决外，还可以应用组合的概念进行处理。例如，杨辉三角形中，每个数值可以由组合
来计算。
其中，每一项的求值如下。
