Floyd's triangle

Why this matters

The patterns in the earlier lessons print the same character everywhere. A star is a star, so the loops only decide where each star goes. Floyd's triangle is different. Each printed value depends on the value before it, and that value was printed by an earlier pass of the loop. You have to carry a fact from one step to the next. This habit appears in many programs: a running total of a shopping cart, a line number in a file, or the position of the next item to read.

Pascal's triangle, the lesson before this one, also builds a triangle of numbers, but each number there is worked out from the row above. Here the rule is simpler. The next number is one more than the previous number.

The shape

Floyd's triangle is a triangle of whole numbers that is right-angled. A right-angled triangle has one square corner, like the corner of a book. In Floyd's triangle the left edge runs straight down and the bottom edge is flat.

Row 1 has one number. Row 2 has two. Row 3 has three. Row r has r numbers. A four-row triangle looks like this:

1
2 3
4 5 6
7 8 9 10

The numbers run from 1 to 10, left to right and top to bottom. Nothing is skipped and nothing repeats.

Ask two questions about this picture before you write any code. The first question is where row 3 starts. It starts at 4, because row 2 ended with 3 and the next number is 4. You found that answer by looking at the number before it, not by using a formula. The second question is how many numbers the triangle holds. Row 1 has 1, row 2 has 2, row 3 has 3 and row 4 has 4. The total is 1 + 2 + 3 + 4, which is 10. The last number printed is also 10, because the numbers start at 1 and go up by one.

The idea: one counter for the whole triangle

A counter is a variable whose only job is to hold the next number to print. In the code below it is called next. Each time a number is printed, the counter goes up by one. Here is the order of events for the first three numbers of the four-row triangle.

start:            next is 1
row 1, cell 1:    print 1, then next becomes 2
row 2, cell 1:    print 2, then next becomes 3
row 2, cell 2:    print 3, then next becomes 4
row 3, cell 1:    print 4, then next becomes 5

Notice that the counter is never reset. Row 2 starts at 2 because the counter already holds 2 when row 2 begins. The counter carries the answer from one row to the next.

The rule for the code follows from this. Declare the counter once, before the outer loop. Add to it only when you print a number. The outer loop walks through the rows. The inner loop walks through the cells in one row. Both loops use the same counter.

Here is the whole plan, written as plain steps. The text is pseudocode, which means a description of the steps that is not yet a program.

counter = 1
for each row from 1 to the number of rows:
    for each cell from 1 to the row number:
        print counter
        add 1 to counter
    move to a new line

The inner loop runs row times, so row 1 gets one cell, row 2 gets two cells and so on. That is what gives the triangle its straight left edge and its slanting right edge.

First program: the plain triangle

This program prints the four-row triangle. Read it first, then press Run.

Press Run. There is no input for this program, so leave the Input box empty. The output is:

1 
2 3 
4 5 6 
7 8 9 10 

Take the program apart line by line.

• #include <iostream> loads the tools for writing text to the screen. Any program that prints with std::cout needs it.
• const int rows = 4; stores the number of rows. The word const means the value does not change while the program runs.
• int next = 1; creates the counter. It is declared once, above both loops.
• for (int row = 1; row <= rows; ++row) is the outer loop. It runs once for each row, with row set to 1, then 2, then 3, then 4. The condition row <= rows means "keep going while row is less than or equal to rows".
• for (int col = 1; col <= row; ++col) is the inner loop. It prints one number for each cell in the current row. When row is 3, it runs three times.
• std::cout << next << ' '; writes the value of the counter, then a space. std::cout is the standard output stream, which is the text that goes to the screen. The std:: prefix means the name comes from the standard library.
• ++next; adds 1 to the counter. The word ++ is the increment operator. It means "add one".
• std::cout << '\n'; ends the row. The '\n' is the newline character, which moves the cursor to the start of the next line.

Look at the output. Each number is followed by a space, so every row ends with a space before the line break. You cannot see that space on the screen, but it is in the output. For this lesson it does no harm. Later, when you compare output with an exact expected text, a trailing space can make a correct answer look wrong. The next program avoids it.

Second program: lining up the columns

The first program looks right only because every number has one digit so far. Change the number of rows to five and the last row has two-digit numbers. The output below is what the first program prints with five rows. Its trailing spaces are left out here.

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

The left edge is still straight, but the columns no longer line up. Look at the second column: 3, 5, 8 and 12. In a neat triangle those numbers would sit one under another. Here the two-digit numbers push the rest of each row to the right, so a reader has to work harder to see the shape.

The fix is to give every number the same width. The width is the number of characters the widest number needs. The widest number in a five-row triangle is 15, which has two characters, so every number gets two characters of space.

Here is the program that does that.

