DECLARE FUNCTION Cat# (n AS INTEGER)

DIM Number AS INTEGER

CLS

LOCATE 2, 1
   PRINT STRING$(40, "=")
   PRINT "   Calculate the Catalan number for n"
   PRINT STRING$(40, "-")

LOCATE 18, 1
   PRINT STRING$(40, "-")
   PRINT "            Enter 0 to Exit"
   PRINT STRING$(40, "=")

VIEW PRINT 6 TO 16

DO

   INPUT "Enter n: ", Number

   SELECT CASE Number

      CASE IS <= 0
         END

      CASE IS = 1
         PRINT "You're a business major, right?"
         PRINT

      CASE IS = 2
         PRINT "How's the lobotomy working out?"
         PRINT

      CASE ELSE
         PRINT "Cat("; Number; ") ="; Cat#(Number)
         PRINT

   END SELECT

LOOP

FUNCTION Cat# (n AS INTEGER)

DIM Denom   AS DOUBLE
DIM Numer   AS DOUBLE
DIM Result  AS DOUBLE
DIM I       AS INTEGER

' Cat(n) was derived from the following identity:
'
'      (2n - 2)!     (n + 1)(n + 2) ... (2n - 2)
'    -----------  =  ---------------------------
'    (n - 1)! n!             (n - 1)!

' First, we calculate the numerator.

Numer = n + 1

FOR I = (n + 2) TO ((2 * n) - 2)   ' Condition: n >= 3
   Numer = Numer * I
NEXT I

' Next, we calculate the denominator.

Denom = 1

FOR I = 2 TO (n - 1)   ' Condition: n >= 3
   Denom = Denom * I
NEXT I

' Taking a/b directly for large integers is inefficient. However,
' it's good enough to make the point that a brute-force approach
' is inadequate to the task of finding the best case for chained
' matrix multiplication.

Result = Numer / Denom

' Obviously, using floating-point numbers is going to cause a
' problem so we filter Result accordingly.

IF (Result - INT(Result)) >= .499999999999998# THEN
   Cat = INT(Result) + 1
ELSE
   Cat = INT(Result)
END IF

END FUNCTION