萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

C 語言打印楊輝三角:動態內存與金字塔對齊完整實現

楊輝三角(Pascal's Triangle)是組合數學與編程基礎的經典題目。本程序採用動態內存分配逐行計算,實現金字塔式居中打印,展示了指針操作、內存管理、格式化輸出的綜合運用。

算法原理

  • 第 n 行有 n 個數,首尾為 1
  • 中間元素:C(n,k) = C(n-1,k-1) + C(n-1,k)
  • 僅需保存上一行數組,空間複雜度 O(n)

完整代碼


#include 
#include 

int main() {
    int line;
    printf("輸入要查看楊輝三角的行數(大於 2):");
    scanf("%d", &line);
    if (line < 2) {
        printf("行數小於 2,Goodbye!\n");
        return 1;
    }

    // 前兩行單獨打印(簡化邏輯)
    for (int i = 1; i <= line; i++) printf("   ");
    printf("%6d\n", 1);

    for (int i = 1; i <= line-1; i++) printf("   ");
    printf("%6d%6d\n", 1, 1);

    int *prev = malloc(2 * sizeof(int));
    prev[0] = 1; prev[1] = 1;

    for (int i = 3; i <= line; i++) {
        int *curr = malloc(i * sizeof(int));
        curr[0] = 1;
        curr[i-1] = 1;

        // 外部縮進:每行減少 3 空格
        for (int j = line; j >= i; j--) printf("   ");
        printf("%6d", 1);

        // 計算並打印中間元素
        for (int k = 2; k < i; k++) {
            curr[k-1] = prev[k-2] + prev[k-1];
            printf("%6d", curr[k-1]);
        }
        printf("%6d\n", 1);

        free(prev);
        prev = curr;
    }
    free(prev); // 釋放最後一行
    return 0;
}

關鍵技術點

  1. 雙指針滾動數組:prev 保存上一行,curr 計算當前行,計算完 free(prev); prev=curr; 實現 O(n) 空間。
  2. 金字塔對齊:外層循環 for(j=line; j>=i; j--) 打印遞減空格,配合 %6d 固定寬度,形成視覺居中效果。
  3. 內存管理:每行 malloc,用完 free,無洩漏。注意最後一行循環外需額外 free(prev)。
  4. 邊界處理:行數 < 2 直接退出;第 1、2 行硬編碼打印,避免通用邏輯特判。

輸出示例(line=6)

                     1
                  1     1
               1     2     1
            1     3     3     1
         1     4     6     4     1
      1     5    10    10     5     1

改進方向

  • 大數支持:行數 > 13 時 int 溢出,改用 long long 或大整數庫。
  • 自適應寬度:根據最大值位數動態計算 %*d 寬度,避免大數對齊崩塌。
  • 單數組原地更新:逆序更新 for(k=i-1; k>0; k--) a[k] += a[k-1],省去 malloc/free 開銷。
  • 文件輸出:支持重定向到文件,便於大行數查看。

單數組原地更新版(更高效)


int *a = calloc(line, sizeof(int));
a[0] = 1;
for (int i = 1; i <= line; i++) {
    // 打印縮進
    for (int s = line; s > i; s--) printf("   ");
    // 逆序更新並打印
    for (int k = i-1; k >= 0; k--) {
        if (k == i-1 || k == 0) a[k] = 1;
        else a[k] = a[k] + a[k-1];
        printf("%6d", a[k]);
    }
    printf("\n");
}
free(a);

總結

楊輝三角程序雖小,卻涵蓋動態內存、指針運算、循環嵌套、格式化輸出、邊界條件等 C 語言核心技能。滾動數組思想廣泛應用於動態規劃(如 01 背包、編輯距離)空間優化,值得深入體會。

copyright © 萬盛學電腦網 all rights reserved