LAB 7: ALGORITHMS
In this lab, you will practice implementing some algorithms as methods in Java. Each algorithm will apply rules, formulae or techniques appropriate for the problem to be solved. In some cases, you will be given an outline of the algorithm you have to implement. You will test each algorithm thoroughly to make sure that the algorithm has been implemented correctly.
Getting started
Create a new BlueJ project called lab7.
Add a new class AlgorithmTester to the project, and remove the sample code that BlueJ creates inside the class. This class will allow you to write and test some methods that implement
Task 1: Calculating a gas bill
An energy company computes its quarterly gas bills by taking the previous and present meter readings and applying the following rules:
the first 40 units used are charged at 30.52 pence per unit
the remainder of units are charged at 14.76 pence per unit
The following pseudocode represents an algorithm that performs this computation.
parameter current gas reading
parameter previous gas reading
unitsUsed = current – previous
if unitsUsed is less than or equal to 40
bill = unitsUsed * 52
else
bill = (40*30.52) + ((unitsUsed-40)*14.76
return bill
Add a method calculateGasBill to the class AlgorithmTester that calculates and returns the total gas bill amount. To help you on your way here are the first few lines of the method. The current and previous readings are parameters for the method. Inside the method we start by declaring any other variables needed. You should continue the coding from step 3 of the algorithm.
public double calculateGasBill(int current, int previous)
{
int unitsUsed; double bill;
Test your calculateGasBill method using the Code Pad or the Object Bench. Create a new instance of AlgorithmTester, and call calculateGasBill with values of 80 for current and 50 for previous. With these values, the number of units used will be 30, which is less than 40, so the first branch of the if statement will be executed, giving a value of 30 * 30.52 = 6.
Repeat the test with values for current and previous which give a number of units used greater than 40. Do the calculation manually to check that your algorithm is working. Which branch of the if statement will be executed here?
Task 2: Calculating a factorial
The factorial of a number, written n! (e.g. 6! Or 12!), is the product of all integers from 1 to that number. For example 6! (the factorial of 6) is 1*2*3*4*5*6 = 720. You can think of this as the mathematical formula for calculateing a factorial.
Add a method calculateFactorial to the class AlgorithmTester that calculates and returns the factorial of a specified
To help you on your way here is the code for a similar example method which does a slightly different calculation – this one calculates the sum of all integers up to a specified number. The specified number is the parameter. The variable sum is used to keep track of the sum as the calculation progresses, and a for loop is used to repeatedly add each integer up to the specified number:
public int calculateSum(int number)
{
int sum = 0;
for (int i=0; i<=number; i++)
{
sum = sum + i;
}
return sum;
}
You should think about the following when writing the factorial method:
What initial value should be assigned?
What range of values of number should be used in the for loop?
Test your calculateFactorial method using the Code Pad or the Object Bench. Create a new instance of AlgorithmTester, and call calculateFactorial with a parameter value of 6 –the result should be 720.
Repeat the test for a value of 10 – calculate the result manually so that you can be sure your algorithm is working correctly. Beware of testing it with larger numbers as the values of factorials increase
Task 3: Reversing an array
A method is needed to reverse the order of an array of numbers. The method should return the reversed array.
The algorithm for this will make use of the technique of swapping the first and last items, then the second and second last items, and so on. For example, to reverse the array
{1,2,3,4,5,6} the steps would be:
{1,2,3,4,5,6} -> {6,2,3,4,5,1}
{6,2,3,4,5,1} -> {6,5,3,4,2,1}
{6,5,3,4,2,1} -> {6,5,4,3,2,1}
After 3 steps, this array of length 6 is completely reversed. You only need to step through the elements in the first half of the array, and swap each with the one an equivalent distance from the end of the array – element 0 swaps with element 6, element 1 swaps with element 5, and so on.
You can do this with a for loop, and pseudocode for the algorithm might be as follows:
parameter array
temp = 0
last = index of last element in the array
for i in indexes for the first half of the array
temp = array[i]
array[i] = array[index to swap with index i]
array[index to swap with index i] = temp
return array
Swapping is a common action in many algorithms, and is done by the three lines inside the for loop. Note that a temporary variable is needed – the first item to be swapped is copied to temp, then the last item overwrites the first, and finally the temporary copy of the first item overwrites the last.
Add a method reverseArray to the class AlgorithmTester that reverses an array of integers and returns the reversed array. The method should have return type and parameter as follows:
public int[] reverseArray(int[] array)
You should continue the coding from step 2 of the algorithm. You will need to think particularly carefully about the expressions needed to implement the parts shown in italics in the pseudocode.
Test your reverseArray method using the Code Pad or Object Bench. Create a new instance of AlgorithmTester, and evaluate an expression which calls reverseArray with a parameter that is the array {1,2,3,4,5,6} – as shown above the result should be {6,5,4,3,2,1}.
Note that you can pass an array as a parameter in code (e.g. in the Code Pad) as follows by evaluating an expression like this (assuming alg is an instance of AlgorithmTester):
alg.reverseArray(new int[]{1,2,3,4,5,6})
When you call the method from the Object Bench you can actually write the parameter more simply, as shown below:
Repeat the test for an array with an odd number of elements, for example
{1,2,3,4,5} – does your method deal correctly with both even and odd length arrays. You may need to think about what how the steps would differ from the example above in the case of an odd length array.
Task 4: Calculating shipping cost
A method is needed to calculate the cost of purchasing an item online, including the cost of shipping. Shipping cost is calculated using the following rules:
Shipping is charged at a fixed price of £5.00 unless the customer has subscribed to a reduced-cost shipping offer, in which case it is charged at 3% of the basic item
Shipping is free for all items which cost more than £100.
The item cost and the customer’s reduced-cost shipping status (true or false) are the parameters for the method. The method should return the total cost of the purchase.
Add a method calculateCostWithShipping to the class AlgorithmTester that calculates and returns the total cost of an item including shipping. All costs should be represented as values of type double. The method should have return type and parameters as follows:
public double calculateCostWithShipping(double itemCost, boolean reducedShipping)
You need to devise the algorithm to implement the specified rules. It may help to write out your algorithm in pseudocode before you try to implement it in Java.
Test your calculateCostWithShipping method using the Code Pad or the Object Bench. Create a new instance of AlgorithmTester, and call calculateCostWithShipping with values of 60.0 for itemCost and true for reduced. With these values, the customer should be charged 3% of the item cost for shipping, making the total cost = 8.
Repeat the test with values for itemCost and previous to check that the rules above have all been implemented fully so that you can be confident your method gives the correct result for all possible situations. How many tests will you need for this?
Writing a program to calculate shipping cost:
Add a new class Program to your project, and remove the code inside the class created
Implement a main method within this class to create a program that uses the calculateCostWithShipping method of your AlgorithmTester The program should prompt the user for the following input:
the basic cost of the item to be shipped
whether or not the user has reduced-cost shipping
It should then output a suitable formatted message informing the user of the total cost with shipping.
Note that your main method will need to create an instance of AlgorithmTester and call its calculateCostWithShipping method to do the actual calculation, passing in the appropriate parameter values. Don’t write code in the main method to do that calculation, the main method should just handle input and output, and create and use an object to do the hard work.
To get user input from the terminal you can use the class Scanner. You will need to import the class java.util.Scanner in your Program class. To get input you can instantiate a Scanner object and call the nextLine method of Scanner to read the data that the user enters in the terminal. The following code shows and example of inputting an integer and a string. You will need to think about the type of input you need to get from the user, and how to turn this into appropriate parameter values for the call to calculateCostWithShipping.
import java.util.Scanner;
public class ScannerExample{
public static void main(String[] args)
{
Scanner reader = new Scanner(System.in);
System.out.println("Please enter an integer and a string");
String input = reader.nextLine(); int myInt = Integer.parseInt(input); String myString = reader.nextLine();
System.out.format("The values you entered were %d and
%s\n", myInt, myString);
}
}
Run your program by right-clicking on the Program class in the BlueJ class diagram and selecting the main Enter input corresponding to one of your test cases in steps 2 or 3 above, and check that the output is as you expect.
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of