Press Run. There is no input for this program. The output is:

 1
 2  3
 4  5  6
 7  8  9 10
11 12 13 14 15

Here is how the new parts work.

• const int last = rows * (rows + 1) / 2; computes the largest number in the triangle. It uses the total from the first section, 1 + 2 + ... + rows, in the form rows * (rows + 1) / 2. For five rows that is 5 times 6 divided by 2, which is 15.
• std::to_string(last) turns the number 15 into the text "15". The .size() part counts the characters in that text, which gives 2. The static_cast<int> changes the count to a plain int. The reason is that size() returns an unsigned type, and std::setw expects an int. A static_cast tells the compiler that the change is intended.
• std::setw(width) sets the minimum number of characters for the next thing printed. If the value is shorter, it is padded with spaces on the left. So 1 is printed as 1, which is two characters. A value that is already as wide as width is printed unchanged.
• The line if (col > 1) adds a space only before the second, third and later numbers in a row. The first number in each row does not get a space before it. That keeps the separator between numbers and avoids the trailing space from the first program.

One detail matters a lot. std::setw applies only to the next item printed. It is not a permanent setting. That is why it sits right before next in the code. If you wrote std::cout << std::setw(width); once before the loops, the first number would be padded and the others would not.

Notice the output. Every number now takes exactly two characters, so each column lines up under the one above it.

Third program: where is a number?

Now use the counter to answer a different question. In the four-row triangle, which row and which column hold the number 7? The answer is row 4, column 1. The program below finds that answer the same way the printing program walks through the numbers. It counts, and it stops when the counter equals the target.

Press Run. The output is:

number 1: row 1, column 1
number 2: row 2, column 1
number 3: row 2, column 2
number 6: row 3, column 3
number 7: row 4, column 1
number 10: row 4, column 4
number 15: row 5, column 5
number 0: row 0, column 0
first numbers match formula: yes

The new ideas here are these.

• struct Position groups two named values into one type. A struct is a simple way to bundle related values. Position has two fields, row and col.
• return {row, col}; builds a Position from the two numbers in braces and hands it back to the caller.
• The loop for (int row = 1; ; ++row) has no end condition. It keeps going until the return inside it runs. That is safe here because every positive number appears somewhere in the triangle, so the search always ends. For a target less than 1 no number matches, so the loop would never end. The guard at the top of the function returns {0, 0} in that case. The output shows that answer for 0.
• The check at the bottom of main uses a formula. The first number in row r is r * (r - 1) / 2 + 1. Here is why. The rows before row r hold 1 + 2 + ... + (r - 1) numbers. That sum equals (r - 1) * r / 2. The first number of row r is one more than that count. For row 4 the formula gives 4 * 3 / 2 + 1, which is 7, and the triangle agrees.

The division in the formula is whole-number division. That is safe here, because r * (r - 1) is always even. It is the product of two numbers in a row, one of which is even.

Which method should you use? If you are printing every number anyway, the counter is the natural choice, because you have to walk through the numbers. If you only need to jump straight to one row, the formula is faster, because it gives the first number of a row without visiting the numbers before it.

Common mistakes

Resetting the counter inside the row loop

A common first attempt puts int next = 1; inside the outer loop. That looks tidy, because each row seems to begin with its own variable. The result is wrong.

The output is:

1 
1 2 
1 2 3 

Every row starts at 1, because the counter is created again at the start of each row. The counter must be declared before the outer loop, so that its value survives from one row to the next. The fix is to move the line int next = 1; above for (int row = 1; ...).

Using < where <= is meant

Another common mistake is the condition of the inner loop.

The output is:

 
1 
2 3 

The first line is empty. Row 1 should hold one number, but the condition col < row is false when col is 1 and row is 1, so the inner loop never runs. Row 2 holds only one number, and row 3 holds two instead of three. The counter still counts correctly, but the triangle is one cell short in every row. The fix is to use <=, so that the inner loop runs row times.

A simple check helps here. Work out by hand how many times the inner loop should run for row 1. If the answer is one and the loop runs zero times, the condition is wrong.

Forgetting the header for std::setw

The std::setw function lives in a separate header called <iomanip>. If you use it without including that header, the compiler stops. This short program uses std::setw and leaves out the header. The line numbers in the error refer to this file.

#include <iostream>
 
int main() {
    int next = 7;
    std::cout << std::setw(3) << next << '\n';
    return 0;
}

The error that g++ prints for it is:

m3_nosetw.cpp: In function ‘int main()’:
m3_nosetw.cpp:5:23: error: ‘setw’ is not a member of ‘std’
    5 |     std::cout << std::setw(3) << next << '\n';
      |                       ^~~~
m3_nosetw.cpp:2:1: note: ‘std::setw’ is defined in header ‘<iomanip>’; this is probably fixable by adding ‘#include <iomanip>’
    1 | #include <iostream>
  +++ |+#include <iomanip>
    2 | 

The first line of the error names the function that failed. The line error: 'setw' is not a member of 'std' means the compiler looked in the std namespace and did not find the name. The note tells you which header defines it and suggests the fix. Add #include <iomanip> at the top of the file and the error goes away.

Your compiler may word the error a little differently, but the meaning is the same. When a name from the standard library is "not a member of std", check the header that defines it.

Practice

Exercise 1: No trailing spaces

Print a five-row Floyd's triangle with a single space between numbers. Do not print a space at the end of any row.

Show the answer

The answer prints the space before every number except the first in a row. This is the same idea as the second program, but without std::setw.

#include <iostream>
 
int main() {
    const int rows = 5;
    int next = 1;
    for (int row = 1; row <= rows; ++row) {
        for (int col = 1; col <= row; ++col) {
            if (col > 1) {
                std::cout << ' ';
            }
            std::cout << next;
            ++next;
        }
        std::cout << '\n';
    }
    return 0;
}

The output is:

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

Exercise 2: Count down

A four-row triangle uses the numbers 1 to 10. Print the same shape, but with the numbers counting down from 10 to 1. The first row should print 10 and the last row should end with 1.

Show the answer

Start the counter at the largest number, which is 10, and subtract one after each printed number with --next.

#include <iostream>
 
int main() {
    const int rows = 4;
    int next = rows * (rows + 1) / 2;
    for (int row = 1; row <= rows; ++row) {
        for (int col = 1; col <= row; ++col) {
            if (col > 1) {
                std::cout << ' ';
            }
            std::cout << next;
            --next;
        }
        std::cout << '\n';
    }
    return 0;
}

The output is:

10
9 8
7 6 5
4 3 2 1

Exercise 3: Predict the output

Read this program and write down what it prints before you run it. Then run it to check.

#include <iostream>
 
int main() {
    const int rows = 3;
    int next = 1;
    for (int row = 1; row <= rows; ++row) {
        for (int col = 1; col <= row; ++col) {
            std::cout << next << ' ';
            // ++next is missing here
        }
        std::cout << '\n';
    }
    return 0;
}

Show the answer

The counter never goes up, so every number is 1. The output has one 1 in row 1, two in row 2 and three in row 3. The output is:

1 
1 1 
1 1 1 

The lesson is that a loop can run correctly and still print wrong values, when the counter update is missing.

Exercise 4: Count the numbers

For a six-row triangle, how many numbers are printed, and what is the largest one? Work out the answer on paper, then write a program that counts them and compare.

Show the answer

Row r holds r numbers, so the total is 1 + 2 + 3 + 4 + 5 + 6, which is 21. The numbers start at 1 and go up by one each time, so the largest number is also 21. The program below counts the numbers while it walks through them.

#include <iostream>
 
int main() {
    const int rows = 6;
    int count = 0;
    int largest = 0;
    int next = 1;
    for (int row = 1; row <= rows; ++row) {
        for (int col = 1; col <= row; ++col) {
            ++count;
            largest = next;
            ++next;
        }
    }
    std::cout << "numbers printed: " << count << '\n';
    std::cout << "largest number: " << largest << '\n';
    return 0;
}

The output is:

numbers printed: 21
largest number: 21

Exercise 5: The first number of each row

For a six-row triangle, print the first number of each row. Use only the counter. Do not use the formula from the third program.

Show the answer

Walk through every cell with the counter, as the printing program does. Print the counter at the start of each row, before the inner loop runs.

#include <iostream>
 
int main() {
    const int rows = 6;
    int next = 1;
    for (int row = 1; row <= rows; ++row) {
        std::cout << "row " << row << " starts at " << next << '\n';
        for (int col = 1; col <= row; ++col) {
            ++next;
        }
    }
    return 0;
}

The output is:

row 1 starts at 1
row 2 starts at 2
row 3 starts at 4
row 4 starts at 7
row 5 starts at 11
row 6 starts at 16

These numbers match the formula r * (r - 1) / 2 + 1 from the third program.

Summary

• Floyd's triangle is a right-angled triangle of consecutive numbers, and row r holds r numbers.
• One counter, declared before the outer loop, carries the next number from one row to the next.
• The counter goes up only when a number is printed.
• The first number of row r is r * (r - 1) / 2 + 1, which lets you jump to a row without walking through the earlier ones.
• std::setw with the width of the largest number keeps the columns lined up, and <iomanip> must be included to use it.
• The three common errors are resetting the counter inside the row loop, using < where <= is meant, and leaving out <iomanip>.