C++ 程序帕斯卡三角形

帕斯卡三角形是二项式系数的一个三角形数组。编写一个函数，以整数值 n 作为输入，并输出帕斯卡三角形的前 n 行。以下是帕斯卡三角形的前 6 行。

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

方法 1（O（n ^ 3）时间复杂度）

每行的条目数等于行数。例如，第一行有“1”，第二行有“1 1”，第三行有“1 2 1”，..以此类推。每行中的每个条目是二项式系数的值。第i个入口的值在第line行中是C（line，i）。该值可以使用以下公式计算。

C(line, i)   = line! / ( (line-i)! * i! )

一个简单的方法是运行两个循环并在内循环中计算二项式系数的值。

//  C++ code for Pascal's Triangle
#include <iostream>
using namespace std;
  
// See https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/ 
// for details of this function
int binomialCoeff(int n, int k);
  
// Function to print first
// n lines of Pascal's 
// Triangle
void printPascal(int n)
{
    // Iterate through every line and
    // print entries in it
    for (int line = 0; line < n; line++)
    {
        // Every line has number of 
        // integers equal to line 
        // number
        for (int i = 0; i <= line; i++)
            cout <<" "<< binomialCoeff(line, i);
        cout <<"\n";
    }
}
  
// See https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/
// for details of this function
int binomialCoeff(int n, int k)
{
    int res = 1;
    if (k > n - k)
    k = n - k;
    for (int i = 0; i < k; ++i)
    {
        res *= (n - i);
        res /= (i + 1);
    }
      
    return res;
}
  
// Driver program 
int main()
{
    int n = 7;
    printPascal(n);
    return 0;
}

输出：

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1

附加空间： O(1)

这种方法的时间复杂度是O（n ^ 3）。以下是优化的方法。

方法2（O（n ^ 2）时间和O（n ^ 2）额外空间）

我们观察三角形时会发现，每个条目都是其上方两个值的总和。因此，我们可以创建一个二维数组来存储已生成的值。要在一行中生成一个值，我们可以使用数组中之前存储的值。

C++ 程序帕斯卡三角形

// C++程序，输出帕斯卡三角形
// 时间复杂度O(n^2)，空间复杂度O(n^2)
#include <bits/stdc++.h>
using namespace std;
  
void printPascal(int n)
{
      
    // 辅助数组，存储生成的帕斯卡三角形的值
    int arr[n][n]; 
  
    // 遍历每一行，并打印出其中的整数
    for (int line = 0; line < n; line++)
    {
        // 每一行包含整数数目等于行数
        for (int i = 0; i <= line; i++)
        {
        // 每一行的第一个和最后一个值为1
        if (line == i || i == 0)
            arr[line][i] = 1;
        // 其他值为上一行(i-1)和(i)以及左上方的值的和
        else
            arr[line][i] = arr[line - 1][i - 1] + 
                            arr[line - 1][i];
        cout << arr[line][i] << " ";
        }
        cout << "\n";
    }
}
  
// 主函数
int main()
{
    int n = 5;
    printPascal(n);
    return 0;
}

输出结果:

此方法可以进行优化，使用O(n)的空间，因为我们只需要上一行的值。因此，我们可以创建一个大小为n的辅助数组并覆盖已有值。以下是使用O(1)空间的另一种方法。

方法3 (时间复杂度O(n^2)，空间复杂度O(1))

该方法基于方法1。我们知道第i个条目的行数为line时，二项式系数为C（line、i），所有行都以值1开始。思路是使用C(line、i-1)来计算C(line、i)，可以使用以下方法在O(1)的时间内计算。

C(line, i) = line! / ( (line-i)! * i! )
C(line, i-1) = line! / ( (line – i + 1)! * (i-1)! )
我们可以从上面两个式子推导出以下表达式
C(line, i) = C(line, i-1) * (line – i + 1) / i

因此，可以从C(line, i-1)中得出C(line, i)的值。

// C++程序，输出帕斯卡三角形
// 时间复杂度O(n^2)，空间复杂度O(1)
#include <bits/stdc++.h>
  
using namespace std;
void printPascal(int n)
{
      
for (int line = 1; line <= n; line++)
{
    int C = 1; // 用于表示C(line, i)
    for (int i = 1; i <= line; i++) 
    {
          
        // 每一行的第一个值总为1
        cout<< C<<" "; 
        C = C * (line - i) / i; 
    }
    cout<<"\n";
}
}
  
// 主函数
int main()
{
    int n = 5;
    printPascal(n);
    return 0}

输出结果: