Java培訓(xùn)：不使用數(shù)組實(shí)現(xiàn)打印“楊輝三角形”

　　一、楊輝三角形

　　1.1 楊輝三角形的概念

　　 楊輝三角，是二項(xiàng)式系數(shù)在三角形中的一種幾何排列。在歐洲，這個(gè)表叫做帕斯卡三角形。帕斯卡(1623----1662)是在1654年發(fā)現(xiàn)這一規(guī)律的，比楊輝要遲393年，比賈憲遲600年。楊輝三角是中國(guó)古代數(shù)學(xué)的杰出研究成果之一，它把二項(xiàng)式系數(shù)圖形化，把組合數(shù)內(nèi)在的一些代數(shù)性質(zhì)直觀地從圖形中體現(xiàn)出來(lái)，是一種離散型的數(shù)與形的結(jié)合 。

        我們先看一下楊輝三角形的打印結(jié)果：

　　1.2 楊輝三角形的性質(zhì)

　　 楊輝三角形有很多性質(zhì)：

　　 1). 每行端點(diǎn)與結(jié)尾的數(shù)為1。

　　 2). 每個(gè)數(shù)等于它上方兩數(shù)之和。

　　 3). 每行數(shù)字左右對(duì)稱，由1開(kāi)始逐漸變大。

　　 4). 第n行的數(shù)字有n項(xiàng)。

　　 5). 前n行共[(1+n)n]/2 個(gè)數(shù)。

　　 6).第n行的m個(gè)數(shù)可表示為 *C(n-1，m-1)*，即為從n-1個(gè)不同元素中取m-1個(gè)元素的組合數(shù)。

　　 7). 第n行的第m個(gè)數(shù)和第n-m+1個(gè)數(shù)相等 ，為組合數(shù)性質(zhì)之一。

　　 8). 每個(gè)數(shù)字等于上一行的左右兩個(gè)數(shù)字之和。可用此性質(zhì)寫(xiě)出整個(gè)楊輝三角。即第n+1行的第i個(gè)數(shù)等于第n行的第i-1個(gè)數(shù)和第i個(gè)數(shù)之和，這也是組合數(shù)的性質(zhì)之一。即 *C(n+1,i)=C(n,i)+C(n,i-1)*。

　　 9). (a+b)^n^的展開(kāi)式中的各項(xiàng)系數(shù)依次對(duì)應(yīng)楊輝三角的第(n+1)行中的每一項(xiàng)。

　　 10). 將第2n+1行第1個(gè)數(shù)，跟第2n+2行第3個(gè)數(shù)、第2n+3行第5個(gè)數(shù)……連成一線，這些數(shù)的和是第4n+1個(gè)斐波那契數(shù);將第2n行第2個(gè)數(shù)(n>1)，跟第2n-1行第4個(gè)數(shù)、第2n-2行第6個(gè)數(shù)……這些數(shù)之和是第4n-2個(gè)斐波那契數(shù)。

　　 11). 將第n行的數(shù)字分別乘以10^(m-1)^，其中m為該數(shù)所在的列，再將各項(xiàng)相加的和為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行數(shù)字的和為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). 斜線上數(shù)字的和等于其向左(從左上方到右下方的斜線)或向右拐彎(從右上方到左下方的斜線)，拐角上的數(shù)字。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). 將各行數(shù)字左對(duì)齊，其右上到左下對(duì)角線數(shù)字的和等于斐波那契數(shù)列的數(shù)字。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。

　　實(shí)現(xiàn)楊輝三角形的打印也有很多方式，今天我為大家介紹兩種方式：

　　- 使用數(shù)組的方式：這也是網(wǎng)上比較常見(jiàn)的方式。需要使用數(shù)組，所以效率較低。

　　- 不使用數(shù)組的方式：不需要使用數(shù)組，所以效率較高。

　　二、使用數(shù)組的方式

　　2.1 示意圖

　　 根據(jù)上面的性質(zhì)，如果我們要打印一個(gè)11行的楊輝三角形，我們可以將整個(gè)排列看做是一個(gè)n行，0-n列的矩陣，再結(jié)合上面的性質(zhì)8，我們將這個(gè)矩陣用一個(gè)二維數(shù)組來(lái)實(shí)現(xiàn)，如下圖：

　　2.2 代碼分步實(shí)現(xiàn)

　　2.2.1 根據(jù)示意圖，我們先定義一個(gè)二維數(shù)組：

int n = 11;//要幾行的數(shù)據(jù)
int[][] values = new int[n][];//定義n行，但暫時(shí)每行的列數(shù)先不定義

　　2.2.2 生成二維數(shù)組，根據(jù)楊輝三角形性質(zhì)，n行的數(shù)字個(gè)數(shù)為n：

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

　　2.2.3 填充二維數(shù)組：

for(int i = 0;i < values.length ; i++){
    values[i] = new int[i + 1];//行0有1列，行1有2列,....,行n有n+1列
    for(int j = 0 ; j < values[i].length ; j++){
        //根據(jù)性質(zhì)1，每行的首尾都為：1
        if(j == 0 || j == value[i].lenght - 1){
            values[i][j] = 1;
        }else if(i > 1){//根據(jù)性質(zhì)8，除首尾外的其它數(shù)字 = 上方數(shù) + 上方左側(cè)的數(shù)
            values[i][j] = values[i - 1][j] + values[i - 1][j - 1];
        }
    }
}

　　2.2.4 完整代碼：

public class YangHui {
    public static void main(String[] args) {
        yangHui(8);
    }
    private static void yangHui3(int n) {
        int[][] values = new int[n][];//定義n行，但暫時(shí)每行的列數(shù)先不定義
        for(int i = 0;i < values.length ; i++){
            values[i] = new int[i + 1];//行0有1列，行1有2列,....,行n有n+1列
            for(int j = 0 ; j < values[i].length ; j++){
                //根據(jù)性質(zhì)1，每行的首尾都為：1
                if(j == 0 || j == values[i].length - 1){
                    values[i][j] = 1;
                }else if(i > 1){//根據(jù)性質(zhì)8，除首尾外的其它數(shù)字 = 上方數(shù) + 上方左側(cè)的數(shù)
                    values[i][j] = values[i - 1][j] + values[i - 1][j - 1];
                }
            }
        }
        print(values);
    }
   
    private static void print(int[][] values) {
        for(int i = 0; i < values.length; i++) {
            for(int j = 0; j < values[i].length; j++) {
                System.out.printf("%-4d", values[i][j]);
            }
            System.out.println();
        }
    }
}

　　數(shù)組的方式比較好理解，但需要?jiǎng)?chuàng)建二維數(shù)組，效率較低，接下來(lái)我們看一下不需要數(shù)組的寫(xiě)法。

　　三、不使用數(shù)組的方式

　　3.1 算法說(shuō)明

　　 根據(jù)性質(zhì)6，第n行的m個(gè)數(shù)可表示為 *C(n-1，m-1)*，即為從n-1個(gè)不同元素中取m-1個(gè)元素的組合數(shù)。

　　 我們將其表示為C(i , j)的組合數(shù)，那么就有以下算法：

1、例如：i=3、j=2的位置上，值為C(3,2)，即(3*2)/(1*2)=3/1 * 2/2 = 3
2、例如：i=5、j=3的位置上，值為C(5,3)，即(5*4*3)/(1*2*3)= 5/1 * 4/2 * 3/3 = 5 * 2 * 1 = 10
3、例如：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 代碼實(shí)現(xiàn)

　　根據(jù)上述算法，我們就可以很方便的寫(xiě)出以下代碼：

private static void yangHui2(int n) {
    for(int i = 0; i < n; i++) {//行
        for(int j = 0; j <= i; j++) {//列
            //計(jì)算每列的值
            int value = 1;
            for(int k = 0; k < j; k++) {
                value = value * (i-k) / (k+1);
            }
            System.out.printf("%-4d", value);
        }
        System.out.println();
    }
}