使用 C 語言列印 Pascal triangle

這是我在 Logdown 的第一篇文章。

之前一直在思考,這個網站對我而言的定位,因為我平時便有在痞客邦經營(小柏之邦),不過我在這裡發現不少非常厲害的 coder、developer 會在 Logdown 分享相關技巧,於是我也想把自己正在學習當中的 C 語言程式設計,當作在這裡寫作的主軸。當然,我只是個菜鳥,若有任何錯誤或是敘述不清楚之處敬請指教,謝謝!

首先,在本篇文章中,我要示範如何使用 C 語言去列印 Pascal triangle(巴斯卡三角形)。
<!--more-->


引用自維基百科

簡單來說,巴斯卡三角形表面上的規則就是從第 3 行開始,某數字為前一行左右兩數的相加(參見上方的 gif 動畫圖檔)。用數學來計算的話,如果三角形有 n 層的話,每層有 k 項,則第 k 個數為

巴斯卡三角形同時也是二項式

的係數。舉例來說,如果是
,展開之後為
,其係數為 1 2 1,正好就是巴斯卡三角形的第 3 層。

在上述例子中,n 等於 2,但為什麼不是三角形的第 2 層、而是第 3 層呢?因為前面的組合公式是 C "k-1" 取 "n-1"。以此類推,第 1 行的 n 值為 0,而在Array(陣列)當中,第一個 element 的 index 正好為 0,因此,以下我將使用陣列來列印出「直角三角形」形狀的巴斯卡三角形。

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

首先,我們先宣告一個變數來作為二維陣列的 size,並且讓使用者自己決定巴斯卡三角形的層數。

int size;
printf("Please enter the size of the array, which equals to the number of the row:\n");
scanf("%d", &size);
int pascal [size][size];

接下來,我們先將二維陣列所有值指定為 0,然後給定前兩層(n=0, n=1)的值皆為 1。

int row, col;
for (int row = 0; row < size; row++)
    for (int col = 0; col < size; col++)
        pascal [row][col] = 0;

自第 3 層開始,將要使用迴圈來自動跑出之後的數字。

row = 2;
col = 0;
while (row < size)
{
    pascal [row][0] = 1; //每行的第 1 個數字皆為 1
     col = 1;
    while (col <= row)
    {
        pascal [row][col] =
        pascal [row - 1][col - 1] + pascal [row - 1][col];
        col++
      ...

關鍵在於這行:

pascal [row][col] =
pascal [row - 1][col - 1] + pascal [row - 1][col];

在正三角形下,外觀上規則為某數字自第 3 行起前一行左右兩數相加,把它變成直角三角形(靠左並排)之後,原本左邊的數就變成在左上方,也就是 col - 1,右邊的數字就變成在正上方,也就是 col(同一直排的數字)。


以上圖而言,紫色的 3 row = 2; col = 2
等於前一行紅色 2 pascal [2 - 1][2 - 1] = pascal [1][1]
加上前一行紅色 1 pascal [2 - 1][2] = pascal [1][2]

最後,再透過迴圈將巴斯卡三角形印出來。記得,第 n 行只有 n 個數字,所以第二個 for 迴圈的第二個參數需設定為 col <= row(如果該處設定為 col < size 的話,會把原先所設定的 0 給列印出來)。

for (row = 0; row < size; row++)
{
    for (col = 0; col <= row; col++)
        printf("%d\t", pascal [row][col]);
    printf("\n");
}

最後做出來的結果如下:

至於,為什麼剛開始要把陣列所有元素的值都先設定成 0?
因為當加總做到最後該行最後一個元素時,會去取左上方(值為 1 且有列印出來)跟正上方(值為 0 但沒有列印出來)的數值來加總,如我們所知,每一行數字的個數都會比前一行多 1 個,因此,若沒有先將所有元素指定為 0,每行的最後一個元素加總出來的值可能會有錯誤,因為:


陣列的原始值會是亂七八糟的數字!

以上是使用 C 語言列印 Pascal triangle 的其中一種方法,謝謝大家的閱讀!

Read on