The Little Book of Algorithms



Yüklə 1,84 Mb.
Pdf görüntüsü
səhifə3/4
tarix28.11.2023
ölçüsü1,84 Mb.
#168110
1   2   3   4
The Little Book of Algorithms

does not change whilst the program is 
running
, this is a constant. Programmers sometimes write 
constants in capitals and may give them meaningful names as 
shown. 
 
Line 3: The function 
circle_area 
is defined and has one 
parameter (a placeholder/variable) called 
radius

 
The 
area_out 
is calculated radius**2 may also be written as 
radius ^2 in other languages and psuedocode. 
 
Lines 8-10: This shows how the function may be used. 
 
Line 9: The 
circle_area 
is called and the 
radius
is passed 
as an argument. The result is stored in the variable 
area

 
Line 10: In Python, we can also use a comma to concatenate the 
area
to the output message. The advantage of using a comma to 
concatenate is that casting is done implicitly. This means the 
str
() 
function is not necessary. It is worth noting that concatenating 
with a comma will automatically add a space between 
concatenated strings. 









10 
CONSTANT_PI=3.14159 
def circle_area(radius_in): 
area_out = CONSTANT_PI * radius_in**2 
return area_out 
radius = int(input("Enter the radius of the circle: ")) 
area = circle_area(radius) 
print("The area of the circle is", area) 



A subprogram which checks if a number is odd or even. It will print 
a meaningful message accordingly. The program should loop until 
the user enters the sentinel value “STOP” 
This is a procedure as no value is returned. 
 
Line 2: The % symbol in Python means MODULO. So when we 
MOD2, we are checking for the remainder when dividing by 2 
 
Line 8: Sets a Boolean flag called 
again 
to True.
 
Line 9: This is a Pythonic way of writing 
while again ==
True: 
 
Lines 11-12: Provided the user does not enter the sentinel value 
(also known as a rogue or trip value) of “STOP”, the while loop 
will continue to call 
is_odd 
with each new number inputted to 
check if it is odd or even.
 
This program could be improved by using function instead of a 
procedure. All inputs and outputs would take place outside of 
the function and you could also use a main function as shown 
previously on page 7.









10 
11 
12 
13 
14 
15 
def is_odd(number_in): 
if int(number_in) %2 == 0: 
print("The number is even") 
else: 
print("The number is odd") 
again = True 
while again:
number = input("Enter a number") 
if number != "STOP" : 
odd = is_odd(number) 
else: 
again = False 


10 
A subprogram which outputs all the numbers between a certain 
start and stop value (inclusive). 
This is a procedure as it does not return a value.
 
The procedure 
number_generator 
is defined on lines 1-3. 
 
Line 2: uses a for loop to iterate from the start value to the stop 
value. In Python, the stop value is exclusive, so 
number_generator(1,10) would only print numbers 1 to 9, this is 
why we use 
stop+1

 
Lines 6-9 show how we would use the procedure. 
 
Lines 6-7: The user’s details are taken as inputs . 
 
Then the procedure is called on line 9. 









def number_generator(start, stop): 
for count in range(start,stop+1): 
print(count) 
start_num = int(input("Enter a start value")) 
stop_num = int(input("Enter a stop value")) 
number_generator(start_num, stop_num) 


11 
A program which generates a random number then asks the user 
to guess the random number. The program repeats until the 
correct number is guessed.
This is a function as the smallest number is returned. 
 
Line 1: Imports the 
random 
module so that we can use the 
randint
function to generate a random integer between 1 
and 10 (inclusive). 
 
Unlike the previous program, we do not know how many times 
we need to repeat; the user could get the answer wrong 8 times 
or they could guess it first time. In these situations we use a 
conditional loop i.e. a while loop. 
 
Line 3: Sets an initial value that will never match the random 
number. This ensures the while loop runs at least once. 
 
Lines 8-9: If the user guess is incorrect, we return to the top of 
the loop i.e. line 5. 









