How do you implement Pascal's Triangle in C plus plus?

Answer 1

There are many ways to implement Pascal's Triangle in C++. One of the easiest ways is to use a vector of vectors, which is essentially a two-dimensional dynamic array. Although you could use a static 2D array, the matrix would need to be sparse because the first row has only one value, while the second has two values, and so on. Unused elements would need to store the value zero, but unused elements are wasteful. You could improve upon this by creating a 1D array of dynamic arrays, however C++ vectors are much easier to work with and achieve the same thing.

The following program asks the user to enter the top value of the triangle and the number of rows in the triangle. The range of acceptable values has been limited to ensure all printed triangles will fit comfortably within an 80-character console window.

The program employs a simple class definition to encapsulate the triangle and its methods. The default constructor builds the triangle using the top value and the number of rows supplied from the user-input, while the print function displays the triangle's values in a symmetric triangle formation.

#include<iostream>

#include<iomanip>

#include<vector>

#include<string>

#include<sstream>

// Some typdefs to simplify coding.

typedef unsigned int uint;

typedef std::vector<uint> row;

// Simple class definition.

class pascal_triangle

{

public:

pascal_triangle(uint top=1, uint rows=10);

void print();

private:

const uint get_width();

std::vector<row> m_triangle;

};

// Default constructor:

pascal_triangle::pascal_triangle(uint top, uint rows)

{

for(uint i=0;i<rows;++i)

{

row r;

uint x=top;

for(uint k=0;k<=i;++k)

{

r.push_back(x);

x=x*(i-k)/(k+1);

}

m_triangle.push_back(r);

}

}

// Return the width required for the largest value.

const uint pascal_triangle::get_width()

{

// Reference the last row of the triangle.

row& r=m_triangle[m_triangle.size()-1];

// Determine the largest value in that row.

uint largest=0;

for(uint i=0;i<r.size();++i)

if(r[i]>largest)

largest=r[i];

// Determine required width plus one space.

uint width=1;

do

{

largest/=10;

++width;

} while( largest );

// Return an even width.

return(width+width%2);

}

// Print the given triangle:

void pascal_triangle::print()

{

// Call private method to determine width.

const uint width=get_width();

// Repeat for each row...

for(uint i=0;i<m_triangle.size();++i)

{

// Insert half-width padding spaces.

std::cout<<std::setw((m_triangle.size()-i)*(width/2))<<' ';

// Print the row values.

row& r=m_triangle[i];

for(uint j=0;j<r.size();++j)

std::cout<<std::setw(width)<<r[j];

std::cout<<std::endl;

}

std::cout<<std::endl;

}

// Print the given range:

void print_range(const uint min,const uint max)

{

std::cout<<'['<<min<<".."<<max<<']';

}

// Return a natural number in the given range from user input:

uint enter_natural(const std::string& prompt,const uint min,const uint max)

{

uint result=0;

while(!result)

{

std::cout<<'\n'<<prompt<<' ';

print_range(min,max);

std::cout<<": ";

std::string in;

std::getline(std::cin,in);

std::stringstream(in)>>result;

if(result<minresult>max )

{

std::cout<<"The valid range is ";

print_range(min,max);

std::cout<<"\nPlease try again.\n"<<std::endl;

result=0;

}

}

std::cout<<std::endl;

return(result);

}

int main()

{

std::cout<<"Pascal's Triangle\n"<<std::endl;

uint top=enter_natural("Enter top value",1,10);

uint rows=enter_natural("Enter number of rows",2,10);

pascal_triangle t(top,rows);

t.print();

return(0);

}