背後的邏輯找出楊輝三角

我發現一些代碼來獲得帕斯卡三角，而無需使用數組或nCr的在Java中，如下：背後的邏輯找出楊輝三角

int maxRows = 6; 
int r, num; 
for (int i = 0; i <= maxRows; i++) 
{ 
    num = 1; 
    r = i + 1; 

    //pre-spacing 
    for (int j = maxRows - i; j > 0; j--) 
    { 
     System.out.print(" "); 
    } 

    for (int col = 0; col <= i; col++) 
    { 
     if (col > 0) 
     { 
      num = num * (r - col)/col; 
     } 
     System.out.print(num + " "); 
    } 
    System.out.println(); 
}

對我的生活中，我想不出如何的碼位產生所需數目（在序列中下一個）：

for (int col = 0; col <= i; col++) 
    { 
     if (col > 0) 
     { 
      num = num * (r - col)/col; 
     } 
     System.out.print(num + " "); 
    }

可能有人請解釋後面是如何產生的數量的邏輯？我有興趣瞭解如何獲得下一位數字的公式，即num=num*(r-col)/col如何工作！我也有興趣找出如何推導出這樣一個公式。

來源

2016-02-22 Somenath Sinha

聽起來像https://en.wikipedia.org/wiki/Binomial_theorem二項式係數 – Toumash

@Toumash這裏使用的二項式定理究竟如何？ –

可能的重複http://stackoverflow.com/questions/24294192/computing-the-binomial-coefficient-in-c/24294262#24294262 – Codor

首先是一點理論：帕斯卡三角形由二項式係數組成，其中第n行第k列的入口代表x ^（n-k）y^k的係數，可以是使用公式（n選擇k）計算，即n！ /（（n-k）！k！）。更多詳細信息可在wiki找到。

現在我們來看看代碼。

num = num * (r - col)/col

假設我們現在計算第n行第k列的num值。執行這條線之前，NUM有第n行和（k-1）列的值，即

num == (n choose (k-1)) == n!/((n - (k-1))!(k - 1)!)

和num的新值應爲：

(n choose k) 
== n!/((n - k)!k!) 
== (n!/((n - (k-1))!(k - 1)!)) * (n - (k-1))/k 
== num * (n - k + 1)/k

因此得到num的新值（來自表示前一個條目的num），我們需要將它乘以（row＃ - col＃+ 1），然後除以列＃。

這正是代碼所做的。在這一行中：

num = num * (r - col)/col

r實際上是==（行＃+ 1），col是col＃。

p.s.不知道如何在stackoverflow上格式化公式。一旦我弄清楚如何做，我需要清理我的答案。

來源

2016-02-22 17:11:10 aychen0110

背後的邏輯找出楊輝三角

回答

相關問題