不使用数组实现打印“杨辉三角形”

　　一、杨辉三角形

　　1.1 杨辉三角形的概念

　　 杨辉三角，是二项式系数在三角形中的一种几何排列。在欧洲，这个表叫做帕斯卡三角形。帕斯卡(1623----1662)是在1654年发现这一规律的，比杨辉要迟393年，比贾宪迟600年。杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合 。

我们先看一下杨辉三角形的打印结果：

　　1.2 杨辉三角形的性质

　　 杨辉三角形有很多性质：

　　 1). 每行端点与结尾的数为1。

　　 2). 每个数等于它上方两数之和。

　　 3). 每行数字左右对称，由1开始逐渐变大。

　　 4). 第n行的数字有n项。

　　 5). 前n行共[(1+n)n]/2 个数。

　　 6).第n行的m个数可表示为 *C(n-1，m-1)*，即为从n-1个不同元素中取m-1个元素的组合数。

　　 7). 第n行的第m个数和第n-m+1个数相等 ，为组合数性质之一。

　　 8). 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。即 *C(n+1,i)=C(n,i)+C(n,i-1)*。

　　 9). (a+b)^n^的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。

　　 10). 将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第4n+1个斐波那契数;将第2n行第2个数(n>1)，跟第2n-1行第4个数、第2n-2行第6个数……这些数之和是第4n-2个斐波那契数。

　　 11). 将第n行的数字分别乘以10^(m-1)^，其中m为该数所在的列，再将各项相加的和为11^(n-1)^。 11^0^=1，

　　 11^1^=1 * 10^0^ + 1 * 10^1^=11，

　　 11^2^=1×10^0^+2x10^1^^+1x10^2^=121，

　　 11^3^=1x10^0^+3×10^1^+3x10^2^+1x10^3^=1331，

　　 11^4^=1x10^0^+4x10^1^10^2^+4x10^3+1x10^4=14641，

　　 11^5^=1x10^0^+5x10^1^+10x10^2^+10x10^3^+5x10^4^+1×10^5^=161051。

　　 12). 第n行数字的和为2^(n-1)^。1=2^(1-1)^，1+1=2^(2-1)^，1+2+1=2^(3-1)^，1+3+3+1=2^(4-1)^，1+4+6+4+1=2^(5-1)^，1+5+10+10+5+1=2^(6-1)^。

　　 13). 斜线上数字的和等于其向左(从左上方到右下方的斜线)或向右拐弯(从右上方到左下方的斜线)，拐角上的数字。1+1=2，1+1+1=3，1+1+1+1=4，1+2=3，1+2+3=6，1+2+3+4=10，1+3=4，1+3+6=10，1+4=5。

　　 14). 将各行数字左对齐，其右上到左下对角线数字的和等于斐波那契数列的数字。1，1，1+1=2，2+1=3，1+3+1=5，3+4+1=8，1+6+5+1=13，4+10+6+1=21，1+10+15+7+1=34，5+20+21+8+1=55。

　　实现杨辉三角形的打印也有很多方式，今天我为大家介绍两种方式：

　　- 使用数组的方式：这也是网上比较常见的方式。需要使用数组，所以效率较低。

　　- 不使用数组的方式：不需要使用数组，所以效率较高。

　　二、使用数组的方式

　　2.1 示意图

　　 根据上面的性质，如果我们要打印一个11行的杨辉三角形，我们可以将整个排列看做是一个n行，0-n列的矩阵，再结合上面的性质8，我们将这个矩阵用一个二维数组来实现，如下图：

　　2.2 代码分步实现

　　2.2.1 根据示意图，我们先定义一个二维数组：

intn=11;//要几行的数据int[][]values=newint[n][];//定义n行，但暂时每行的列数先不定义

　　2.2.2 生成二维数组，根据杨辉三角形性质，n行的数字个数为n：

for(inti=0;i<values.length;i++){values[i]=newint[i+1];//行0有1列，行1有2列,....,行n有n+1列}

　　2.2.3 填充二维数组：

for(inti=0;i<values.length;i++){values[i]=newint[i+1];//行0有1列，行1有2列,....,行n有n+1列for(intj=0;j<values[i].length;j++){//根据性质1，每行的首尾都为：1if(j==0||j==value[i].lenght-1){values[i][j]=1;}elseif(i>1){//根据性质8，除首尾外的其它数字=上方数+上方左侧的数values[i][j]=values[i-1][j]+values[i-1][j-1];}}}

　　2.2.4 完整代码：

publicclassYangHui{publicstaticvoidmain(String[]args){yangHui(8);}privatestaticvoidyangHui3(intn){int[][]values=newint[n][];//定义n行，但暂时每行的列数先不定义for(inti=0;i<values.length;i++){values[i]=newint[i+1];//行0有1列，行1有2列,....,行n有n+1列for(intj=0;j<values[i].length;j++){//根据性质1，每行的首尾都为：1if(j==0||j==values[i].length-1){values[i][j]=1;}elseif(i>1){//根据性质8，除首尾外的其它数字=上方数+上方左侧的数values[i][j]=values[i-1][j]+values[i-1][j-1];}}}print(values);}privatestaticvoidprint(int[][]values){for(inti=0;i<values.length;i++){for(intj=0;j<values[i].length;j++){System.out.printf("%-4d",values[i][j]);}System.out.println();}}}

　　数组的方式比较好理解，但需要创建二维数组，效率较低，接下来我们看一下不需要数组的写法。

　　三、不使用数组的方式

　　3.1 算法说明

　　 根据性质6，第n行的m个数可表示为 *C(n-1，m-1)*，即为从n-1个不同元素中取m-1个元素的组合数。

　　 我们将其表示为C(i , j)的组合数，那么就有以下算法：

1、例如：i=3、j=2的位置上，值为C(3,2)，即(3*2)/(1*2)=3/1*2/2=32、例如：i=5、j=3的位置上，值为C(5,3)，即(5*4*3)/(1*2*3)=5/1*4/2*3/3=5*2*1=103、例如：i=7、j=4的位置上，值为C(7,4)，即(7*6*5*4)/(1*2*3*4)=7/1*6/2*5/3*4/4=35

　　3.2 代码实现

　　根据上述算法，我们就可以很方便的写出以下代码：

privatestaticvoidyangHui2(intn){for(inti=0;i<n;i++){//行for(intj=0;j<=i;j++){//列//计算每列的值intvalue=1;for(intk=0;k<j;k++){value=value*(i-k)/(k+1);}System.out.printf("%-4d",value);}System.out.println();}}