Your challenge, should you choose to accept it, is to generate and properly display Pascal’s triangle for some command-line argument input number of lines N in [0,32]. Your program should be 50 lines or fewer.
#include <iostream>
#include <vector>
#include <cmath>
usingnamespace std;
using INT = unsignedlonglong;
int numDigits( INT n ){ return n < 10 ? 1 : 1 + numDigits( n / 10 ); }
void space( int n ){ while( n-- ) cout << ' '; }
double lognCr( int n, int r )
{
if ( n == 0 || n == r || r == 0 ) return 0.0;
double result = 0.0;
for ( int i = 0; i < r; i++ ) result += log10( ( n - i ) / ( 1.0 + i ) );
return result;
}
void cell( INT n, int width )
{
int length = numDigits( n );
int pre = ( width - length ) / 2;
int post = width - length - pre;
space( pre );
cout << n;
space( post);
}
void printPascal( int N, bool narrow )
{
int width = floor( lognCr( N, N / 2 ) ) + 1.1;
int gap = narrow ? 2 + width % 2 : width;
vector<INT> row, old;
for ( int r = 0; r <= N; r++ )
{
old = row;
for ( int i = 1; i < r; i++ ) row[i] = old[i] + old[i-1];
row.push_back( 1 );
space( ( N - r ) * ( width + gap ) / 2 );
for ( INT I : row ) { cell( I, width ); space( gap ); }
cout << '\n';
}
}
int main()
{
int N;
cout << "Enter N (row 0 is apex): "; cin >> N;
printPascal( N, false );
}
You managed your spacing differently than I did. You did catch on to the need to determine the width of the bottom, center element and the mathematical properties to compute it. Your method of computation is unique as well.
A well-organized solution! Also, frist → bonus points!
I should note that the input N is the number of rows, so an input of 0 should print nothing, 1 should print the top row, 2 the second, etc. Sorry the challenge didn’t express that clearly enough.
Also, I adjusted the challenge to accept any reasonable method of input, like I should have to begin with.
I’ll wait a little longer before posting my solution as well.
#include <iostream>
#include <vector>
usingnamespace std;
using INT = unsignedlonglong;
int numDigits( INT n ){ return n < 10 ? 1 : 1 + numDigits( n / 10 ); }
void space( int n ){ while( n-- ) cout << ' '; }
void printPascal( int N, bool narrow, bool left )
{
vector<vector<INT>> triangle;
for ( int r = 0; r <= N; r++ )
{
triangle.push_back( vector<INT>( r + 1, 1 ) );
for ( int j = 1; j < r; j++ ) triangle[r][j] = triangle[r-1][j] + triangle[r-1][j-1];
}
int width = numDigits( triangle[N][N/2] );
int gap = narrow ? 2 + width % 2 : width;
for ( int r = 0; r <= N; r++ )
{
space( ( N - r ) * ( width + gap ) / 2 );
for ( INT I : triangle[r] )
{
int length = numDigits( I );
int pre = left ? 0 : ( width - length ) / 2;
space( pre );
cout << I;
space( gap + width - length - pre );
}
cout << '\n';
}
}
int main()
{
int N;
cout << "Enter N (row 0 is apex): "; cin >> N;
printPascal( N, false, false );
}
If the top line corresponds to N=1 then change the penultimate line to if ( N > 0 ) printPascal( N - 1, false, false );
Setting the second argument sent to printPascal to true will make the gaps smaller for large N.
Setting the third argument sent to printPascal to true will left-align each column, but will cause a gradual swing to the right down a column as the numbers get larger. (Edited to allow this, but not turned on by default)
Ah, that is indeed neat. A 'simple' problem with a surprising amount of scope for different answers - even in just generating the elements of a familiar triangle. Having the 'narrow' option definitely helps when N reaches 32.
I guess what is 'neat and tidy' is a bit subjective: my children and I always used to reach opposing conclusions as to whether their bedrooms were 'tidy'. Having some options in coding (as in family life) gives scope to keep everybody happy.
Hi @duthomas,
A rather pretty variant of this is to work out Pascal's triangle in MODULAR ARITHMETIC, printing solid for non-zero, blank for 0 (ie those original numbers that are divisible by the base).
It produces beautiful fractals (BASE=2 gives the Sierpinski gasket).
Have to admit that the idea (but not the code) came from Alex Bellos's book "Alex’s Adventures in Numberland" (which my family gave me for Christmas). There's also some brilliant sequences in there ... which will do for next year's challenge.