C++ 中的帕斯卡三角形

Question

我正在尝试用 C++ 制作 Pascal 三角形。但我不能那样做！我的代码有什么问题？

#include <iostream>
using namespace std;

 int main()
 {
    int rows = 5;
    int currentNumber = 1;
    int numbers;
    int tempNumber;
    bool odd;

    for(int i = 0; i < rows; i++)
    {
        numbers = i+1;
        if(i%2 != 0) {
            odd = true;
        } else {
            odd = false;
        }
        for(int j = 0; j < (rows/2)-(numbers/2); j++)
        {
            cout << "  ";
        }
        if(odd)
        {
            cout << " ";
        }

        currentNumber = 1;
        tempNumber = 0;
        for(int k = 0; k < numbers; k++)
        {
            cout << currentNumber << " ";

            if(k > numbers/2) {
                currentNumber-=tempNumber;
                tempNumber-=currentNumber;
            } else {
                currentNumber+=tempNumber;
                tempNumber+=currentNumber;
            }
        }
        cout << endl;
    }

    cout << "test";
 }

输出如下：

Answer 1

我要做的第一件事就是不要担心打印时数字的实际排列。这是所有编程的类似概念，您希望将事物如何显示的关注点“视图”与数据中的事物“模型”分开。现在你已经有了构建代码的概念基础，我也会使用 class 结构和对象，因为你说 C++ 是你正在尝试练习的，它主要集中在面向对象的编程上（面向对象）范式。有了这些想法，我们就可以开始想出一种创建三角形的方法了。

我们要实现的是以下结构的程序化生产：

为了实现这种影响，我们真正想要创造的是：

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

如果您从上图中注意到，我们可以推断出从公理开始（假设第一个 iteration/something 在我们开始之前就已经存在），在这种情况下，它只是一行，仅包含number 1，我们可以看到每个产生式（任何给定的迭代，它有一些产生它的规则，首先从公理 1 开始）是通过将它上面一行中的两个值相加得到的，具有相同索引和下一个索引。为了算法的缘故，我们假设如果产生式找不到一个数字，我们会说这个数字存在但没有显示，我们会假设它是 0。（如果它是所有的一直在左边，没有第一个值，如果一直在右边，就没有第二个值)

所以这意味着如果你看我的第二张图，我们有第一行只是 1 但我们要假装它真的是 0,1,0。这给了我们一个更像的金字塔：

0,1,0
0,1,1,0
0,1,2,1,0
0,1,3,3,1,0
0,1,4,6,4,1,0

最重要的部分是公理 1，我们假设它是 0,1,0。现在让我们找出我们“生产”的代码，即在给定它之前的行的情况下创建一行的方法。我们想要创建一个函数，该函数将从上一行中获取数字列表，并创建下一行，假设它的两边都填充了我们的 0s。该函数可能看起来像这样：

std::vector<int> produceNextRow(std::vector<int> previousRow) {
  std::vector<int> nextRow;

  int left, right = 0;
  /* For each of the numbers in the previous row, plus one more
  because each next row has one more value than the last */
  for( int i = 0; i < previousRow.size()+1 ; i++ ) {
    
    // If we're all the way on the left we need 'left' to be our imaginary 0
    if( i == 0 ) {
      left = 0;
    } else {
      /* Otherwise we want it to be the value in the same position of the
      previous row which is slightly to the left, hence -1 */
      left = previousRow[i-1];
    }

    // If we're all the way on the right, we need 'right' to be our imaginary 0
    if( i == previousRow.size() ) {
      right = 0;
    } else {
     /* Otherwise we want it to be the value of the previous row, at the same
      position */
      right = previousRow[i];
    }

    /* Finally we add left and right, to get our new number, then we put it into
    the next row */
    nextRow.push_back(left+right);
  }

  // Let's return our new row we created
  return nextRow;
}

实际上，这就是我们所需要的。现在你只需要使用一个技巧在它们之间放置空格并将它们打印出来。我不会在这里这样做，但我将向您展示如何使用此函数生成几行三角形：

int main(int argc, char *argv[]) {

  // Vector of vectors of ints! This is our entire triangle
  std::vector<std::vector<int>> triangle;
  std::vector<int> axiom {1};

  // Lets put our axiom into the triangle first
  triangle.push_back(axiom);

  // Alright, for the sake of example lets do some number of productions like 6
  int productions = 6;
  for( int i=0; i < productions ; i++ ) {
    triangle.push_back(produceNextRow(triangle[i]));
  }

  /* Now lets print out our triangle, you'd replace this with something fancy
  that maybe computes how many spaces are required, and makes the triangle look
  better. I'll leave that as an exercise for you */

  // For each row in the triangle
  for( int i=0; i < triangle.size() ; i++ ) {
    // For each number in the row
    for( int j=0; j < triangle[i].size() ; j++ ) {
      // print that number followed by a comma and a space
      std::cout << triangle[i][j] << ", ";
    }
    // print a new line after each row
    std::cout << std::endl;
  }

  return 0;
}

我已经把它放到一个 class 对象中，并且还把它打印成一个真正的帕斯卡三角形作为练习给你，我认为你应该尝试一下，花时间真正思考什么是在 produceNextRow 方法中进行。

Answer 2

如果您将三角形想象成左对齐 (https://en.wikipedia.org/wiki/Pascal%27s_triangle#Overall_patterns_and_properties)，那么它可以表示为二维数组：

#include <iomanip> //setw
....

    static int const size = 20;
    int const width = 6;
    int cell[size][size+1];

    for (int i = 0; i < size; ++i)
    {
        cell[i][0] = 1;
        cell[i][i + 1] = 0;

        std::cout << std::string((size - i) * width / 2, 0x20) << cell[i][0];

        for (int j = 1; j <= i; ++j)
        {
            cell[i][j] = cell[i - 1][j - 1] + cell[i - 1][j];
            std::cout << std::setw(width) << cell[i][j];
        }

        std::cout << std::endl;
    }

打印：

C++ 中的帕斯卡三角形

Pascal's triangle in C++

c++

pascals-triangle