INTRODUCTION TO PROGRAMMING IN JAVA: REPETITION (MORE ON FOR LOOPS)

NOTE: This set of www pages is not the set of www pages for the curent version of COMP101. The pages are from a previous version that, at the request of students, I have kept on line.

1. Processing a loop "in reverse"
2. Example problem - Factorial

3. Example problem - Extended factorial application

The first (Factorial) example problem gives another illustration of a variable count pre-test loop using a "for" construct. The example also: (1) includes an error recovery mechanism using an "if-else" construct as illustrated previously, and (2) uses data items of type long (first time such data items are used in this sequence of WWW pages).

1. PROCESSING A LOOP "IN REVERSE"

It is sometimes desirable to process a fixed count loop backwards, i.e. in reverse. In some programming languages (such as Ada and Pascal) this requires the inclusion of a reserved word such as reverse in the loop definition. In Java (and languages such as C and C++) this is not necessary because of the greater versatility of the for loop construct. All we need to do is decrement the loop parameter instead of the more usual incrementation. For example the code in Table 1 would produce the output:

10 9 8 7 6 5 4 3 2 1

// SEQUENCE NUMBERS CLASS
// Frans Coenen
// Tuesday 13 April 1999
// The University of Liverpool, UK
   
class SequenceNumbers { 

    // ------------------ METHODS -----------------------
    
    /* Main method  */

    public static void main(String[] args) {
	final int START_CONDITION = 10;
	final int END_CONDITION   = 0;
	
	// For loop
	
	for (int loopParameter = START_CONDITION;loopParameter > END_CONDITION;
							loopParameter--) 
		System.out.print(loopParameter + " ");
	
	// End
	
	System.out.println("\n");
	}
    }

Table 1: Sequence of numbers output in "reverse"

2. EXAMPLE PROBLEM - FACTORIAL

2.1 Requirements

Design and implement a Java program that returns the value of N! (N Factorial) given a specific value for N. Note:

n! = n x (n-1) x (n-2) ... 3 x 2 x 1

For example:

10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3628800

Assume that the minimum permissible value for N is 1, and the maximum permissible value is 20.

2.2 Analysis

To produce a solution to factorial N! we loop over N iterations adding multiplying the loop counter by the product obtained so far starting with a product value of 1.

A class diagram for the proposed solution is given in Figure 1. Two classes are proposed. A general class Factorial, and an application class FactorialApp.

Note that we define the product field to be of type long because !20 = 2432902008176640000, which is greater than the maximum value permitted for a data item of type int (Integer.MAXIMUM = 2147483647).

2.3 Design

2.3.1 `Factorial` Class

Figure 1: Factorial class diagram

Class comprises: two private instance fields numberOfTerms and product, a constructor and two instance methods as follows.

1. Factorial: Constructor to create an instance of the class Factorial given a number of terms.

Field Summary
`private long`	`numberOfTerms` An instance field to store the number of required terms in the factorial sequence.
`private long`	`product` An instance field to store the total derived from multiplying the terms in the sequence.

Constructor Summary

Factorial(long numTerms)
Constructor to create an instance of the class Factorial given a number of terms.

Method Summary
`public long`	`getProduct()` Trivial "get" method to return the value of a given factorial.
`public void`	`factorialN()` Method to carry out the actual calculation.

A Nassi-Shneiderman chart for the above methods is given in Figure 2.

NASSI-SHNEIDERMAN CHART FOR FACTORIAL CLASS

Figure 2: Nassi-Shneiderman charts for Factorial class

2.3.2 `FactorialApp` Class

Field Summary
`private static Scanner`	`input` A class instance to facilitate input from the input stream.

Method Summary
`public static void`	`main(String[] args)` Main method. Calls `inputNumTerms` to input number of terms, and then creates an instance of the class `Factorial`. The actual calculation is achieved through a call to the `FactorialN` instance method defined in the `Factorial` class, after which the result is output.
`private static long`	`inputNumTerms()` Method to allow user to input the required number of terms. This must be an integer between 1 and 20 inclusive. Note that the value of 20! is such that we must use a long integer type to store it. The method includes an error recovery mechanism in the event of an erroneous input.

A Nassi-Shneiderman chart for the above is presented in Figure 3, and a control flow chart to assist in path testing in Figure 4.

NASSI-SHNEIDERMAN CHART FOR FACTORIAL
APPLICATION CLASS

Figure 3: Nassi-Shneiderman charts for FactorialApp class methods

Figure 4: Control flow diagram for factorial application

2.4. Implementation

The encoding of the above is given in Tables 2 and 3:

2.4.1 `Factorial` Class

// FACTORIAL CLASS
// Frans Coenen
// Tuesday 13 April 1999
// The University of Liverpool, UK

/*********************************************/
/*                                           */
/*               PROGRESSION                 */
/*                                           */
/*********************************************/

class Factorial {

    // ------------------ FIELDS ----------------------

    private long numberOfTerms;
    private long product;
    
    // ----------------- CONSTRUCTORS -----------------
    
    /** Factorial constructor */
    
    public Factorial(long numTerms) {
    	numberOfTerms = numTerms;
	}
	
    // ------------------ METHODS ---------------------
    
    /** Get product */
    
    public long getProduct() {
        return(product);
	}
    
    /** Calculate factorial N */
    
