CONSTRAINED AND UNCONSTRAINED ARRAYS

3. EXAMPLE PROBLEM PASCAL'S TRIANGLE

3.1. Requirements

To develop an Ada program that expands expressions of the form (1+x)^n, for any value of n ranging from 1 to 32, using Pascal's triangle to determine the appropriate coefficients. Recall that Pascal's triangle is of the form:

            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10   5   1
  1   6  15  20  15   6   1
1   7  21  35  35  21   7   1
Etc.

where the start and end coefficient in each line are 1 (unity) and each of the other coefficients is the sum of the corresponding coefficient and the preceding coefficient in the line above. Examples:

                          (1 + x) = 1 + x
       (1 + x)^2 = (1 + x)(1 + x) = 1 + 2x + x^2
(1 + x)^3 = (1 + x)(1 + x)(1 + x) = 1 + 3x + 3x^2 + x^3
     (1 + x)^4 = (1 + x)(1 = x)^3 = 1 + 4x + 6x^2 + 4x^3 + x^4
     (1 + x)^5 = (1 + x)(1 = x)^4 = 1 + 5x + 10x^2 + 10x^3 + 5x^4 + x^4

and so on.

3.2. Design

A top-down analysis of the proposed problem is given below.

We will store the current line in the Triangle in an unconstrained array and use this to build the following line. The start line array will comprise two elements: 1 and 1. We will use a recursive function to iterate through the levels in the triangle until level N is reached. Once we have established line N in the triangle we will use the resulting array of coefficients to expand the expression (1-x)^N for the appropriate value of N.

1. PASCALS_TRIANGLE (top level procedure): Input power N, check for power of 1 in which case direct output ((1+x)). Otherwise call PASC_TRIANG.

   NAME	USAGE	TYPE	RANGE
   POWER_N	Local variable	INTEGER	1.32

2. PASC_TRIANG (Level 2 procedure): Initiate expansion. Calls to CALCULATE_COEF and EXPANSION. Include type definition for LINE_ARRAY and initialisation of start line ({1, 1}).

   NAME	USAGE	TYPE	RANGE
   POWER	Formal parameter	INTEGER	Default
   START_LINE	Local constant (array)	LINE_ARRAY	{1, 1}
   COEFFICIENTS	Local variable (array)	LINE_ARRAY	n.a.

3. CALCULATE_COEF (level 2 function): Recur till appropriate line in triangle is arrived at. Call LINE_IN_TRIANGLE and self.

   NAME	USAGE	TYPE	RANGE
   CURRENT_LINE	Formal parameter (array)	LINE_ARRAY	n.a.
   LINE_LENGTH	Formal parameter	INTEGER	Default
   LINE_NUMBER	Formal parameter	INTEGER	Default
   NEXT_LINE	Local variable (array)	LINE_ARRAY	Default

4. EXPANSION (Level 2 procedure): Using identified line in triangle output expansion of expressions

   NAME	USAGE	TYPE	RANGE
   LINE_N	Formal parameter (array)	LINE_ARRAY	n.a.
   POWER	Formal parameter	INTEGER	Default

5. LINE_IN_TRIANGLE (Level 3 function): Calculate next line in triangle form current line and return next line.

   NAME	USAGE	TYPE	RANGE
   OLD_LINE	Formal parameter (array)	LINE_ARRAY	n.a.
   INDEX	Local variable	INTEGER	Default
   NEW_LINE	Local variable (array)	LINE_ARRAY	n.a.

Complete set of Nassi-Shneiderman charts for the above are given below:

A control flow chart indicating the flow of control through this sequence of procedures/functions is as follows.

3.3. Implementation

-- PASCALS TRIANGLE
-- 25 SEPTEMBER 1997
-- Frans Coenen
-- Dept Computer Science, University of Liverpool

with TEXT_IO;
use TEXT_IO;

