您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 訊息 >> iOS 相關資訊

iOS 以程式輸出等腰巴斯卡三角形(楊輝三角)

編輯:iOS 相關資訊

楊輝三角是矩陣與組合數的經典入門題。本文先整理它的數學性質,再給出以 C 語言輸出等腰形式的完整實作。

一、先記住這幾條性質

端點恆為 1。

每一行的數字左右對稱,由 1 開始逐漸變大再變小。

第 n 行有 n 個數字,其總和為 2 的 (n-1) 次方。

第 n 行的第 m 個數與第 n-m+1 個數相等,也就是 C(n-1, m-1) = C(n-1, n-m),這是組合數的對稱性。

最實用的一條:每個數字等於上一行左右兩數之和。換句話說,第 n+1 行的第 i 個數,等於第 n 行的第 i-1 個數加上第 i 個數。有了這條遞推式,整個三角形就能逐層填出來,不必真的去算階乘。

二、實作

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);

    int i, j, k;
    int 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++) {
        for (k = 0; k < n - 1 - i; k++) {   // k 控制左側留白
            printf(" ");
        }
        for (j = 0; j <= i; j++) {
            printf("%6d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

三個迴圈各司其職:第一輪把每列的頭尾填成 1,第二輪用遞推式填中間,第三輪負責排版輸出。留白數量 n-1-i 就是等腰效果的來源——列數越大,左側空白越少。

三、執行結果

輸入 10,輸出如下:

四、可以再進步的地方

上面的寫法配置了 n×n 的二維陣列,空間用了 O(n²)。但其實每一列只依賴前一列,因此可以用一個一維陣列「由後往前」更新,把空間降到 O(n):

int row[n] = {0};
row[0] = 1;
for (i = 1; i < n; i++) {
    for (j = i; j > 0; j--) {   // 必須由後往前,避免覆蓋上一列的結果
        row[j] = row[j] + row[j-1];
    }
}

之所以要倒著更新,是因為 row[j] 需要用到「上一列」的 row[j] 與 row[j-1];若由前往後,row[j-1] 已經被改成本列的值,結果就錯了。這是動態規劃中「滾動陣列」的常見技巧,值得一併記住。

另外,printf 的 %6d 只是簡單對齊;若 n 較大導致數字位數超過 6,等腰的視覺效果就會被破壞,此時可依 n 推算最大位數後動態決定欄寬。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved