Higher – Find Maximum and Find Minimum Standard Algorithms

We spent a lot of last week on Standard Algorithms, most of them have the structure of an IF inside a FOR loop. While it is possible to use a FOR EACH loop this would mean that we could not know what the position was of the value we were searching for. In the examples below the returned value (max or min) could be changed to the position to allow this to be used elsewhere in the program.

To find the largest number in an array we would use the “Find Maximum” algorithm

def findMax(numbers):
    # Find biggest number
    max=numbers[0]
    for counter in range(1,len(numbers)):
        if numbers[counter]>max:
            max=numbers[counter]
            #position=counter
    return max

To find the smallest number in an array we would use the “Find Minimum” algorithm

def findMin(numbers):
    #Find smallest number
    min=numbers[0]
    for counter in range(1,len(numbers)):
        if numbers[counter]<min:
            min=numbers[counter]
            #position=counter
    return min

Notice that both of these functions are very similar with only the operator changing. Did you also notice that the for loop starts from index 1? Why do you think this is?

Higher – Linear Search Standard Algorithm

A linear search is used to check if a value is in an array. There are two ways of doing this:-

Check every value in the list, even if you find the value immediatly.


def linSearchV1(target,numbers):
    #Search for target in all of the numbers
    found=False
    for counter in range(len(numbers)):
        if numbers[counter]==target:
            found=True
    return found

Check until you find the value you are looking for, this is much more effient and can on average half the ammount of time taken for the program to run.


def linSearchV2(target,numbers):   
    #Search for the target numbers until it is found
    counter=0
    found=False
    while not found and counter!=len(numbers):
        if numbers[counter]==target:
            found=True
        else:
            counter=counter+1
    return found

The same algorithms can be used to find a string in an array of strings or a character in a string.

Higher – Random Number Array Function

The class was asked to create a function that generated 100 number dice throws and stored them in an array.

This function is used to create an array of random integers. The size of the array and the magnatude of the values is set when the function is called.


def randomNumbers(size,min,max):
    # creates an array of (size) random numbers between min and max
    import random
    numbers=[]
    for loop in range(size):
        numbers.append(random.randint(min,max))
    return numbers

rndNumbers=randomNumbers(100,1,6)

Higher – Substring Operations

pre-defined functions (with parameters):

  • to create substrings

In Python we can treat strings as arrays of characters. We do this by using

string[start:stop:step]

where

  • start is the postion of the first character to be displayed.
  • stop is the postion to stop displaying characters (not displayed).
  • step is the step value, just like a for loop.

Read more

N5 – Input Validation

Today we looked at the following problem

Write a program which will allow a user to input only a number in the range 0-100. An error message will be output if the number is invalid.

The program will output a message when the number input is valid (after the loop for checking the number).

We then worked through Analysis, Design, Implementation and Testing of the program.

Analysis

Input – a number

Process – check number is between 0 and 100

Output – a message about the numbers validity

Design

We looked at all three design methodologies and created designs in our jotter.

Pseudocode

  1. Declare Integer Number
  2. Get Number from user
  3. While Number < 0 OR Number > 100
  4.     Display “Sorry that number is not valid”
  5.     Get number from user
  6. End While
  7. Display “That is a valid number”

Flowchart

Structure Diagram

Implementation in Python


number=0 # declare number as type integer
number = int(input("Please enter a number from 0 - 100 "))
while number < 0 or number > 100:
    print("Sorry that number is not valid")
    number = int(input("Please enter a number from 0 - 100 "))
print("That is a valid number")

Testing

We tested the code with Normal, Extreme and Exceptional test data.

N5 – Input Process Output

Leading on from the work we did last term and this week. We created a program to solve the calorie counter problem.

Analysis

Inputs

  • calories in porridge
  • calories in toast
  • calories in marmalde
  • calories in coffee

Process

  • add all calories and store in total

Output

  • The total number of calories in breakfast

Design

  1. Get the number of calories in porridge
  2. Get the number of calories in of toast
  3. Get the number of calories in of marmalade
  4. Get the number of calories in of coffee
  5. Total = Porridge + toast + marmalade + coffee
  6. Display the total number of calories