## $Id: s2-chevron.html,v 1.4 1996/09/21 21:28:25 ellard2 Exp ellard2 $ ## Dan Ellard -- 10/09/94

** ** ** ** **

However, some of the algorithms that were devised to generate the
chevrons were quite a bit different than I would have expected, and
some were quite a bit more complicated than I expected or hoped to
see. While I enjoy a complicated algorithm from time to time,
*unnecessarily* complicated algorithms are usually nothing but
trouble. Therefore, I thought I'd take a few moments and write down a
short discussion of several algorithms for printing a chevron.

For the sake of simplicity, I'm going to pretend that the assignment is just to write a program that takes a single number and prints a chevron of that size (with no error checking, instructions, etc). This will let me focus on the heart of the algorithm, and skip over the rest of the mechanics (although the rest of the stuff is very important, of course!).

/* ************************************************************ */ /* Dan Ellard chevron1.c-- The bread-and-butter chevron program. */ /* ************************************************************ */ #include <stdio.h> #include "genlib.h" #include "simpio.h" void main () { int size = GetInteger (); int row; int spaces; int stars; for (row = 0; row < size; row++) { for (spaces = 0; spaces < row; spaces++) printf (" "); for (stars = 0; stars < size; stars++) printf ("*"); printf ("\n"); } for (spaces = 0; spaces < size; spaces++) printf (" "); for (stars = 0; stars < size; stars++) printf ("*"); printf ("\n"); for (row = size - 1; row >= 0; row--) { for (spaces = 0; spaces < row; spaces++) printf (" "); for (stars = 0; stars < size; stars++) printf ("*"); printf ("\n"); } exit (0); } /* ***************** */ /* end of chevron1.c */ /* ***************** */This is a perfectly good algorithm. (Of course, how it's written leaves something to be desired- it's horribly short on comments!) It identifies the three main parts of the chevron- the loop where the chevron is "moving to the right", the single middle line with as many spaces as stars, and the loop where the chevron is moving back to the left again.

/* ************************************************************ */ /* Dan Ellard chevron2.c-- A variation on chevron1.c: noticing that the middle row of the chevron is just the next row that the first for loop would have printed, and letting it continue on. (the same effect could be gotten by letting the second for loop start at row = size - 1.) */ /* ************************************************************ */ #include <stdio.h> #include "genlib.h" #include "simpio.h" void main () { int size = GetInteger (); int row; int spaces; int stars; for (row = 0; row <= size; row++) { for (spaces = 0; spaces < row; spaces++) printf (" "); for (stars = 0; stars < size; stars++) printf ("*"); printf ("\n"); } for (row = size - 1; row >= 0; row--) { for (spaces = 0; spaces < row; spaces++) printf (" "); for (stars = 0; stars < size; stars++) printf ("*"); printf ("\n"); } exit (0); } /* ***************** */ /* end of chevron2.c */ /* ***************** */One again, this is a perfectly good algorithm, but the way that the middle line gets built as a sort of special case of the first or last loops needs a little extra comment (which I have not made in this program!).

If you gave 100 grizzled programmers this simplified chevron problem, and asked them to put together a C program to solve it, 99 of them would probably come up with something very much like the first or the second algorithms.

Modifying the first main loop from the previous algorithm to run from -size to zero, and the second loop to run from 1 to size, I realize that I can combine the loops into a single loop, plus a small amount of logic to make sure that I get the right sign on the number of spaces to print out (I wish C had an absolute value operator!). This gives the following:

/* ************************************************************ */ /* Dan Ellard chevron3.c-- Another variation on chevron1.c: noticing that there is symmetry between the top and bottom of the chevron, making a single for loop which iterates from row = -size to row = size. */ /* ************************************************************ */ #include <stdio.h> #include "genlib.h" #include "simpio.h" void main () { int size = GetInteger (); int row; int spaces; int stars; int spaces_needed; for (row = -size; row <= size; row++) { spaces_needed = (row < 0) ? size + row : size - row; for (spaces = 0; spaces < spaces_needed; spaces++) printf (" "); for (stars = 0; stars < size; stars++) printf ("*"); printf ("\n"); } exit (0); } /* ***************** */ /* end of chevron3.c */ /* ***************** */That's certainly short and simple, but probably deserves a bit more commenting than the previous algorithms (and an awful lot more than I've given it).

for (row = 0; row < 2 * size + 1; row++) { if ( I'm in the top part ) print a top-part row else if ( I'm in the middle ) print the middle row else print a bottom-part row }This works, but is very clumsy, especially because of the complicated formulas necessary to figure out how many spaces to print (particularly in the bottom-part row. It's much simpler to have different loops counting up or down in order to figure out the number of spaces directly from the index of the loop.

Stylistically, this algorithm is also very misleading. The if-else inside the loop is not a function of anything except the row and the size, so there really isn't any question which way you're going to go on each particular iteration. The if-else is essentially just a way to fake the single for-loop into behaving like two separate loops. Don't do it!

Dan Ellard <ellard@deas.harvard.edu>