3.9: Algorithms & Flowcharts Hacks

Consider this situation:

  • You're playing a short game using a random number generator from 1 to 20

  • On each turn, a player will generate 3 random numbers

  • They get to keep the highest number that they generate as their score

Your TASK:

  1. Create a flowchart that can be used to write an algorithm that calculates a player's score after a turn

    • NOTE: Don't forget the syntax for Flowcharts! (each shape represents an action)

    • Try to implement selection and/or iteration in your algorithm

    • Please do this using Google Drawing. It can be found in your Google Drive if you click New > More > Google Drawings

  2. Write the working algorithm in Python

    • Make sure to initialize / define any variables you may need

    • Add comments to your code!

import random # import random numbers

numList = [] # create an empty list to be filled with the randomly generated numbers
score = 0 # create a variable score, and set it equal to 0

number1, number2, number3 = random.sample(range(1,20), 3) # take a random sample of 3 numbers out of a range of 1-20, and set each of those 3 numbers equal to one of the 3 variables
numList.extend([str(number1), str(number2), str(number3)]) # use the 3 variables assigned to the 3 randomly generated numbers to fill the once empty list numList

for i in numList: # iterate through numList
    score = (max(map(int, numList))) # search for the highest number in numList, and once it is found assign it to the variable "score"

print("Your random numbers are " + str(number1) + ", " + str(number2) + ", and " + str(number3) + ". Your score is equivalent to your highest number: " + str(score)) # print the list of 3 random numbers and indicate the score)

Your random numbers are 19, 2, and 14. Your score is equivalent to your highest number: 19

3.11: Binary Search Hacks

Using my example above and steps below, create your own iteration using binary search

Steps

  1. Compare x with the middle element.
  2. If x matches with the middle element, we return the mid index.
  3. Else if x is greater than the mid element, then x can only lie in the right (greater) half subarray after the mid element. Then we apply the algorithm again for the right half.
  4. Else if x is smaller, the target x must lie in the left (lower) half. So we apply the algorithm for the left half.
def binarySearch(array, x):
    low = 0 # define low as 0
    high = len(array)-1 # define high as the length of the array -1
    mid = 0 # define middle as 0

    if low <= high: # if low is less than high
        mid = (low + high) // 2 # find the middle (taking the highest index number plus the lowest and divided by two)
        
        if x == array[mid]: # if x is equal to the middle element, return it
            return mid
        elif x < array[mid]: # if x is lower than the middle element, make "high" the left of the middle to search the lower half
            high = mid - 1
            return high
        else:
            low = mid + 1 # if x is  smaller than the middle element, check to the right of the middle element
            return low
    else:
        return -1 

array = [1,2,3,4,5,6,7,8,9,10,11] # 6 is at position 5
x = 6

result = binarySearch(array, x)

if result != -1:
    print("Found at position : ",str(result))
else:
    print("Not found, try again")

Found at position :  5