import random 
randomNumber = random.randint(1,10) 
guess = 99 
while guess != randomNumber: 
guess = int(input("Guess the number between 1 and \ 
10: ")) 
if guess == randomNumber: 
print("Correct") 
else: 
print("Try again") 


12 
A program which iterates through a list of numbers and outputs the 
lowest number 
 
Line 3: We start with the hypothesis that the item at position 0 
of 
numbers_list
is
the lowest. 
 
Line 5: We then iterate through the full length of the list, 
comparing each position with the initial value stored in 
lowest

 
Lines 6-7 If the current value is smaller than 
lowest
, this 
number replaces the item in 
lowest

 
Line 9: When the for loop has finished and we have therefore 
reached the end of the list, we output the value of 
lowest
.
 
This can also be written as a function which takes a list as an 
argument. 









numbers_list = [9,8,7,5,6,2,1,12,14,0,13] 
lowest = numbers_list[0] 
for count in range(len(numbers_list)): 
if numbers_list[count] < lowest: 
lowest = numbers_list[count] 
print("The lowest number in the list is ", lowest) 
def find_lowest(numbers_list_in): 
lowest = numbers_list_in[0] 
for count in range(len(numbers_list_in)): 
if numbers_list_in[count] < lowest: 
lowest = numbers_list_in[count] 
return lowest 
numbers_list = [9,8,7,5,6,2,1,12,14,0,13] 
lowest_num = find_lowest(numbers_list) 
print("The lowest number in the list is ", lowest_num) 









10 
11 
12 


13 
Iterating through a list from start to finish as seen in the previous 
algorithm is effectively a linear search. We start at position 0 and 
continue checking each position from left to right until we reach the 
end. A meaningful message informs the user whether the item was 
found. 
 
For all searching algorithms, you should start by setting a 
Boolean flag to False. We do this on line 6. 
 
Lines 9-11: If the target matches the item in the array, the name 
is outputted and the Boolean flag is set to True. 
 
Lines 13-14: When we’ve iterated through the entire list, check 
to see if 
found 
is still False. If so, the item was not in the list. 
 
Line 18: Notice how we pass the argument stored in the variable 
called 
name
into the parameter called 
target
. The argument 
and parameter name are different so that we understand that 
their scope is different. The footnote on page 5 explains this in 
more detail. 
def linear_search(target): 
names = ["Rocky", "Connor", "Jawwad", 
"Yacoub", "Cara", "Jess", 
"Jake", "Suki", "Zi", "Q"] 
found = False 
for count in range(len(names)): 
if target == (names[count]): 
print(target, "found at position", count) 
found = True 
if found == False: 
print(target, "was not found") 
name = input("Who are you looking for? ") 
linear_search(name) 









10 
11 
12 
13 
14 
15 
16 
17 
18 


14 
A program which searches for a student’s results within a 2D list of 
exam scores.¹ 
 
Line 10: Use a variable to set a Boolean flag to False. 
 
Lines 12-14: if the name is located, the 
found 
flag is set to 
True and the result can be found by indexing the 2D list using 
the current 
count 
and the 
exam_number

 
Line 18: if we reach the end of the list and found is still False, 
then the number was not in the list. 
 
Lines 16 and 19: Output a meaningful message.
¹Python does not have an array data structure. Instead it uses a list. The main differences 
between a list and an array is that lists allow the storage of mixed data types and they are 
dynamic (allow appending). I’ve tried to use single data types with the lists in this book so 
they appear more like arrays. I have also avoided the use of in-built list functions. This 
may seem strange and inefficient in places but it has been done as the GCSE exam will 
only feature arrays. 









10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
cs_scores=[["Jo","45","60","72"],["Zi","55","65","70"], 
["Ellie","71","78","78"],["Jessica","68","79","80"], 
["Abdul","65","70","71"]] 
print("We will try to find the result for a given \ 
student's exam") 
name = input("Enter a student name: ") 
exam_number = int(input("Enter the exam number: ")) 
found = False 
for count in range(len(cs_scores)): 
if name == cs_scores[count][0]: 
found = True 
result = cs_scores[count][exam_number] 
print(name+ "'s result for exam", exam_number,\ 
"was", result ) 
if found == False: 
print(name, "cannot be found") 


15 
A program which checks to see if the username and password 
matches the one in our program. The user gets three attempts. 
 
Line 3: Initialises a while loop counter called 
tries 
to 0. 
 
Line 5: The while loop provides a maximum of 3 password 
attempts. We use a while loop because we do not know how 
many attempts the user will need to get the answer correct.
 
Lines 10-12: If the correct 
username 
and 
password 
is 
supplied, we output a message and break out of the while loop. 
Otherwise, a meaningful error message is shown and the 
tries 
variable is incremented (Line 18).
 
Line 18: This is also a common way to increase a score or 
counter.
 
N.B. Storing the password as plaintext in the program that you 
are using is a really bad idea! Curious readers should visit: 
http://bit.do/hashing-python-passwords for more info. 
 









10 
11 
12 
13 
14 
15 
16 
17 
18 
username = "James" 
password = "myPasswordIsDog!" 
tries = 0 
while tries < 3: 
user_in = input("Enter the username") 
pass_in = input("Enter the password") 
if user_in == username: 
if pass_in == password: 
print("Logged in") 
break 
else: 
print("Incorrect password") 
else: 
print("Incorrect username") 
tries = tries+1 


16 
A procedure which performs a linear search on a 2D list that is 
stored in a file. 
 
Line 5: Opens the file 
users.txt 
in read mode. 
 
Line 6: Reads the file. We have used the 
eval 
function which 
means that the translator will treat the text file’s contents as a 
Python expression if the format is valid. In this case, it converts 
the contents of the text file into a 2D list and stores this under 
the identifier 
users_2D

 
Lines 17 and 21: calls the 
login 
procedure if the login fails 
i.e. it restarts the procedure.









10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20
21 
22 
23 
users.txt
[['lauw', 'insecurePwd'], ['vegaj', 'iLoveWebDesign'], 
['lassamil', 'zeroDawn']] 
def login(): 
username = input("What is your username") 
password = input("What is your password") 
newfile = open("users.txt","r") 
users_2D = eval(newfile.read()) 
newfile.close() 
found = False 
for count in range(len(users_2D)): 
if username == users_2D[count][0]: 
found = True 
if password == users_2D[count][1]: 
print("logged in") 
else: 
print("incorrect password") 
login() 
if found==False: 
print("Invalid username") 
login() 
login() 


17 
A program which allows the user to enter a pin number. If the user 
gets the pin number wrong, the program keeps asking them to 
enter a correct pin.
N.B. An unlimited number of attempts is a bad idea as it allows for 
brute force hacking. However, this is a common algorithm that is 
used in guessing games e.g. guess the number. 
 
The program keeps looping while the pin is not equal to 1984. It 
is very similar to the program on page 11.
 
Line 1: Sets an initial value that is not equal to the pin. This 
ensures the while loop runs at least once. 
 
Line 3 asks the user to enter their pin. 
 
Lines 5-8 check to see if the pin matches, a meaningful 
message is produced depending on the outcome.








pin = "" 
while pin != "1984": 
pin = input("Please enter the pin") 
if pin == "1984": 
print("Logged in") 
else: 
print("Incorrect pin") 


18 
A program which adds up numbers in a list 
 
Line 3: Defines the variable 
total
and initialises it to 0. 
 
Line 5: Iterates through the length of the list, 0 to 9 (exclusive). 
 
Line 6: Takes the current value of total and adds the current 
value in the list to the total. This cumulative total is commonly 
used for scores and timers in programs. 
 
A functional programming approach is also shown below: 








number_list = [9, 8, 3, 5, 4, 1, 8, 4, 1] 
total = 0 
for count in range(len(number_list)): 
total = total + number_list[count] 
print("The total sum of the list is ", total) 
def total_list (number_list_in):
total = 0 
for count in range(len(number_list)): 
total = total + number_list[count] 
return total #the total is returned 
def main():
# The main function contains all inputs and outputs
number_list = [9, 8, 3, 5, 4, 1, 8, 4, 1] 
op = input("Do you wish to find the mean, lowest \
value, highest value or the total of the list?") 
# Call the relevant function based on the user input
if op == "total":
total_out = total_list(number_list)
print("The total sum of the list is ", total_out) 
# Elifs would go here
# Call the main function 
main() 









10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 


19 
A program which adds up each student’s scores in a 2D list i.e. a 
row or sub list
 
In the program above we are trying to calculate each student’s 
total, so the student is in the first loop. This is also known as the 
outer loop. 
 
Line 8: Iterate through 0 to 5 (exclusive) i.e each student . 
 
Line 9: Now starting with student 0 i.e. Karman, enter the nested 
inner loop through exams 1 to 4 (exclusive) i.e. exams 1-3. 
 
Line 10: Add the score to the running total. 
 
Line 11: Output the student’s total. 
 
Line 12: Reset the 
total 
variable to 0 so that we can now 
start the second iteration of the student loop and calculate the 
total of Daniel’s exams.
cs_scores = [["Karman","45","60","72"], 
["Daniel","55","65","70"], 
["Giacomo","71","78","78"], 
["Jessica","68","79","80"], 
["Edie","98","85","91"]] 
total = 0 
for student in range(len(cs_scores)): 
for exam in range(1,4): 
total = total + int(cs_scores[student][exam]) 
print("Total for",cs_scores[student][0],"=",total) 
total = 0









10 
11 
12 


20 
A subprogram which takes a 4-bit binary string as an argument and 
returns the denary equivalent 
 
Lines 17-18: The default value for 
__name__ 
in every Python 
program is 
'__main__' 
and so the main function is called. 
 
Line 12: Asks the user for a binary string. 
 
Line 13: Calls the 
binary_to_denary
function, passing the 
binary string as an argument. The returned value will be stored 
in the denary variable and output on Line 14. 
 
Line 1: Defines a function called 
binary_to_denary 
and 
takes the 
binary_in
string as an argument. 
 
Lines 2-5: Slices each individual digit and multiplies it by its 
relevant place value. 
 
Lines 7-8: The total is calculated and returned. 
 
Line 14: The denary equivalent is outputted with a meaningful 
message. 
def binary_to_denary(binary): 
bit1 = int(binary[3])*1 
bit2 = int(binary[2])*2 
bit3 = int(binary[1])*4 
bit4 = int(binary[0])*8 
denary_out = bit1 + bit2 + bit3 + bit4 
return denary_out 
def main():
binary_in = input("Enter the binary string") 
denary = binary_to_denary(binary_in) 
print("The binary value", binary_in, "in denary \ 
is", denary) 
if __name__ == '__main__': 
main() 









10 
11 
12 
13 
14 
15 
16 
17 
18 


21 
A program which converts a denary value between 0-15 to a 4-bit 
binary value 
 
Line 3: With binary numbers, we cannot use the integer data 
type. A default string of “0000” also cannot be used as strings in 
Python are not mutable. Having four bits like the previous 
program could work, but I would have to define and initialise 
each bit. This could create up to four lines of extra code. I 
therefore decided to use a list as lists are mutable. 
 
Lines 7-17: This models the “left-to-right” process of checking 
how many 8s, 4s, 2s and 1s go into a number between 0-15.
 
Lines 19-20: This is a way to iterate through the list and print 
each element without commas, brackets and new lines. The 
end=“” means at the end of each print, do not add anything, as 
a default end=“\n” i.e. a new line at the end of every print. 









10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
denary = int(input("Enter the denary number between \ 
0 and 15")) 
binary = ["0","0","0","0"] 
if denary > 15: 
print("error") 
if denary >=8 and denary <=15: 
binary[0] = "1" 
denary = denary - 8 
if denary >=4: 
binary[1] = "1" 
denary = denary - 4 
if denary >=2: 
binary[2] = "1" 
denary = denary - 2 
if denary >=1: 
binary[3] = "1" 
for count in range(len(binary)): 
print(binary[count],end="") 


22 
You’ve written a few programs in class and at home. Now is the 
time to practise. The challenges will start by getting you to modify 
existing programs in this book and progressively get more difficult. 
Try to write your answer without looking back at the programs at 
the front of this book. If you really need a hint, page numbers are 
provided. You can check your answers against the solutions
Pro tip: Always answer in pencil first, you can go over these in pen 
afterwards. 
1. 
Highest number……………………………………….………… 
2. 
Unique username…………………………………………..….. 
3. 
Volume of a cuboid……………………………….…………... 
4. 
Roll a double to start……………………….………………… 
5. 
Counting vowels………………………………………………... 
6. 
Highest number in a list…………………………….………. 
7. 
Weak password?……………………………………………..… 
8. 
Grade boundaries……………………………….….…………. 
9. 
Penalty shootout………………………………………….….... 
10. Register an account ………………………………………..... 
11. Average of a list…………………………………………………. 
12. Total for each exam in a 2D list………….………….. 
13. Average for each student in a 2D list………………….. 
14. Converting hexadecimal to denary……………………… 
15. Calculating the file size of a sound file……………….. 
23 
24 
28 
29 
30 
34 
35 
36 
37 
40 
42 
43 
44 
45 
46 


23 
Write a subprogram that has three parameters, num1, num2 and 
num3. The program should take three numbers as arguments and 
return the highest number.
Hint: You may consult the lowest number program on page 5. 
def highest_number (num1, num2, num3): 
if num1 >= num2 and num1 >= num3: 


24 
Write a subprogram which generates a username for a teacher 
based on their first name and surname. The format should be their 
surname, followed by the first letter of their first name. The 
program should check to see if the username already exists in 
users.txt and if so, a unique username should be generated by 
appending a “#” symbol. E.g. if a teacher joins the school called 
Winnie Lau, their username would be LauW# .
Hint: You may consult programs on page 6 and 16 
def generate_username(firstname, lastname): 
username =
#check to see if the username already exists 
users_file = open( , )
usernames = eval( ) 
users_file.close() 
for count in range(len( )): 
if ==username: 
username =
return
users.txt
[['LauW', 'insecurePwd'], ['VegaJ', 'iLoveWebDesign'], 
['LassamiL', 'zeroDawn']] 


25 
Write a program which asks for a teacher’s first name and 
surname. Then demonstrate how you would call the function on the 
previous page to generate a username and output this in a 
meaningful message. 
The next two pages are provided so that you can practise Challenges 1 
and 2 without the writing frames. It’s important that you keep challenging 
yourself and eventually you should be able to write these programs 
independently. 


26 
Write a subprogram that has three parameters, num1, num2 and 
num3. The program should take three numbers as arguments and 
return the highest number.


27 
Write a subprogram which generates a username for a teacher 
based on their first name and surname. The format should be their 
surname, followed by the first letter of their first name. The 
program should check to see if the username already exists in 
users.txt and if so, a unique username should be generated by 
appending a “#” symbol. E.g. if a teacher joins the school called 
Winnie Lau, their username would be LauW# .
users.txt
[['LauW', 'insecurePwd'], ['VegaJ', 'iLoveWebDesign'], 
['LassamiL', 'zeroDawn']] 


28 
Write a subprogram that takes the length, width and height as 
arguments and return the volume of the cuboid.
After writing the function, show how you might use the function to 
output an answer with a meaningful message.
Hint: You may consult the “area of a circle” program on page 8.


29 
Write a program which simulates two dice being rolled. Output the 
values of both dice. Keep prompting the user to roll the dice until 
the two dice match e.g. Double 6. When the user roles a double, 
output the message “Game loading”. For all other combinations, 
ask the user to press Enter to roll again. 
Hint: You may consult the while loop programs on pages 11 and 17. 


30 
def vowel_counter(sentence): 
A = 0 
E = 0 
I = 0 
for count in range( 
if sentence[count] == “A”: 
Iterate through the sentence below and count how many times 
each vowel occurs. At the end of the program, ouput the number of 
As, Es, Is, Os and Us with a meaningful message. 
sentence = “Learning programming is similar to learning a musical 
instrument. Both involve practise and making lots of mistakes. 
Both also require perseverance to develop fluency. Keep going!” 
# hint: See programs on pages 10, 12, 15. You can iterate through 
the sentence in the same way you iterate through a list or list.


31 


32 
Iterate through the sentence below and count how many times 
each vowel occurs. At the end of the program, ouput the number of 
As, Es, Is, Os and Us with a meaningful message. 
sentence = “Learning programming is similar to learning a musical 
instrument. Both involve practise and making lots of mistakes. 
Both also require perseverance to develop fluency. Keep going!” 
#Extra challenge, store the vowel counters in a list or 2D list.


33 


34 
Write a program which iterates through a list of numbers and 
outputs the highest number 
I dare you to pass the list into a function! 
Hint: Page 10 
numbers = [9, 8, 72, 22, 21, 81, 2, 1, 11, 76, 32, 54] 


35 
Write a program which asks the user to enter a desired password. 
Perform a linear search through a list of obvious (weak) passwords. 
If the user’s password is found in the obvious passwords list, 
output a message to tell them it is weak and would be easily 
hacked using a brute force attack.
Extra challenge: You may also want to add in various validation 
checks. One example might be a length check, so if the password 
does not meet a particular length it is also declared weak. 
Meaningful messages are necessary for each different validation 
check.
obvious = [“password”, “qwerty”, “hello123”, “letmein”, “123456”] 


36 
An A-Level student wants to find out how many marks are required 
to receive a certain grade. Write a subprogram that takes a user’s 
desired grade as an argument and then iterates through the 2D list 
to return the number of marks they need for that grade. 
Hint: Page 12 
def marks( ): 
grades = [ [“A*”, “90”], [“A”, “83”,], [“B”, “72”], [“C”, 
“60”], [“D”, “49”], [“E”, “30”] ] 


37 
Write a program which simulates a penalty shootout. The computer 
is the goalkeeper and dives a random direction or stays in the 
centre each turn. The keeper’s move is generated but not 
outputted at first. The user takes a penalty by typing in “left”, 
“right” or “centre”. The keeper’s move is then outputted. If the 
player typed left and the keeper dives left, the penalty is saved etc. 
The program repeats 5 times. After 5 penalties, the winner is 
announced with a meaningful message.
Hint: Pages 10 and 11. I strongly advise using a pencil for this one! 
import random 
keeper = [“left”, “centre”, “right”] 
# More space on next page... 


38 


39 


40 
Write a subprogram to allow a teacher to register a new account. 
The subprogram should take the username and password as 
arguments and write these details to the existing users.txt file 
shown opposite. We can assume this subprogram used the 
generate_username
function on page 24 to for the username 
and a password is inputted separately in the main function.
Hint: Use the comments on the opposite page as skeleton code to 
structure your subprogram 
def new_user(username_in, password_in): 


41 
# define a function called new_user with two parameters: username and password 
#open the file in read mode 
#use eval to read in the 2D list 
#close the file 
#make a new list for the new user 
#append the username to the new user list 
#append the password to the same list 
#append this new user list to the existing 2D list that we read in 
#open the file in write mode 
#cast the updated 2D list as a string and write this string to the file 
#close the file 
users.txt
[['lauw', 'insecurePwd'], ['vegaj', 'iLoveWebDesign'], 
['lassamil', 'zeroDawn']] 


42 
Write a subprogram called mean_of_list that takes a list of 
numbers as an argument and returns the mean average.
Write the main function which contains your list and which calls the 
subprogram (function)
Hint: Pages 7, 18, 20 
def mean_of_list(numbers_list_in): 


43 
cs_scores = [["Karman","45","60","72"], 
["Daniel","55","65","70"],
["Giacomo","71","78","78"], 
["Jessica","68","79","80"],
["Edie","98","85","91"]]
total = 0
for exam in range( ): 
Recall the program which adds up each student’s scores in a 2D 
list i.e. a row or sub list on page 19.
Write a program which will 
output the total for each exam with a meaningful message. 
Hint: As the focus is on each 

Yüklə 1,84 Mb.

Dostları ilə paylaş:
1   2   3   4




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin