Heading 1

Computing the Height of a Staircase

Assume a staircase is constructed using the following design:

Our program calculates the number of bricks required given the desired height of the staircase.

Program Output

Enter staircase height: 3

# bricks required = 6 (= 6)
Enter staircase height: 4

# bricks required = a (= 10)
Enter staircase height: 5

# bricks required = f (= 15)
Enter staircase height: 20

# bricks required = 210 (= 528)
Enter staircase height:

main()

We begin by increasing the amount of stack space and setting the debug flag:

#define CAPACITY 1024
#define DEBUG
#include "..\cmm.h"

Here's main():

void main()
{
Again:
   PROMPT("Enter staircase height: ");
   GETWORD(reg1);
   PUSH(reg1);
   tri();
   POP();
   NEWLINE();
   PROMPT("# bricks required = ");
   PUTWORD(reg0);
   NEWLINE();
   goto Again;
   return;
}

Recursive Version

The recursive version is based on the following observation:

tri(n) = n + tri(n - 1)

where

tri(n) = # of bricks needed to build a height n staircase
= nth triangle number

Here it is:

void tri()
{
   PUSH(reg1); /* save caller's state */
   reg1 = mem[sp + 2]; /* reg1 = argument */
   if (0 < reg1) goto Recur;
   reg0 = 0;
   goto Done;
Recur:
   reg1 -= 1;
   PUSH(reg1);
   tri();
   POP();
   reg1 = mem[sp + 2];
   reg0 += reg1; /* = arg * (arg - 1)! */
Done:
   reg1 = TOP(); /* restore caller's state */
   POP();
   return;
}

Elementary Version

The elementary (non-recursive, non-iterative) version is based on the following observation:

tri(n) = n * (n + 1) / 2

Here it is:

void tri()
{
   reg0 = mem[sp + 1]; /* reg0 = argument */
   reg0 *= (reg0 + 1);
   reg0 /= 2;
}