c/c++蓝桥杯经典编程题100道（13）杨辉三角

杨辉三角

->返回c/c++蓝桥杯经典编程题100道-目录

目录

杨辉三角

一、题型解释

二、杨辉三角例题问题描述

例题 1：输入 5，输出前 5 行杨辉三角

例题 2：输入 6 和 2，输出第 6 行第 2 列的值

三、C语言实现杨辉三角

解法 1：试除法（难度：★）

代码实现：

代码逻辑解释：

解法 2：递归实现（难度：★★）

代码实现：

代码逻辑解释：

解法 3：优化试除法（难度：★★☆）

代码实现：

代码逻辑解释：

四、C++实现杨辉三角

解法 1：面向对象封装（难度：★★）

代码实现：

代码逻辑解释：

解法 2：STL与Lambda表达式（难度：★★☆）

代码实现：

代码逻辑解释：

五、总结对比表

六、特殊方法与内置函数补充

题型二题型三补充：

一、组合数查找：给定 n 和 k，输出杨辉三角的第 n 行第 k 列的组合数 C(n,k)

解法 1：基于阶乘公式（难度：★）

代码实现：

代码逻辑解释：

优点与缺点：

解法 2：递推计算（难度：★★）

代码实现：

代码逻辑解释：

优点与缺点：

解法 3：动态规划（难度：★★☆）

代码实现：

代码逻辑解释：

优点与缺点：

二、杨辉三角的性质应用：使用杨辉三角解决组合数、二项式定理等相关数学问题

应用 1：计算 (a + b)^n展开式的系数（难度：★★）

代码实现：

代码逻辑解释：

优点与缺点：

应用 2：利用杨辉三角计算组合数的其他应用（难度：★★☆）

代码实现：

代码逻辑解释：

三、总结对比表

四、特殊方法与内置函数补充

一、题型解释

杨辉三角（Pascal's Triangle）是一个由组合数构成的矩阵。常见的题型包括：

1. 基础题型： 输出杨辉三角的前 n行。

   • 例如：输入 n=5，输出前 5 行杨辉三角。

2. 组合数查找： 给定 n 和 k，输出杨辉三角的第 n 行第 k 列的组合数 C(n,k)。

   • 例如：输入 n=5, k=2，输出 C(5,2)。

3. 杨辉三角的性质应用： 使用杨辉三角解决组合数、二项式定理等相关数学问题。

   • 例如：计算 (a + b)^n展开式的系数。

二、杨辉三角例题问题描述

例题 1：输入 5，输出前 5 行杨辉三角

问题描述：
输入一个整数 n=5，输出杨辉三角的前 5 行。

预期输出：

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

例题 2：输入 6 和 2，输出第 6 行第 2 列的值

问题描述：
输入 n=6, k=2，求杨辉三角第 6 行第 2 列的元素，即组合数 C(6,2)。

预期输出：

C(6, 2) = 15

三、C语言实现杨辉三角

解法 1：试除法（难度：★）

通俗解释：
通过简单的递推关系，逐行计算并输出杨辉三角。每行的元素由上一行的元素计算而来。

代码实现：

#include <stdio.h>

