Section 3.9 and 3.11
Notes
components of Algorithms
- selection
- Sequence
- Iteration
- Algorithms can be written differently but it still go same thing. Some Algorithms look similar, but it work in different way.
- !!!Know that the code can be similar but sometime they goes different!!!! ### So, why is this important? Why are we even doing this?
- When 2 algorithms look extremely similar, it is easy to assume they do the same thing. However, that is not the case and we have learn how to notice small differences in code and pretty much debug.
- just know that codes that look similar don't always produce the same things :) ### Why is this important?
- When collaborating or working on group projects, two people might come up with two different ways to solve a problem, and that happens a lot.
- know that same goal can be achieved in many ways (the possibilities are endless)
- make notes in you code! (explain how it works to others or you future self) ### Binary Search:
repeatedly dividing a search interval in half
Binary Search Steps:
- first put the numbers in order
- ascending
- descending
-
find the middle number first
- this is found by taking the highest index number plus the lowest index number and divide by 2
- the numbers on the right will be greater and the numbers on the left will be smaller
- this can be represented with a binary tree
- middle number with the smaller number branched off on the left and bigger numbers branched off on the right
-
these lists are not always numbers
- lists can be made with strings
- ex. ["apple", "banana", "cherry", "peach", "watermelon"]
- alphabetical order
- a-z
l = [7, 13, 96, 111, 33, 84, 60]
for j in range(len(l)):
k = len(l) - j
for i in range(1, k):
if l[i-1] >= l[i]:
temp = l[i-1]
l[i-1] = l[i]
l[i] = temp
def finding(x):
n=len(x)
if n%2==1:
result=x[int((n-1)/2)]
else:
result=(x[int(n/2)-1]+x[int(n/2)])/2
return result
print(finding(l))
Hack 1
Why it is important to know algorithms that look different?
- It is important to know algorithms that look different can do the same thing because if we know many codes, it will comfortable to us to write. There are many ways in coding to make same result. But, if the code is shorter, it will be more easy to understand or can teach to other people. If you know different kind of code that lead to same result, you can write each codes in proper situation. Code is not just made by one person and codes are being complicated these days.
Wht it is important to aware algorithms that look same but different result?
- It is also important to learn same algorithms that lead to different result. It will make you prevent mistake in your code. Most of elective devices are composed by several codes. But, if there is one mistake in just one code. The devices will not work well. The code is like a gear. If one gear in the clock is broken, the clock will stop. This is also same as codes.
Boolean conversion
Raining = True
IsWeekend = False
if IsWeekend == True:
print("Don't have to go school")
else:
if Raining == True:
print("Need to take Umbrella")
else:
print("Don't need to take Umbrella")
Raining = True
IsWeekend = False
SchoolForUmbrella = not(IsWeekend) and Raining
if SchoolForUmbrella == True:
print("Take Umbrella")
if SchoolForUmbrella == False:
print("Don't have to take it")
import datetime
now = datetime.datetime.now()
print(now.year, 'year')
print(now.month, 'month')
print(now.day, 'day')
print(now.hour, 'hour')
print(now.minute, 'minute')
print(now.second, 'second')
print('{}year {}month {}day {}hour {}minute {}second'.format(
now.year,
now.month,
now.day,
now.hour,
now.minute,
now.second
))
if now.hour < 12:
print('The current time is {}:{}, so it is AM!'.format(now.hour, now.minute))
if now.hour >=12:
print('The current time is {}:{}, so it is PM!'.format(now.hour, now.minute))
if 3 <= now.month <= 5:
print('This month is spring!'.format(now.month))
elif 6 <= now.month <= 8:
print('This month is summer!'.format(now.month))
elif 9 <= now.month <= 11:
print('This month is fall!'.format(now.month))
elif now.month ==12 or 1<= now.month <= 2:
print('This month is winter!'.format(now.month))
Hack 2
Flow chart
- I made a code about rock, scissor, papaer
- Start
- Player and computer are doing rock, scissor, paper
- compare what they did
- If (player,com) is (rock, scissor) or (paper, rock) or (scissor, paper), player won
- If player and computer did a same thing, it will be draw.
- else, computer won
- End
import random
sel = ['scissor', 'rock', 'paper']
result = {0: 'win.', 1: 'lose.', 2: 'draw.'}
def checkWin(user, com):
if not user in sel:
print('you wrote wrong. type it again')
return False
print(f'player 1 ( {user} vs {com} ) com')
if user == com:
state = 2
elif user == 'scissor' and com == 'rock':
state = 1
elif user == 'rock' and com == 'paper':
state = 1
elif user == 'paper' and com == 'scissor':
state = 1
else:
state = 0
print(result[state])
return True
print('\n-------------------------------------------')
while True:
user = input("rock, scissor, paper : ")
com = sel[random.randint(0, 2)]
if checkWin(user, com):
break
print('-------------------------------------------\n')
import random
#sets variables for the game
num_guesses = 0
user_guess = 0
upper_bound = 100
lower_bound = 0
#generates a random number
number = int(random.randint(1,100))
# print(number) #for testing purposes
print(f"I'm thinking of a number between 1 and 100.")
#Write a function that gets a guess from the user using input()
def guess():
guess = int(input("Guess the number: "))#add something here
return guess#add something here
#Change the print statements to give feedback on whether the player guessed too high or too low
def search(number, guess):
global lower_bound, upper_bound
if guess < number:
print("The random Number is more higher than you guess") #change this
lower_bound = guess
elif guess > number:
print("The random Number is more lower than you guess") #change this
upper_bound = guess
return lower_bound, upper_bound
while user_guess != number:
user_guess = guess()
num_guesses += 1
print(f"You guessed {user_guess}.")
lower_bound, upper_bound = search(number, user_guess)
print(f"Guess a number between {lower_bound} and {upper_bound}.")
print(f"You guessed the number in {num_guesses} guesses!")
import random
tries = 0
guess = 0
answer = random.randint(1,100)
print("guess the number between 1 to 100")
guess = int(input("enter the number"))
while True:
tries = int(tries + 1)
if tries > 10:
print("Answer is ", answer)
break
elif guess < answer:
print("Low")
elif guess > answer:
print("High")
elif guess == answer:
print("Congratulation you tries", tries +1, "times")
break
guess = int(input("enter the number"))
a = [12, 14, 43, 57, 79, 80, 99]
midNumber = round(((len(a)-1)/2))
print(midNumber)
print(a[midNumber])
b = [92, 43, 74, 66, 30, 12, 1]
b.sort()
median = 0
idx = 0
if len(b) % 2 == 0:
idx = len(b)//2
median = (b[idx-1] + b[idx])/2
else:
idx = len(b)//2
median = b[idx]
print(idx)
print(median)
lst = [7, 13, 96, 111, 33, 84, 60]
def median(i):
half = len(i)//2
i.sort()
if not len(i) % 2:
return(i[half-1]+i[half])/2.0
return i[half]
print(median(lst))
l = [7, 13, 96, 111, 33, 84, 60]
for j in range(len(l)):
k = len(l) - j
for i in range(1, k):
if l[i-1] >= l[i]:
temp = l[i-1]
l[i-1] = l[i]
l[i] = temp
def finding(x):
n=len(x)
if n%2==1:
result=x[int((n-1)/2)]
else:
result=(x[int(n/2)-1]+x[int(n/2)])/2
return result
print(finding(l))
Question 1
- Using one of the sets of numbers from the question above, what would be the second number looked at in a binary search if the number is more than the middle number? #### Answer
- Set1: 80, Set2: 74, and Set: 96. ### Question2
-
Which of the following lists can NOT a binary search be used in order to find a targeted value?
a. ["amy", "beverly", "christian", "devin"]
b. [-1, 2, 6, 9, 19]
c. [3, 2, 8, 12, 99]
d. ["xylophone", "snowman", "snake", "doorbell", "author"] #### Answer
- The answer is C, because it is not sorted.
def board(bingo, dimension):
for i in range(dimension):
print(' _', end = '')
for i in range(dimension):
print()
print('|', end = '')
for j in range(dimension):
print(bingo[i][j] + '|', end = '')
print()
while True:
dimension = int(input("Please input the size of the game board(more than 2): "))
if dimension <= 2 :
print('[Error] try again')
else:
break
bingo = [['_']*dimension for i in range(dimension)]
board(bingo, dimension)
turn = 1
play_count = 0
while True:
print('<Play no.{}>'.format(play_count+1))
if turn == 1:
print('Currently player: 1')
row_1 = int(input('Which row?(start with 1)'))
column_1 = int(input('Which column?(start with 1)'))
if bingo[row_1-1][column_1-1] != '_':
print('Space is not empty. Try again')
turn = 1
continue
else:
bingo[row_1-1][column_1-1] = 'O'
board(bingo,dimension)
turn = 2
elif turn == 2:
print('Currently player: 2')
row_2 = int(input('Which row?(start with 1) '))
column_2 = int(input('Which column?(start with 1) '))
if bingo[row_2-1][column_2-1] != '_':
print('Space is not empty. Try again')
turn = 2
continue
else:
bingo[row_2-1][column_2-1] = 'X'
board(bingo,dimension)
turn = 1
check_diag = []
check_reverse = []
check_row = []
check_column =[]
for i in range(dimension):
check_diag.append(bingo[i][i])
check_reverse.append(bingo[dimension-i-1][i])
for j in range(dimension):
check_row.append(bingo[i][j])
check_column.append(bingo[j][i])
if set(check_row) == {'O'}:
print('Player 1 wins!')
turn = 0
elif set(check_row) == {'X'}:
print('Player 2 wins!')
turn = 0
check_row = []
if set(check_column) == {'O'}:
print('Player 1 wins!')
turn = 0
elif set(check_column) == {'X'}:
print('Player 2 wins!')
turn = 0
check_column = []
check_diag = set(check_diag)
check_reverse = set(check_reverse)
if check_diag == {'O'} or check_reverse == {'O'}:
print('Player 1 wins!')
turn = 0
elif check_diag == {'X'} or check_reverse == {'X'}:
print('Player 2 wins!')
turn = 0
play_count += 1
if turn == 0 or play_count == dimension**2:
print('Finish')
break