C语言求解帕斯卡三角形指定行所有系数平方和的问题求助

方案1：按原思路实现组合数计算 #

你可以用递推方式计算组合数C(n,k)，避免直接计算阶乘导致的溢出和效率问题，递推公式为：

C(n, 0) = 1
C(n, k) = C(n, k-1) * (n - k + 1) / k
该公式每一步都是整数运算，不会出现小数误差，计算效率更高。

修改后的完整代码如下：

#include <stdio.h>

// 计算组合数C(n,k)
unsigned long comb(const int n, const int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    // 利用C(n,k)=C(n,n-k)的性质减少计算次数
    int k_min = (k < n - k) ? k : n - k;
    unsigned long res = 1;
    for (int i = 1; i <= k_min; i++) {
        res = res * (n - k_min + i) / i;
    }
    return res;
}

unsigned long sum_triangle(const int row);

int main(){
    printf("%lu\n", sum_triangle(7));
    // 输出结果为3432，对应C(14,7)
    return 0;
}

unsigned long sum_triangle(const int row){
    unsigned long sum = 0;
    // 原代码两层循环冗余，直接遍历目标行的所有位置即可
    for (int number = 0; number <= row; number++) {
        unsigned long c = comb(row, number);
        sum += c * c;
    }
    return sum;
}

原代码存在的问题：

• 两层循环完全冗余，不需要遍历前面的行，直接遍历目标行的每个位置即可
• temp定义为int类型会溢出，需要改成unsigned long类型

方案2：用数学恒等式优化（效率更高） #

根据范德蒙德恒等式，杨辉三角第n行所有系数的平方和等于组合数C(2n, n)，不需要逐个计算平方再累加，直接计算这个组合数就能得到结果，时间复杂度从O(n²)降到O(n)：

#include <stdio.h>

unsigned long comb(const int n, const int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    int k_min = (k < n - k) ? k : n - k;
    unsigned long res = 1;
    for (int i = 1; i <= k_min; i++) {
        res = res * (n - k_min + i) / i;
    }
    return res;
}

unsigned long sum_triangle(const int row) {
    return comb(2 * row, row);
}

int main(){
    printf("%lu\n", sum_triangle(7));
    return 0;
}

内容的提问来源于stack exchange，提问作者helperman200