楊輝三角(在印度與西方又稱帕斯卡三角)有幾條非常好用的規律,記住它們,代碼幾乎是順著寫出來的:
其中「每項等於上一行相鄰兩項之和」這條最為關鍵:第 n+1 行的第 i 個數,等於第 n 行第 i-1 個數與第 i 個數之和。有了它,整個三角形就能逐行推導出來。
int n;
scanf("%d", &n);
int i, j, k, a[n][n]; // i 控制行,j 控制列
// 先將每行的首尾置為 1
for (i = 0; i < n; i++) {
a[i][0] = 1;
a[i][i] = 1;
}
// 再依「上一行相鄰兩數之和」填補中間部分
for (i = 2; i < n; i++) {
for (j = 1; j <= i - 1; j++) {
a[i][j] = a[i-1][j] + a[i-1][j-1];
}
}
// 輸出等腰(居中)的楊輝三角
for (i = 0; i < n; i++) {
// k 負責輸出前導空格,讓三角形居中
for (k = 0; k < n - 1 - i; k++) {
printf(" ");
}
for (j = 0; j <= i; j++) {
printf("%6d ", a[i][j]);
}
printf("\n");
}
輸入 10,輸出如下:
上面用的是二維數組,空間複雜度為 O(n²)。如果只關心當前行,其實用一維數組反向前推即可把空間降到 O(n)。另外,居中效果依賴空格寬度與數字佔位的匹配,若行數較大導致位數增加,需要相應調整 printf 的格式串,否則三角形兩側會錯位。若 n 超過 30 左右,數值會迅速超出 int 範圍,此時應改用 long long 或高精度處理。