Laboratory 13 Solutions

Lesson 13-2

Exercise 1

Exercise 2

Exercise 3

Exercise 4

Exercise 5

Exercise 6

Lesson 13-3

Exercise 1

Exercise 2

Exercise 3

Exercise 4

Exercise 5

Exercise 6

Exercise 7

Exercise 8

Exercise 9

Lesson 13-4

Exercise 1

Lesson 13-2

Exercise 1:

The following is the base case.

if ( exp == 0 )
return 1;

Exercise 2:

The following is the recursive case.

else
return num * power(num, exp-1);

Exercise 3:

The following is the complete application.

// Application Power calculates and prints an
// integer value raised to an integer power
public class Power
{
static int power(int num, int exp)
{
if ( exp == 0 )
/* TO BE FILLED IN: Exercise 1 */
return 1;
else
/* TO BE FILLED IN: Exercise 2 */
return num * power(num, exp-1);
}
public static void main(String[] args)
{
System.out.println("3 to the 4th power is " +
power(3,4));
System.out.println("4 to the 3rd power is " +
power(4,3));
System.out.println("10 to the 5th power is " +
power(10, 5));
}
}

The following is printed:

3 to the 4th power is 81
4 to the 3rd power is 64
10 to the 5th power is 100000

Exercise 4:

The following is the base case.

if ((n==0)||(n==1))
return n;

The following is the recursive (general) case.

else
return fib(n-1) + fib(n-2);

Exercise 5:

The following is an example of method ‘fib’.

public static long fib( long n )
{
if ((n==0)||(n==1)) // Base case
return n;
else // Recursive calls
return fib(n-1) + fib(n-2);
}

Exercise 6:

The following is an example application.

public class Fibonacci
{
public static void main( String[] args )
{
System.out.println( "fib(5) = " + fib(5) );
System.out.println( "fib(5) = " + fib(10) );
System.out.println( "fib(5) = " + fib(20) );
}
public static long fib( long n )
{
if ((n==0)||(n==1)) // Base case
return n;
else // Recursive calls
return fib(n-1) + fib(n-2);
}
}

The following is printed:

fib(5) = 5
fib(5) = 55
fib(5) = 6765

Lesson 13-3

Exercise 1:

The following is the method ‘printList’.

Exercise 2:

The following is the method ‘print’.

void print(int first, int last)
{
// TO BE FILLED IN: Exercise 2
if ( first < last )
{
System.out.println( "value[" + first + "] = " + values[first] );
print( first + 1, last);
}
}

Exercise 3:

Note: The class List has an error: the constructor name is wrong.

The following is a sample of the corrected and completed class List.

public class List
{
// Methods
public void store(int item)
// Pre: The list is not full
// Post: item is in the list
{
values[numItems] = item;
numItems++;
}

public void printList()
// Post: If the list is not empty, the elements are
// printed on the screen; otherwise "The list
// is empty" is printed on the screen
{
// TO BE FILLED IN: Exercise 1
if ( numItems > 0 )
print( 0, numItems );
else
System.out.println( "List is empty!" );
}
void print(int first, int last)
{
// TO BE FILLED IN: Exercise 2
if ( first < last )
{
System.out.println( "value[" + first + "] = " + values[first] );
print( first + 1, last);
}
}
public List(int maxItems)
// Constructor
// Post: Empty list is created with maxItems cells
{
numItems = 0;
values = new int[maxItems];
}
// Data fields
private int numItems;
private int[] values;
}

The following is the driver.

import java.util.Scanner;
import java.io.*;
public class ListDriver
{
public static void main(String[] args) throws IOException
{
Scanner inFile = new Scanner(new FileReader("int.dat"));
List list = new List(20);
while (inFile.hasNextInt())
list.store(inFile.nextInt());
list.printList();
}
}

The following is printed.

value[0] = 10
value[1] = 20
value[2] = 30
value[3] = 40
value[4] = 50
value[5] = 60
value[6] = 70
value[7] = 80
value[8] = 90
value[9] = 100

Exercise 4:

The following is the recursive method ‘print’.