procedure PASCALS_TRIANGLE is
    package INTEGER_INOUT is new INTEGER_IO(INTEGER);
    use INTEGER_INOUT;
    POWER_N : INTEGER range 1..32;

    --------------------------------------------------------------------------
    -- CALCULATE LINE OF COEFFICIENTS IN TRIANGLE, recursive function to
    -- determine appropriate line in triangle
    function CALCULATE_COEF(CURRENT_LINE : LINE_ARRAY; LINE_LENGTH,
                LINE_NUMBER : INTEGER) return LINE_ARRAY is
        NEXT_LINE : LINE_ARRAY(1..LINE_LENGTH+1);
        ----------------------------------------------------------------------
        -- CALCULATE NEXT LINE IN TRIANGLE
        function LINE_IN_TRIANGLE(OLD_LINE : LINE_ARRAY) return
                    LINE_ARRAY is
            INDEX    : INTEGER := 1;
            NEW_LINE : LINE_ARRAY(1..OLD_LINE'LENGTH+1) ;
        begin
            NEW_LINE(INDEX) := 1;
        -- Loop through previous line in triangle
            loop
                INDEX := INDEX + 1;
                NEW_LINE(INDEX) := OLD_LINE(INDEX-1) + OLD_LINE(INDEX);
                exit when OLD_LINE(INDEX) = 1;
            end loop;
            NEW_LINE(INDEX+1) := 1;
            RETURN(NEW_LINE);
        end LINE_IN_TRIANGLE ;
        ----------------------------------------------------------------------
    begin
        -- Base case
        if LINE_NUMBER = 1 then
        RETURN(CURRENT_LINE);
        -- Recursive step
        else
        NEXT_LINE := LINE_IN_TRIANGLE(CURRENT_LINE);
        RETURN(CALCULATE_COEF(NEXT_LINE,LINE_LENGTH+1,LINE_NUMBER-1));
        end if;
    end CALCULATE_COEF;
    --------------------------------------------------------------------------

    --------------------------------------------------------------------------
    -- EXPANSION, output
    procedure EXPANSION(LINE_N: LINE_ARRAY; POWER: INTEGER) is
    begin
        PUT("1 + ");
        PUT(LINE_N(2), WIDTH=>1);
        PUT("x");
    -- Loop through coefficients in line in triangle
        for LOOP_PARAMETER in 2..POWER-1 loop
            PUT(" + ");
            PUT(LINE_N(LOOP_PARAMETER+1), WIDTH=>1);
            PUT("x^");
            PUT(LOOP_PARAMETER, WIDTH=>1);
        end loop;
        PUT(" + x^");
        PUT(POWER,WIDTH=>1);
        NEW_LINE;
    end EXPANSION;
    ------------------------------------------------------------------------------

    ------------------------------------------------------------------------------
    -- PASC. TRIANG. - Commence expansion
    procedure PASC_TRIANG(POWER_N : INTEGER) is
        type LINE_ARRAY is array (INTEGER range <>)
                of INTEGER;
        START_LINE   : constant LINE_ARRAY(1..2) := (1, 1);
        COEFFICIENTS : LINE_ARRAY(1..POWER_N+1);
    begin
        COEFFICIENTS :=CALCULATE_COEF(START_LINE,2,POWER_N);
        EXPANSION(COEFFICIENTS,POWER_N);
    end PASC_TRIANG;
    ------------------------------------------------------------------------------

begin
-- Get input
    PUT_LINE("Input power (integer 1..32): ");
    GET(POWER_N);
-- If power 1 direct output
    if POWER_N = 1 then
    PUT_LINE("1 + x");
-- Otherwise determine coefficients and then output expansion
    else
    PASC_TRIANG(POWER_N);
    end if;
end PASCALS_TRIANGLE;

3.4. Testing

2.4.1. Black Box Testing

BVA, Limit and Arithmetic Testing Test input variable POWER_N using BVA analysis and limit testing. Test operation of arithmetic expression using (in this case) a positive sample value. A suitable set of test cases given in the table to the right.

2.4.2. White Box Testing

Path Testing: We should test each path through the code. The flow chart presented previously indicates 3 paths through the code (if we include the recursion). An appropriate pair of test cases is given in the following table, both of which have already been run as part of black box testing discussed above.

Loop Testing: We have three loops in the code (including the recursion). Loop testing theory dictates the following (where M is the maximum number of allowable passes):

1. Skip loop entirely
2. Only one pass through the loop
3. Two passes through the loop
4. M passes through the loop where M < N
5. N-1, N, N+1 passes through the loop

Test cases for the recursion, LINE_IN_TRIANGLE loop and EXPANSION loops are given in the following tables. Note that with respect to the recursion and the LINE_IN_TRIANGLE loop the loop is always exercised at least once.