Introduction to solving complex problems
Hide30 comments
So far we’ve looked at solving simple problems using conditional and looping constructs. But what if there is a complex problem where a combination of conditional and looping constructs have to be used? Or, multiple conditions and multiple looping constructs have to be used? In this tutorial we’ll cover how to tackle some of these problems by applying what you have learnt so far in the course.
Consider a grading system with four different grades: A, B, C and D - where A is the highest grade and D the lowest. The system of grades is defined as shown below:
| Grade | Marks |
|---|---|
| A | marks > 75 |
| B | 50 < marks <= 75 |
| C | 35 < marks <= 50 |
| D | marks <= 35 |
The algorithm to determine the grade when a mark is given should go something like this:
- Line 1: Begin
- Line 2: Check marks
- Line 3: If mark is greater than 75 then Grade A
- Line 4: Otherwise,
- Line 5: if mark is greater than 50 but less than or equal to 75, then Grade = B
- Line 6: Otherwise,
- Line 7: if mark is greater than 35 but less than or equal to 50, then Grade = C
- Line 8: Otherwise, Grade = D
- Line 9: End
This algorithm has several conditional statements. First it needs to be checked whether the mark is greater than 75. If the mark is not greater than 75, there are many possibilities. So there are two more conditional checks within the ‘Otherwise’ part of the first conditional statement. Because these conditional statements are inside one another they are described as ‘nested’ conditions.
Implementing this in a Java program using ‘if’ statements would look like this:
int mark;
String Grade;
if ( mark > 75 )
Grade = "A";
else {
if ( (mark <= 75) && (mark > 50) )
Grade = "B"; /*in the above condition you do not need to check (mark <= 75) as we only get to this point if it is so. We have shown it here for clarification*/
else {
if ( (mark <= 50) && (mark > 35) )
Grade = "C"; /*similar to previous condition check we do not need (mark<= 50) here as execution gets here only if that is true*/
else
Grade = "D";
}
}
Now can you improve this program to check whether the value of ‘mark’ is non-negative? Not greater than 100?
To check the non-negativity you will have to add an additional condition
if ( mark >= 0 )
To check whether the mark is less than 100 you will have to add another condition
if ( mark < 100 )
But if you want to make sure the mark is non-negative AND less than 100 you can use this condition:
if ( ( mark >= 0 ) && ( mark < 100 ) )Nested looping
Here’s an example of nested looping: Suppose we have the marks for a class of four students and we want to sort these into ascending order. An algorithm can be used to design a program to do this.
First, you need to identify the steps required to rearrange the marks into ascending order.
The array, representing the marks of the four students, should start out like this:
| 0 | 70 |
| 1 | 60 |
| 2 | 26 |
| 3 | 9 |
After sorting the elements into ascending order the array should look like this:
| 0 | 9 |
| 1 | 26 |
| 2 | 60 |
| 3 | 70 |
Pass 1:
| 0 | 70 |
| 1 | 60 |
| 2 | 26 |
| 3 | 9 |
Step 1: Compare the element at index 0 with element at index 1 (in this example 70 and 60). Then swap them over to sort the two values in ascending order.
| 0 | 60 |
| 1 | 70 |
| 2 | 26 |
| 3 | 9 |
Step 2: Compare the element at index 1 and index 2. That is 70 and 26. Now switch them around.
| 0 | 60 |
| 1 | 26 |
| 2 | 70 |
| 3 | 9 |
Step 3: The element at index 2 is compared with element at index 3. That is 70 and 9. Because 70 is greater than 9 you will have to swap them over.
| 0 | 60 |
| 1 | 26 |
| 2 | 9 |
| 3 | 70 |
At this point the largest value of all has reached its correct position. So in the next pass you don’t need to compare the last element.
Pass 2:
| 0 | 60 |
| 1 | 26 |
| 2 | 9 |
| 3 | 70 |
Step 1: Compare the element at index 0 with the element at index 1; 60 and 26 and swap them over.
| 0 | 26 |
| 1 | 60 |
| 2 | 9 |
| 3 | 70 |
Step 2: The next comparison is between the element at index 1 and the element at index 2; 60 and 9. Swapping is done to achieve ascending order.
| 0 | 26 |
| 1 | 9 |
| 2 | 60 |
| 3 | 70 |
At this point the next largest value (60) has also reached its correct place in the sequence.
Pass 3:
| 0 | 26 |
| 1 | 9 |
| 2 | 60 |
| 3 | 70 |
Step 1: the elements at index 0 and 1 ( 26 and 9 respectively) are compared and swapped.
| 0 | 9 |
| 1 | 26 |
| 2 | 60 |
| 3 | 70 |
The marks are now arranged in ascending order, so no more swapping is required.
Implementing nested looping
Two loops (nested loops) can be used to implement this program.
First, these values need to be stored in the program. The marks are whole numbers between 0 and 100, so you can choose from
short, int orbyte as the data type. The byte data type requires the least memory and, as it is sufficient to store this range of numbers, it would be the best choice here.
Four separate variables could be used to store this data, but this would be cumbersome. Because this data is of the same type, a single array can be used to store all of the marks. This would also allow this particular program to be easily reused for classes of different sizes.
‘n’ number of elements will be needed in the array where the ‘n’ is equal to the number of students. A byte array called
myArray can be used to hold these values:for (int index1 = 0; index1 < 3 ; index1++) {
for (int index2 = 0; index2 + index1 < 3 ; index2++){
if ( myArray[index2] > myArray [index2+1]){
/*this means we need to swap the two elements*/
byte tempValue = myArray[index2];
/*store myArray[index2] in tempValue variable*/
myArray[index2] = myArray[index2+1];
/*assign myArray[index2+1] value to myArray[index2]*/
myArray[index2+1] = tempValue;
/*now assign myArray[index2]’s original value that was temporarily stored in tempValue to myArray[index2+1]*/
}/*end of if section*/
}/*end of for with index2*/
}/*end of for with index1*/
Pass 1:
index1 = 0 (Throughout Pass 1, index1 is equal to ‘0’)index2 = 0| 0 | 60 |
| 1 | 70 |
| 2 | 26 |
| 3 | 9 |
index2 = 1| 0 | 60 |
| 1 | 26 |
| 2 | 70 |
| 3 | 9 |
index2 = 2| 0 | 60 |
| 1 | 26 |
| 2 | 9 |
| 3 | 70 |
Pass 2:
index1 = 1 (Throughout Pass 2, index1 is equal to 1)index2 = 0| 0 | 26 |
| 1 | 60 |
| 2 | 9 |
| 3 | 70 |
index2 = 1| 0 | 26 |
| 1 | 9 |
| 2 | 60 |
| 3 | 70 |
Pass 3:
index1 = 2index2 = 0| 0 | 9 |
| 1 | 26 |
| 2 | 60 |
| 3 | 70 |
The program has finished executing and the marks are now in ascending order. By creating an algorithm first each of the steps that were required to sort the marks into ascending order could be identified and a program could be created that performed these steps.
This sorting problem uses two nested
for loops. It also has a conditional statement within a loop. These constructs can be used in a wide range of combinations to solve different types of programming problems.
When you use nested constructs it is a lot easier to make mistakes. When programs are not producing the desired output, you can use a debugger to check through the code to find where it is going wrong.
