Opstap¶
De uitwerkingen staan in dezelfde volgorde als de negen opdrachten in de opstap. Bij de naspeel- en leesopdrachten voert de cel de code uit.
Opdracht 1¶
Het programma drukt zeven aanroepen af. Elke aanroep die niet in een basisgeval eindigt, doet er twee: eerst use it, dan lose it.
function(3, [1, 2]) True
├── function(2, [2]) True use it: de 1 gebruikt
│ ├── function(0, []) True use it: de 2 gebruikt
│ └── function(2, []) False lose it
└── function(3, [2]) False lose it: de 1 laten liggen
├── function(1, []) False use it
└── function(3, []) False lose it
De laatste regel drukt True af: 3 cent betaal je met 1 en 2.
def function(amount, coins):
print(amount, coins)
if amount == 0:
return True
elif amount < 0:
return False
elif coins == []:
return False
else:
use_it = function(amount - coins[0], coins[1:])
lose_it = function(amount, coins[1:])
return use_it or lose_it
print(function(3, [1, 2]))
3 [1, 2]
2 [2]
0 []
2 []
3 [2]
1 []
3 []
True
De controle uit de opstap:
def check(amount, coins, depth):
"""Doet hetzelfde als function en drukt elke aanroep af, met wat hij teruggeeft."""
print(" " * depth + "function(" + str(amount) + ", " + str(coins) + ")")
if amount == 0:
result = True
elif amount < 0:
result = False
elif coins == []:
result = False
else:
use_it = check(amount - coins[0], coins[1:], depth + 1)
lose_it = check(amount, coins[1:], depth + 1)
result = use_it or lose_it
print(" " * depth + "-> " + str(result))
return result
check(3, [1, 2], 0)
function(3, [1, 2])
function(2, [2])
function(0, [])
-> True
function(2, [])
-> False
-> True
function(3, [2])
function(1, [])
-> False
function(3, [])
-> False
-> False
-> True
True
Opdracht 2¶
function(5, [4, 3, 2]) geeft 5 terug, met de items 3 en 2. Use it met de 4
levert maar 4 op: daarna is er nog 1 over, en bij de aanroepen
function(1, [3, 2]) en function(1, [2]) past het eerste item niet. Daar
wordt alleen lose it geprobeerd.
def function(capacity, items):
if items == []:
return 0
first = items[0]
rest = items[1:]
if first > capacity:
return function(capacity, rest)
else:
use_it = first + function(capacity - first, rest)
lose_it = function(capacity, rest)
return max(use_it, lose_it)
print(function(5, [4, 3, 2]))
5
De controle uit de opstap:
def check(capacity, items, depth):
"""Doet hetzelfde als function en drukt elke aanroep af, met wat hij teruggeeft."""
print(" " * depth + "function(" + str(capacity) + ", " + str(items) + ")")
if items == []:
result = 0
elif items[0] > capacity:
print(" " * depth + "past niet: " + str(items[0]))
result = check(capacity, items[1:], depth + 1)
else:
use_it = items[0] + check(capacity - items[0], items[1:], depth + 1)
lose_it = check(capacity, items[1:], depth + 1)
result = max(use_it, lose_it)
print(" " * depth + "-> " + str(result))
return result
check(5, [4, 3, 2], 0)
function(5, [4, 3, 2])
function(1, [3, 2])
past niet: 3
function(1, [2])
past niet: 2
function(1, [])
-> 0
-> 0
-> 0
function(5, [3, 2])
function(2, [2])
function(0, [])
-> 0
function(2, [])
-> 0
-> 2
function(5, [2])
function(3, [])
-> 0
function(5, [])
-> 0
-> 2
-> 5
-> 5
5
Opdracht 3¶
sorted en max zonder key= vergelijken de woorden op alfabet: "zebra" is
dan het grootste. Met key=len vergelijken ze de lengte, en dan is "olifant"
het grootste en "kat" het kleinste.
animals = ["olifant", "kat", "zebra"]
print(sorted(animals))
print(max(animals))
print(max(animals, key=len))
print(min(animals, key=len))
['kat', 'olifant', 'zebra']
zebra
olifant
kat
Opdracht 4¶
Zonder key= sorteert sorted op de hele string, dus op de letter vooraan. Met
de lambda-functie sorteert ze op het tweede teken, het cijfer. Voor "b2" geeft
de lambda-functie "2" terug.
codes = ["b2", "a3", "c1"]
print(sorted(codes))
print(sorted(codes, key=lambda s: s[1]))
['a3', 'b2', 'c1']
['c1', 'b2', 'a3']
Opdracht 5¶
function roept f twee keer aan: eerst op x, en dan op wat daaruit komt. Bij
10 wordt dat 10 + 3 + 3, en bij "hoi" komen er twee uitroeptekens achter.
def function(f, x):
return f(f(x))
print(function(lambda x: x + 3, 10))
print(function(lambda s: s + "!", "hoi"))
16
hoi!!
Opdracht 6¶
words = ["vuurtoren", "de", "draait", "nacht"]
by_length = sorted(words, key=len)
longest = max(words, key=len)
shortest = min(words, key=len)
assert by_length == ["de", "nacht", "draait", "vuurtoren"]
assert longest == "vuurtoren"
assert shortest == "de"
Opdracht 7¶
pairs = [["b", 2], ["a", 3], ["c", 1]]
def second(pair):
"""Geeft het tweede element van pair."""
return pair[1]
by_second = sorted(pairs, key=second)
by_second_lambda = sorted(pairs, key=lambda pair: pair[1])
assert second(["b", 2]) == 2
assert by_second == [["c", 1], ["b", 2], ["a", 3]]
assert by_second_lambda == [["c", 1], ["b", 2], ["a", 3]]
Opdracht 8¶
prices = {"brood": 3.2, "kaas": 6.5, "melk": 1.25, "appels": 2.8}
cheapest = min(prices, key=prices.get)
by_price = sorted(prices, key=prices.get)
assert cheapest == "melk"
assert by_price == ["melk", "appels", "brood", "kaas"]
Opdracht 9¶
Zodra één element niet aan de test voldoet, weet je het antwoord en stopt de recursie.
def all_pass(L, test):
"""Geeft True als test(x) waar is voor elk element x van L."""
if L == []: # basisgeval
return True
elif not test(L[0]): # basisgeval: dit element voldoet niet
return False
else: # recursief geval
return all_pass(L[1:], test)
assert all_pass([2, 4, 6], lambda x: x % 2 == 0) == True
assert all_pass([2, 3, 4], lambda x: x % 2 == 0) == False
assert all_pass(["kat", "ezel"], lambda s: len(s) >= 3) == True
assert all_pass([], lambda x: x > 0) == True