之前有學(xué)弟問(wèn)過(guò)我一道java的面試題，題目不算難。用java實(shí)現(xiàn)楊輝三角。我花了點(diǎn)時(shí)間整理了一下，發(fā)現(xiàn)挺有意思的，于是想寫(xiě)下來(lái)分享一下。在寫(xiě)代碼之前，我們先理清下面兩個(gè)問(wèn)題。
什么是楊輝三角
楊輝三角，是二項(xiàng)式系數(shù)在三角形中的一種幾何排列。在我國(guó)南宋數(shù)學(xué)家楊輝1261年所著的《詳解九章算法》有提到過(guò)。在歐洲叫做帕斯卡三角形，如圖。
楊輝三角的規(guī)律即原理
1.每個(gè)數(shù)等于它上方兩數(shù)之和。
2.每行數(shù)字左右對(duì)稱，由1開(kāi)始逐漸變大。
3.第n行的數(shù)字有n項(xiàng)。
4.第n行數(shù)字和為2n-1。
5.第n行的m個(gè)數(shù)可表示為 C(n-1，m-1)，即為從n-1個(gè)不同元素中取m-1個(gè)元素的組合數(shù)。
6.第n行的第m個(gè)數(shù)和第n-m+1個(gè)數(shù)相等 ，為組合數(shù)性質(zhì)之一。
7.每個(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)。
8.(a+b)n的展開(kāi)式中的各項(xiàng)系數(shù)依次對(duì)應(yīng)楊輝三角的第(n+1)行中的每一項(xiàng)。
9.將第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ù)。
10.將各行數(shù)字相排列，可得11的n-1（n為行數(shù)）次方：1=11^0; 11=11^1; 121=11^2……當(dāng)n>5時(shí)會(huì)不符合這一條性質(zhì)，此時(shí)應(yīng)把第n行的最右面的數(shù)字"1"放在個(gè)位，然后把左面的一個(gè)數(shù)字的個(gè)位對(duì)齊到十位... ...，以此類推，把空位用“0”補(bǔ)齊，然后把所有的數(shù)加起來(lái)，得到的數(shù)正好是11的n-1次方。以n=11為例，第十一行的數(shù)為：1,10,45,120,210,252,210,120,45,10,1，結(jié)果為 25937424601=1110。
清楚了這兩點(diǎn)之后，我們的思路就十分的清晰了。實(shí)現(xiàn)的方法有很多種，這里我打算用二維數(shù)組加雙重for循環(huán)來(lái)實(shí)現(xiàn)。
demo代碼：
重慶分公司
重慶分公司
public class Yanghui {
public static void main(String[] args) {
// 創(chuàng)建二維數(shù)組
int t[][]=new int[10][];
// 遍歷二維數(shù)組的第一層
for (int i = 0; i < t.length; i++) {
// 初始化第二層數(shù)組的大小
t[i]=new int[i+1];
// 遍歷第二層數(shù)組
for(int j=0;j<=i;j++){
// 將兩側(cè)的數(shù)組元素賦值為1
if(i==0||j==0||j==i){
t[i][j]=1;
}else{
// 其他數(shù)值通過(guò)公式計(jì)算
t[i][j]=t[i-1][j]+t[i-1][j-1];
}
// 輸出數(shù)組元素
System.out.print(t[i][j]+"\t");
}
//換行
System.out.println();
}
}
}
