快捷導(dǎo)航

用java實(shí)現(xiàn)楊輝三角的示例代碼

更新時(shí)間：2018年01月09日 13:57:52 作者：白晝黯淡了星光

本篇文章主要介紹了用java實(shí)現(xiàn)楊輝三角的示例代碼，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧

之前有學(xué)弟問過我一道java的面試題，題目不算難。用java實(shí)現(xiàn)楊輝三角。我花了點(diǎn)時(shí)間整理了一下，發(fā)現(xiàn)挺有意思的，于是想寫下來分享一下。在寫代碼之前，我們先理清下面兩個(gè)問題。

什么是楊輝三角

楊輝三角，是二項(xiàng)式系數(shù)在三角形中的一種幾何排列。在我國南宋數(shù)學(xué)家楊輝1261年所著的《詳解九章算法》有提到過。在歐洲叫做帕斯卡三角形，如圖。

楊輝三角

楊輝三角的規(guī)律即原理

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

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

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ì)寫出整個(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的展開式中的各項(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ù)加起來，得到的數(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)來實(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ù)值通過公式計(jì)算
          t[i][j]=t[i-1][j]+t[i-1][j-1];
        }
        // 輸出數(shù)組元素
        System.out.print(t[i][j]+"\t");     
      }
      //換行
      System.out.println();        
    }
  }
}

輸出在控制臺(tái)的結(jié)果如下：