For the following functions, consider:
def maximum(a_list):
maximum = float('-inf')
i = 0
# What is the precondition?
# Invariant
while i < len(a_list):
# Invariant
if a_list[i] > maximum:
maximum = a_list[i]
i += 1
# Invariant
# Invariant
# What is the postcondition?
return maximum
def maximum2(a_list):
maximum = float('-inf')
# What is the precondition?
# Invariant
for element in a_list:
# Invariant
if element > maximum:
maximum = element
# Invariant
# Invariant
# What is the postcondition?
return maximum
This is probably not the best way to implement this function. Once you’ve determined the loop invariant for this implementation,
def nested_maximum(a_list_of_lists):
maximum = float('-inf')
for a_list in a_list_of_lists:
temp_max = float('-inf')
for element in a_list:
if element > temp_max:
temp_max = element
if temp_max > maximum:
maximum = temp_max
return maximum
def powers_of_two(n):
total = 1
i = 0
while i < n:
total += 2**i # Exponentiation
i += 1
return total
def reverse(n):
m = n
rever = 0
while m > 0:
remainder = m % 10
rever = 10*rever + remainder
m = m // 10 # Integer division (the floor of m/10)
return rever
def bubble_sort(a_list):
for passes in range(len(a_list)-1, 0, -1):
for i in range(passes):
if a_list[i] > a_list[i + 1]:
a_list[i], a_list[i + 1] = a_list[i + 1], a_list[i] # This swaps two values
return a_list
Challenge problem:
Nim: Given two piles of counters, each having an arbitrary number of initial counters. Two players take turns removing counters from the piles. Each player chooses to remove as many counters as they would like (but at least one). The player who removes the last counter wins the game.