    public void factorialN() {
	final long startCondition = 1;
	
	// Initial value for product
	product = 1;
	
	// Loop
	for(long loopParameter = startCondition; loopParameter <=
	numberOfTerms;loopParameter++) 
	    product = product*loopParameter;
	}    			
    }

Table 2: Implementation for factorial class

Notes:

The above is somewhat contrived for the benefit of giving an illustration of a for loop where the loop parameter is decremented. The same result could be achieved using "normal" incrementation thus:
```
for(loopParameter = 1; loopParameter <= numberTerms;loopParameter++) 
    product = product*loopParameter;
```

2.4.2 `FactorialApp` Class

// Frans Coenen
// Tuesday 13 April 1999
// Revised: Thursday 28 July 2005
// The University of Liverpool, UK
   
import java.util.*;
   
class FactorialApp { 
  
    // ------------------- FIELDS ------------------------ 
                      
    // Create Scanner class instance

    private static Scanner input = new Scanner(System.in);
     
    // ------------------ METHODDS -----------------------
    
    /* Main method  */

    public static void main(String[] args) {
	// Input
	long numTerms = inputNumTerms();
	
	// Create instance of class Factorial
	Factorial newFactorial = new Factorial(numTerms);
	
	// Calculate
	newFactorial.factorialN();
	
	// Output
	System.out.println(numTerms + "! = " + newFactorial.getProduct());
	}

    /* Input number of terms */
    
    private static long inputNumTerms() {
        final long maxTerms = 23;
	final long minTerms = 1;
	
	// Input	
	System.out.println("Input Number of terms (long " + minTerms + ".." +
		maxTerms + "): ");
	long numTerms = input.nextLong(); 
	
	// Check input	
	if (numTerms > maxTerms || numTerms < minTerms) {
	    System.out.println("ERROR 1: Number of terms must be between the limits " +
	    	minTerms + " and " + maxTerms);
	    return(inputNumTerms());	
	    }
	else return(numTerms);    
        }
    }

Table 3: Implementation for factorial application

2.4. Testing

2.4.1 Black box testing

BVA, Limit and Arithmetic Testing. A suitable set of test cases is given in Table 4.

TEST CASE	EXPECTED RESULT
numTerms	OUTPUT
0	ERROR
1	1
2	2
10	3628800
19	121645100408832000
20	2432902008176640000
21	ERROR

Table 4: BVA, limit and arithmetic test cases

2.4.2 White box testing

Loop testing. Test repetitions in variable count loop using set of test cases of the form given in Table 5. Note that all these have already been proposed as either BVA, limit or arithmetic test cases (see above).

Path testing. Also path testing comprised of both BVA and limit test cases.

TEST CASE	EXPECTED RESULT
numTerms	OUTPUT
0 (start value -1: no passes)	Error
1 (start value: one pass)	1
2 (start value +1: two passes)	2
10 (somewhere in the middle)	3628800
19 (end value -1 passes)	121645100408832000
20 (end value passes)	2432902008176640000
21 (end value +1 passes)	Error

Table 5: Loop test cases

3. EXAMPLE PROBLEM --- EXTENDED FACTORIAL APPLICATION

3.1 Requirements

Produce a Java program that outputs the values of 1! to 20! inclusive.

3.2 Analysis

We can make use of the Factorial class defined in the foregoing section, we therefore only need an appropriate application class, (say) FactiorialExtApp, which would only need one method (main).

3.3 Design

3.3.1 `FactorialExtApp` Class

Method Summary
`public static void`	`main(String[] args)` Top level method. Contains a (fixed count) for loop which loops through from 1 to 20. On each iteration a new instance of the `Factorial` class is created, and then the actual calculation is achieved through a call to the `FactorialN` instance method defined in the `Factorial` class, after which the result is output.

A Nassi-Shneiderman chart for the above is presented in Figure 5.

3.4. Implementation

The encoding of the above is given in Tables 6.

NASSI-SHNEIDERMAN CHART FOR FACTORIAL
EXTENDED APPLICATION CLASS

Figure 5: Nassi-Shneiderman charts for FactorialExtApp class method

// FACTORIAL EXTENDED APPLICATION CLASS
// Frans Coenen
// Wednesday 14 April 1999
// Revised: Thursday 28 July 2005
// The University of Liverpool, UK
   
class FactorialExtApp { 
   
    // ------------------ METHODDS -----------------------
    
    /** Main method  */

    public static void main(String[] args) {
	final int startValue = 1;
	final int endCondition = 20;
	Factorial newFactorial;
	
	// Lopp to output series of factorials
	
	for(long loopParameter = startValue;loopParameter <= endCondition;
	                                               loopParameter++) {
	    System.out.print(loopParameter + "! = ");
	    newFactorial = new Factorial(loopParameter);
	    newFactorial.factorialN();
	    System.out.println(newFactorial.getProduct());
            }
	    
	// End
	
	System.out.println("\n");
	}
    }

Table 6: Implementation for factorial application

3.4. Testing

Given that there is no input there is no testing that can be undertaken other than a simple "test run". The results of such a run are presented in Table 7.

Note that, from the sample output given in Table 7, we can see that using an int to store our product would mean that we could not calculate factorials beyond !13 (Integer.MAXIMUM = 2147483647).

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000

Table 7: Output from extended factorial application program

Created and maintained by Frans Coenen. Last updated 10 February 2015