void print( Node list )
{
// TO BE FILLED IN: Exercise 4
if ( list != null )
{
System.out.println( list.getItem() );
print( list.getNext() );
}
}

Exercise 5:

The following is the method ‘printList’.

public void printList()
{
// TO BE FILLED IN: Exercise 5
if ( numItems > 0 )
print( listPtr );
else
System.out.println( "List is empty!" );
}

Exercise 6:

The following is a sample class LinkedList.

public class LinkedList
{
int numItems;
Node listPtr;
public LinkedList()
{
numItems = 0;
listPtr = null;
}
public void insert(String newItem)
{
numItems++;
Node currentPtr = listPtr;
Node prevPtr = null;
Node newNode = new Node(newItem);
if (listPtr == null)
listPtr = newNode;
else
{
while (currentPtr != null &
currentPtr.getItem().compareTo(newItem) < 0)
{
prevPtr = currentPtr;
currentPtr = currentPtr.getNext();
}
if (prevPtr == null) // First item
{
newNode.setNext(listPtr);
listPtr = newNode;
}
else
{
newNode.setNext(prevPtr.getNext());
prevPtr.setNext(newNode);
}
}
}
void print( Node list )
{
// TO BE FILLED IN: Exercise 4
if ( list != null )
{
System.out.println( list.getItem() );
print( list.getNext() );
}
}
public void printList()
{
// TO BE FILLED IN: Exercise 5
if ( numItems > 0 )
print( listPtr );
else
System.out.println( "List is empty!" );
}
}

The following is the driver.

import java.util.Scanner;
import java.io.*;
public class UseLinked
{
public static void main(String[] args) throws IOException
{
Scanner inData = new Scanner(new FileReader("Linked.dat"));
LinkedList list = new LinkedList();
while (inData.hasNextLine())
{
String newItem = inData.nextLine();
list.insert(newItem);
}
list.printList();
}
}

The following is printed.

blue
blue
green
green
orange
red
white

Exercise 7:

Modify method ‘print’ as follows.

void print( Node list ) // Prints in reverse order
{
// TO BE FILLED IN: Exercise 7
if ( list != null ) //first < (numItems-1))
{
print( list.getNext() );
System.out.println( list.getItem());
}
}

The following is now printed.

white
red
orange
green
green
blue
blue

Exercise 8:

The following is a sample recursive method that returns the position of a given value in a list.

public int getPositionOfValue(int first, int value )
{
if ( values[first] == value ) // Base case. Value found.
return first;
else if ( first < numItems ) // Recursive case.
return getPositionOfValue( first + 1, value );
else
return -1; // Value not found.
}

Exercise 9:

The following is the list driver with added calls to the new method.

list.getPositionOfValue( 0, 10 ) );
System.out.println( "Position of value 40: " +

list.getPositionOfValue( 0, 40 ) );
System.out.println( "Position of value 80: " +

list.getPositionOfValue( 0, 80 ) );
System.out.println( "Position of value 100: " +

list.getPositionOfValue( 0, 100 ) );
System.out.println( "Position of value 25: " +

list.getPositionOfValue( 0, 25 ) );
System.out.println( "Position of value 99: " +

list.getPositionOfValue( 0, 99 ) );
}
}

The following will be printed.

value[0] = 10
value[1] = 20
value[2] = 30
value[3] = 40
value[4] = 50
value[5] = 60
value[6] = 70
value[7] = 80
value[8] = 90
value[9] = 100
Position of value 10: 0
Position of value 40: 3
Position of value 80: 7
Position of value 100: 9
Position of value 25: -1
Position of value 99: -1

Lesson 13-4

Exercise 1:

The following is the corrected SumTest program.

public class SumTest
{
static Scanner inFile;
static int sum(Scanner inFile) throws IOException
{
if (inFile.hasNextInt())
return inFile.nextInt() + sum(inFile);
return 0; //added
}
public static void main(String[] args) throws IOException
{
inFile = new Scanner(new FileReader("int.dat"));
//System.out.println(sum()); //error; argument is missing
System.out.println(sum( inFile ));//corrected; argument 'inFile'

//added
}
}

The output is

550