void generatePascalTriangle(int n) {
    int triangle[n][n];  // 创建二维数组存储杨辉三角
    
    for (int i = 0; i < n; i++) {
        triangle[i][0] = 1;  // 每行第一个元素是1
        triangle[i][i] = 1;  // 每行最后一个元素是1
        for (int j = 1; j < i; j++) {
            // 根据上一行的元素计算当前元素
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }

    // 输出杨辉三角
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            printf("%d ", triangle[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int n = 5;
    generatePascalTriangle(n);  // 输出前5行杨辉三角
    return 0;
}

代码逻辑解释：

• 二维数组： 用二维数组 triangle[n][n] 存储杨辉三角的每个元素。
• 递推关系： 每行的第一个和最后一个元素都是1，其他元素由上一行的两个相邻元素相加。
• 输出： 双层 for 循环遍历并输出每一行的元素。

解法 2：递归实现（难度：★★）

通俗解释：
递归的方式可以通过分解出最小的子问题，逐步推导出杨辉三角的每个元素。

代码实现：

#include <stdio.h>

int combination(int n, int k) {
    if (k == 0 || k == n) return 1;  // 基本情况：C(n, 0) = C(n, n) = 1
    return combination(n - 1, k - 1) + combination(n - 1, k);  // 递归公式
}

void generatePascalTriangle(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            printf("%d ", combination(i, j));  // 输出每个组合数
        }
        printf("\n");
    }
}

int main() {
    int n = 5;
    generatePascalTriangle(n);  // 输出前5行杨辉三角
    return 0;
}

代码逻辑解释：

• 组合数计算： 使用递归函数 combination(n, k) 根据组合数公式计算每个元素。
• 递归公式： C(n,k)=C(n−1,k−1)+C(n−1,k)。
• 输出： 每行通过调用 combination(i, j) 输出对应的组合数。

解法 3：优化试除法（难度：★★☆）

通俗解释：
使用一个优化的方案，直接计算每行的组合数，减少不必要的计算。

代码实现：

#include <stdio.h>

void optimizedPascalTriangle(int n) {
    for (int i = 0; i < n; i++) {
        int val = 1;  // 每行的第一个元素是1
        for (int j = 0; j <= i; j++) {
            if (j > 0) {
                // 使用上一行的组合数递推计算当前行的组合数
                val = val * (i - j + 1) / j;
            }
            printf("%d ", val);  // 输出当前组合数
        }
        printf("\n");
    }
}

int main() {
    int n = 5;
    optimizedPascalTriangle(n);  // 输出前5行杨辉三角
    return 0;
}

代码逻辑解释：

• 优化递推： 使用上一行的组合数递推，避免了每次递归的重复计算。
• 递推公式：C(n,k)=C(n,k−1)×(n−k+1)/k。
• 输出： 每行通过递推计算当前行的每个组合数并输出。

四、C++实现杨辉三角

解法 1：面向对象封装（难度：★★）

通俗解释：
通过面向对象的方式封装杨辉三角的生成过程，使得代码更加模块化和可复用。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

class PascalTriangle {
private:
    vector<vector<int>> triangle;  // 存储杨辉三角

public:
    void generate(int n) {
        triangle.resize(n);  // 调整三角形的行数
        for (int i = 0; i < n; i++) {
            triangle[i].resize(i + 1);  // 每行的列数等于行号 + 1
            triangle[i][0] = triangle[i][i] = 1;  // 每行的第一个和最后一个元素为1
            for (int j = 1; j < i; j++) {
                // 递推公式
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
        }
    }

    void print() {
        for (const auto& row : triangle) {
            for (int num : row) {
                cout << num << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    PascalTriangle pt;
    pt.generate(5);  // 输出前5行杨辉三角
    pt.print();
    return 0;
}

代码逻辑解释：

• 类封装： PascalTriangle 类用于生成和输出杨辉三角。
• 生成三角形： generate() 函数通过递推关系生成每一行的元素。
• 输出： print() 函数遍历二维数组并输出每行。

解法 2：STL与Lambda表达式（难度：★★☆）

通俗解释：
使用 C++ 中的 Lambda 表达式简化代码逻辑，使得代码更加灵活。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

void generatePascalTriangle(int n) {
    vector<vector<int>> triangle(n);  // 创建二维 vector 存储杨辉三角
    auto generateRow = [&](int row) {
        triangle[row].resize(row + 1);
        triangle[row][0] = triangle[row][row] = 1;
        for (int i = 1; i < row; i++) {
            triangle[row][i] = triangle[row - 1][i - 1] + triangle[row - 1][i];
        }
    };

    for (int i = 0; i < n; i++) {
        generateRow(i);  // 生成每一行
    }

    // 输出杨辉三角
    for (const auto& row : triangle) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
}

int main() {
    generatePascalTriangle(5);  // 输出前5行杨辉三角
    return 0;
}

代码逻辑解释：

• Lambda表达式： 使用 Lambda 表达式简化每一行的生成过程。
• 生成三角形： generateRow() 函数使用 Lambda 表达式生成当前行。
• 输出： 遍历二维 vector 并输出每一行的元素。

五、总结对比表

六、特殊方法与内置函数补充

1. C++的 vector 容器
   作用：动态数组，用于存储杨辉三角的每行。支持自动扩展大小。

2. Lambda表达式
   作用：定义匿名函数，可以简化代码逻辑，尤其是需要多次使用的小逻辑。

3. 动态规划优化
   扩展思路：可以使用动态规划缓存中间结果，避免重复计算。

题型二题型三补充：

一、组合数查找：给定 n 和 k，输出杨辉三角的第 n 行第 k 列的组合数 C(n,k)

组合数 C(n,k) 也叫做“从 n 个元素中选出 k 个元素的组合数”，其数学表达式为：

C(n,k)=n!​/k!(n−k)!

解法 1：基于阶乘公式（难度：★）

通俗解释：
通过直接计算阶乘公式来求解组合数。虽然实现简单，但对于较大的 nnn 和 kkk，计算阶乘可能会导致溢出。

代码实现：

#include <stdio.h>

long long factorial(int n) {
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

long long combination(int n, int k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

int main() {
    int n = 5, k = 2;
    printf("C(%d, %d) = %lld\n", n, k, combination(n, k));
    return 0;
}

代码逻辑解释：

• 阶乘函数：
  factorial 函数计算给定整数 n的阶乘。

• 组合数函数：
  combination 函数通过组合数公式C(n,k)=n!​/k!(n−k)!计算结果。

优点与缺点：

• 优点：实现简单直观。
• 缺点：阶乘计算在 n 较大时会导致数值溢出，且计算效率低。

解法 2：递推计算（难度：★★）

通俗解释：
利用组合数的递推关系，逐步计算 C(n,k)。利用杨辉三角的递推性质：

C(n,k)=C(n−1,k−1)+C(n−1,k)

代码实现：

#include <stdio.h>

long long combination(int n, int k) {
    if (k == 0 || k == n) return 1;  // C(n, 0) = C(n, n) = 1
    return combination(n - 1, k - 1) + combination(n - 1, k);  // 递推公式
}

int main() {
    int n = 5, k = 2;
    printf("C(%d, %d) = %lld\n", n, k, combination(n, k));
    return 0;
}

代码逻辑解释：

• 递归计算：
  使用递归方式计算组合数 C(n,k)。基本情况是 C(n,0)=C(n,n)=1，否则通过递推公式计算。

优点与缺点：

• 优点：递推实现较为简洁，符合杨辉三角的递推性质。
• 缺点：递归深度过大会导致栈溢出，且效率较低，尤其是对于较大的 n。

解法 3：动态规划（难度：★★☆）

通俗解释：
使用动态规划存储已经计算过的组合数，避免重复计算，提升效率。

代码实现：

#include <stdio.h>

long long combination(int n, int k) {
    long long C[k+1];
    C[0] = 1;  // C(n, 0) = 1
    for (int i = 1; i <= n; i++) {
        for (int j = (i < k ? i : k); j > 0; j--) {
            C[j] += C[j-1];
        }
    }
    return C[k];
}

int main() {
    int n = 5, k = 2;
    printf("C(%d, %d) = %lld\n", n, k, combination(n, k));
    return 0;
}

代码逻辑解释：

• 动态规划：
  使用一维数组 C 存储组合数。每次计算新的一行时，依赖上一行的值。通过倒序遍历更新值，避免覆盖尚未计算的值。

优点与缺点：

• 优点：动态规划避免了重复计算，提高了效率。
• 缺点：相对于简单的递归实现，代码稍微复杂。

二、杨辉三角的性质应用：使用杨辉三角解决组合数、二项式定理等相关数学问题

应用 1：计算 (a + b)^n展开式的系数（难度：★★）

通俗解释：
根据二项式定理，(a + b)^n 展开式中的系数就是杨辉三角的第 n 行的元素。例如，(a + b)^5 展开式的系数就是杨辉三角第 5 行的元素：1,5,10,10,5,1。

代码实现：

#include <stdio.h>

void printBinomialCoefficients(int n) {
    long long C = 1;  // 初始值为 C(n, 0) = 1
    for (int k = 0; k <= n; k++) {
        if (k > 0) C = C * (n - k + 1) / k;  // 递推计算 C(n, k)
        printf("%lld ", C);
    }
    printf("\n");
}

int main() {
    int n = 5;
    printf("Coefficients of (a + b)^%d:\n", n);
    printBinomialCoefficients(n);  // 输出 (a + b)^n 展开式的系数
    return 0;
}

代码逻辑解释：

• 二项式展开：
  通过递推公式 C(n,k)=C(n,k−1)⋅(n−k+1)/k来计算每个系数。打印出从 C(n,0) 到 C(n,n)的所有系数。

优点与缺点：

• 优点：通过递推可以高效计算所有系数。
• 缺点：对于较大 n，直接计算可能会有溢出问题。

应用 2：利用杨辉三角计算组合数的其他应用（难度：★★☆）

通俗解释：
利用杨辉三角的递推关系，我们不仅可以计算单个组合数，还可以解决一些与组合数相关的数学问题，如从中挑选不同的组合、求解排列问题等。

代码实现：

#include <stdio.h>

long long combination(int n, int k) {
    if (k == 0 || k == n) return 1;
    return combination(n-1, k-1) + combination(n-1, k);
}

int main() {
    int n = 5, k = 2;
    printf("C(%d, %d) = %lld\n", n, k, combination(n, k));  // 计算 C(5, 2)
    printf("Coefficient of (a + b)^5:\n");
    for (int i = 0; i <= n; i++) {
        printf("C(5, %d) = %lld\n", i, combination(n, i));  // 打印 (a + b)^5 的每个系数
    }
    return 0;
}

代码逻辑解释：

• 递推应用：
  通过组合数的递推公式来计算从中选择不同数量的组合，并打印所有系数。这不仅展示了杨辉三角在计算单个组合数时的应用，也展示了它在二项式定理中的作用。

三、总结对比表

四、特殊方法与内置函数补充

1. 递推公式：
   通过递推公式 C(n,k)=C(n−1,k−1)+C(n−1,k）  来高效计算组合数。

2. 大数处理：
   当 nnn 较大时，阶乘和组合数的计算可能会导致溢出。为了处理这些大数，可以使用 大整数库 或者 模运算（比如使用模10^9 + 7）来避免溢出。

3. 动态规划优化：
   通过动态规划保存中间结果，可以避免重复计算，尤其是对于多个组合数计算时的高效性。

->返回c/c++蓝桥杯经典编程题100道-目录