# Creating a pyramid of numbers with a certain logic

To correctly format your pyramid, supposing you’re using fixed width characters, you need to know beforehand some information, e.g.:

• what is the largest number that you’re going to print.
• how many numbers have which width.

Since the pyramid is increasing downwards, this information is available when you print the last line.

So what you need to do is to calculate (but not output, of course) the last line first. Say that you want five rows, then the middle number will be 2^(5-1), i.e. 16. So you will have to output 1 2 4 8 16. The column positions will be 0 (beginning), 2 (0 plus length of “1” plus 1 space), 4 (2 plus 1 plus 1 space), 6 (4 plus 1 plus 1), 8, 11 (8 plus length of “16” which is 2, plus 1 space), 13, 15, 17.

At this point you start output of the first line, beginning at column 5, i.e. at position 8.

The second line will start at column 4, i.e. at position 6.

And so on.

Another possibility is to imagine you’re filling a table (as if you were generating a HTML table):
– fill it top to bottom
– “explore” every cell size the same way as above, in any order
– generate column positions accordingly
– print the table top to bottom

This requires only one round of calculations, but needs memory storage for the table itself.

A shortcut is to verify what is the largest number you’re gonna print, and format all columns with that width. In this case 16 is 2 characters, so you add one space padding and output all columns padded to 3 character width. This may waste unnecessary space.

The latter case can be implemented using cout.width:

int main() {

int line;

// Read input from standard input
cin >> line;

// We output the pyramid by allocating a fixed width to each number.
// This requires to know beforehand which will be the largest number.
// We can observe that at every line, the largest number is 2 to the
// power of that line number: on line 0, the largest number is 2^0
// which is 1, on line 1 it is 2 which is 2^1... on line 4 it is 16
// which is 2^4. So if we have five lines (from 0 to 4), the largest
// number will be 2 to the 4th.

// Now the length of a number in base 10 is given by the logarithm
// base 10 of that number, truncated, plus 1. For example log10 of
// 1000 is exactly 3, and 3+1 is 4 digits. Log10 of 999 is
// 2.9995654... which truncates to 2, 2+1 is 3 and 999 is 3 digits.

// Here our number is 2 to the power of (line-1).
// By the properties of the logarithm
// this is the same as (line-1)*log10(2), and log10(2) is around 0.3.

// So we multiply (line-1) by log10(2), truncate to integer and add 1
// (or vice versa: we add 1 and then assign to width, which is an
// integer, thereby truncating the value to integer.

// But we need to add another 1 for the padding space (we want 1 2 4
// 2 1, not 12421...). So before assigning, we add 2, not 1.

int width = 2+(line-1)*0.30102999566398119521373889472449;

//////////////////////
// TODO: we're gonna output 2*line+1 strings, each 'width' wide.
// So if (2*line+1)*width > 80 we'd better say it and stop, or the
// output will be sorely messed up, since a terminal is only 80 chars
// wide at the most. Which means that N=9 is the maximum number we
// can print out and still be "nice".
//////////////////////

// For every line that we need to output...
for (int i = 0; i < line; i++) {
for (int j = 0; j < (line-i); j++) {
// Set the width of the next cout to "width" bytes
cout.width(width);
cout<<" ";
}
int n = 1;
// output the forward sequence: 1, 2, 4... doubling each time
for (int j = 0; j < i; j++) {
cout.width(width);
cout <<n;
n *= 2;
}
// output the top number, which is the next doubling
cout.width(width);
cout <<n;

// output the sequence in reverse. Halve, output, repeat.
for (int j = 0; j < i; j++) {
n /= 2;
cout.width(width);
cout<<n;
}
// Now n is 1 again (not that we care...), and we output newline
cout <<"\n";
}

// Return 0 to signify "no error".
return 0;
}


Categories c++ Tags