Search code examples
c++pascals-triangle

Pascal's triangle in C++


I'm trying to make a Pascal triangle in C++. But I couldn't do that! What's wrong with my code?

#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";
 }

And the output is below:

    1 
   1 1 
  1 1 2 
 1 1 2 5 
1 1 2 5 -3 
test

Solution

  • The first thing I would do is not worry about the actual arrangement of the numbers when they're printed. This is a similar concept across all of programming, you want to separate the concern of how things are displayed, the "view" from how things are in data, the "model". Now that you have a conceptual basis for structuring the code, I would also use class structures and objects, since you say that C++ is what you're trying to practice, which is mainly focused around the object-oriented programming (OOP) paradigm. With these ideas in place we can begin to come up with a way for how we want to create the triangle.

    What we want to achieve is the procedural production of the following structure:

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

    to achieve this affect we really want to create:

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

    If you notice from the above diagrams, we can deduce that starting with the axiom (the very first iteration/something assumed to be there before we even start) which in this case is simply a row containing only the number 1, we can see that each production (any given iteration, which has some rule to produce it, starting first with the axiom, 1) is given by adding the two values in the row above it, that have the same index, and the next index. For the sake of the algorithm we're going to assume that if the production can't find a number we'll say that the number exists but isn't shown, and we'll assume that it's 0. (if it's all the way on the left side, there's no first value, and if it's all the way on the right side there's no second value)

    So that means if you look at my second diagram, we have the first row which is just 1 but we're going to pretend that it's really 0,1,0. That gives us a pyramid more like:

    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
    

    The most important part is the axiom 1 which we'll assume to be 0,1,0. Now let's figure out the code for our "production" that is, the method to create a row, given the row before it. We want to make a function that will take a list of numbers from the previous row, and create the next row, assuming that it's padded with our 0s on either side. That function might look something like this:

    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;
    }
    

    In reality this is all we need. Now you simply need to use a trick to put spaces in between them and print them out. I won't do that here, but I'll show you how to use this function to produce a few rows of the triangle:

    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;
    }
    

    I've left putting this into a class object, and also pretty printing it like an actual pascal triangle as exercises for you, I think you should try it out, and spend time really thinking about what's going on in the produceNextRow method.