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.
- 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 - 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. - 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 - 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 - 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. - 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}).
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;