Probeer bij het maken van de onderstaande oefeningen programma's te schrijven die generiek zijn. Dat wil zeggen, die niet alleen het juiste antwoord geven voor het bij de opgave gegeven voorbeeld, maar het juiste antwoord in alle mogelijke, op het voorbeeld gelijkende, gevallen.
Dus het is beter als je programma bij 1b werkt niet alleen voor de gegeven list A = [[1, 2, 3], [4, 5, 6], [], [7, 8], [9]], maar ook voor andere lists die er ongeveer hetzelfde uitzien.
Schrijf een programma om ...
a. de verwachtingswaarde van het totaal aantal ogen te bepalen als je gooit een 6-zijdige dobbelsteen.
b. de verwachtingswaarde van het totaal aantal ogen te bepalen als je gooit met drie 6-zijdige dobbelstenen.
c. de verwachtingswaarde van het totaal aantal ogen te bepalen als je gooit met vier dobbelstenen: een 5-zijdige, een 8-zijdige, een 10-zijdige en een 12-zijdige?
d. de verwachtingswaarde van het totaal aantal ogen te bepalen als je gooit met een opgegeven aantal dobbelstenen met een opgegeven aantal zijden.
dice = [5, 8, 10, 12] # als oefening 1c. of:
dice = [6, 6, 8, 10, 12]
In [ ]:
# 1a
pi_times_xi = []
for d1 in range(1, 7):
pi_times_xi.append(d1 / 6)
expected_value = sum(pi_times_xi)
print("Expected value:", expected_value)
In [ ]:
# 1b
pi_times_xi = []
for d1 in range(1, 7):
for d2 in range(1, 7):
for d3 in range(1, 7):
pi_times_xi.append((d1 + d2 + d3) / (6**3))
expected_value = sum(pi_times_xi)
print("Expected value:", expected_value)
In [ ]:
# 1c
pi_times_xi = []
for d1 in range(1, 6):
for d2 in range(1, 9):
for d3 in range(1, 11):
for d4 in range(1, 13):
pi_times_xi.append((d1 + d2 + d3 + d4) * (1/5 * 1/8 * 1/10 * 1/12))
expected_value = sum(pi_times_xi)
print("Expected value:", expected_value)
In [ ]:
# 1d: optie 1 - uitrekenen (easy way out)
dice = [6, 6, 8, 10, 12]
expected_values = []
for die in dice:
total = 0
for value in range(1, die + 1):
total += value
expected_values.append(total / die)
print("Expected value:", sum(expected_values))
In [ ]:
# 1d: optie 2 - alle combinaties genereren zonder recursie (the hard way)
dice = [6, 6, 8, 10, 12]
values = dice.copy()
pi = 1
for value in values:
pi *= 1 / value
pi_times_xi = 0
while values[0] > 0:
xi = sum(values)
pi_times_xi += xi * pi
i = len(values) - 1
values[i] -= 1
while i > 0 and values[i] == 0:
values[i] = dice[i]
i -= 1
values[i] -= 1
print("Expected value:", pi_times_xi)
In [ ]:
# 1d: optie 3 - alle combinaties genereren met recursie (the easy hard way)
def dice_combinations(dice):
result = []
if len(dice) > 0:
for i in range(1, dice[0] + 1):
rest_results = dice_combinations(dice[1:])
if len(rest_results) > 0:
for rest_result in rest_results:
result.append((i,) + rest_result)
else:
result.append((i,))
return result
dice = [6, 6, 8, 10, 12]
combinations = dice_combinations(dice)
expected_value = 0
for combination in combinations:
expected_value += sum(combination) / len(combinations)
print("Expected value:", expected_value)
Schrijf een programma dat ...
a. het aantal geneste lists van een list geeft.
A = [[1, 2, 3], [4, 5, 6], [], 7, 8, [9]]
# bepaal aantal geneste lists in A (=4)
b. het totaal aantal elementen van een list plus het aantal elementen van alle geneste lists in een list geeft.
A = [[1, 2, 3], [4, 5, 6], [], 7, 8, [9]]
# bepaal het totaal aantal elementen in A (incl. geneste lists) (=9)
c. de som van alle elementen in een list, inclusief de elementen in alle geneste lists.
A = [[1, 2, 3], [4, 5, 6], [], 7, 8, [9]]
# bepaal de som van alle elementen van in A geneste lists (=45)
In [ ]:
# 2a
A = [[1, 2, 3], [4, 5, 6], [], 7, 8, [9]]
counter = 0
for elem in A:
if isinstance(elem, list):
counter += 1
print("Aantal geneste lists:", counter)
In [ ]:
# 2b
A = [[1, 2, 3], [4, 5, 6], [], 7, 8, [9]]
counter = 0
for elem in A:
if isinstance(elem, list):
for e in elem:
counter += 1
else:
counter += 1
print("Aantal elementen:", counter)
In [ ]:
# 2c
A = [[1, 2, 3], [4, 5, 6], [], 7, 8, [9]]
total = 0
for elem in A:
if isinstance(elem, list):
for e in elem:
total += e
else:
total += elem
print("Som van de elementen:", total)
Schrijf een programma dat ...
a. een platte list maakt met alle elementen van een list, inclusief de elementen in geneste lists.
A = [[1, 2, 3], 4, 5, [6], [7, 8], 9]
# maak een 'platte' list met de elementen van A
# (= [1, 2, 3, 4, 5, 6, 7, 8, 9])
b. alle opeenvolgende duplicaten van elementen in een list verwijdert.
A = [1, 1, 1, 1, 2, 2, 3, 4, 4, 4, 1, 1]
# verwijder opeenvolgende duplicaten van elementen in A
# (= [1, 2, 3, 4, 1])
c. een run-length encoded versie van een list maakt. Daarbij maak je een nieuwe list, waarin alle opeenvolgende duplicaten van de elementen van de list zijn vervangen door een tuple met daarin het element en het aantal duplicaten.
A = [1, 1, 1, 1, 2, 2, 3, 4, 4, 4, 1, 1]
# maak een run-length encoded versie van A
# (= [(1, 4), (2, 2), (3, 1), (4, 3), (1, 2)])
d. een run-length encoded list (zie 2c.) uitpakt naar een platte list.
A = [(1, 4), (2, 2), (3, 1), (4, 3), (1, 2)]
# pak de run-length encoded list A uit
# (= [1, 1, 1, 1, 2, 2, 3, 4, 4, 4, 1, 1])
In [ ]:
# 3a
A = [[1, 2, 3], 4, 5, [6], [7, 8], 9]
result = []
for elem in A:
if isinstance(elem, list):
for e in elem:
result.append(e)
else:
result.append(elem)
print("Flattened list:", result)
In [ ]:
# 3b
A = [1, 1, 1, 1, 2, 2, 3, 4, 4, 4, 1, 1]
result = []
last_elem = None
for elem in A:
if elem != last_elem:
result.append(elem)
last_elem = elem
print("Duplicaten verwijderd:", result)
In [ ]:
# 3c
A = [1, 1, 1, 1, 2, 2, 3, 4, 4, 4, 1, 1]
result = []
last_elem = None
elem_count = 0
for elem in A:
if elem != last_elem:
if elem_count > 0:
result.append((last_elem, elem_count))
last_elem = elem
elem_count = 1
else:
elem_count += 1
if elem_count > 0:
result.append((last_elem, elem_count))
print("Run-length encoded versie:", result)
In [ ]:
# 3d
A = [(1, 4), (2, 2), (3, 1), (4, 3), (1, 2)]
# pak de run-length encoded list A uit
# (= [1, 1, 1, 1, 2, 2, 3, 4, 4, 4, 1, 1])
result = []
for elem, elem_count in A:
result.extend([elem] * elem_count)
print("Uitgepakte versie van run-length encoded list:", result)
Schrijf een programma dat ...
a. alle elementen in een list dupliceert in dezelfde list, dus zonder een nieuwe list te maken.
A = [1, 2, 3, 4]
# dupliceer de elementen in A (zonder een nieuwe list te maken)
# (A = [1, 1, 2, 2, 3, 3, 4, 4])
b. de elementen van een list een opgegeven aantal plaatsen naar links 'draait'. Elementen die er aan de linkerzijde af zouden vallen, komen rechts terug in de list.
A = list("abcdefgh")
positions = 3
# draai de list A over positions elementen naar links
# (= ["d", "e", "f", "g", "a", "b", "c"])
In [ ]:
# 4a
A = [1, 2, 3, 4]
for i in range(len(A)):
A.insert(2*i, A[2*i])
print("Lijst met gedupliceerde elementen:", A)
In [ ]:
# 4b
A = list("abcdefgh")
positions = 3
# draai de list A over positions elementen naar links
# (= ["d", "e", "f", "g", "a", "b", "c"])
result = A[positions:] + A[:positions]
print("Geroteerde lijst:", result)
In [ ]:
# 5a
import random
A = [1, 3, 5, 7, 8, 9]
count = 3
result = []
for i in range(count):
index = random.randrange(len(A))
result.append(A[index])
del A[index]
print("Willekeurig gekozen elementen:", result)
In [ ]:
# 6a
A = [[1, 2, 3], [4, 5, 6]]
B = [[9, 8, 7], [6, 5, 4]]
result = []
for i in range(len(A)):
row = []
for j in range(len(A[i])):
row.append(A[i][j] + B[i][j])
result.append(row)
print("Som matrix:", result)
In [ ]:
# 6b
A = [[1, 2, 3], [4, 5, 6]]
B = [[9, 8], [7, 6], [5, 4]]
result = []
for i in range(len(A)):
row = []
for j in range(len(A)):
total = 0
for k in range(len(B)):
total += A[i][k] * B[k][j]
row.append(total)
result.append(row)
print("Product matrix:", result)
Als we een matrix niet met een geneste list zouden modelleren,
maar met een platte list, hoe zou je dan een element van de matrix
kunnen aanwijzen?
De afmeting van de matrix is bekend.
Bijvoorbeeld: $$ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} $$ Hoe vind ik nu $A_{r,c}$ ?
In Python:
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
rows, cols = (3, 3) # matrix dimensions
r, c = (1, 2) # 0-based row and column index
# hoe vind ik het element op A(r, c)?
In [ ]:
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
rows, cols = (3, 3) # matrix dimensions
r, c = (1, 2) # 0-based row and column index
index = r * cols + c
print("A(r,c):", A[index])
In het 8-koniginnen-probleem probeer je zoveel mogelijk koniginnen op een schaakbord te plaatsen. De koniginnen mogen niet de mogelijkheid hebben
elkaar te slaan.
Een konigin mag op het schaakbord zowel horizontaal, verticaal als diagonaal lopen.
Een voorbeeld van een geldige oplossing:
a. Op hoeveel mogelijke manieren kun je de 8 koniginnen op de vakjes van het schaakbord plaatsen als je geen rekening hoeft te houden met het slaan?
b. Schrijf een Python programma dat een geldige oplossing van het probleem zoekt en vindt.
In [1]:
# 8a
from IPython.display import display, Latex
from scipy.misc import comb
combinations = comb(64, 8, exact=True)
display(Latex(r"Er zijn 8 koniginnen te verdelen over 64 vakjes:"))
display(Latex(r"$\binom{{64}}{{8}} = {}$".format(combinations)))
In [ ]:
# 8b
# We zouden het schaakbord kunnen modelleren met een
# geneste list, waarbij iedere sublist een rij voorstelt,
# en deze dan vullen met een Q bij ieder vakje waar een
# konigin staat.
# Maar aangezien koniginnen toch nooit in dezelfde kolom
# kunnen staan, kunnen we net zo goed alleen de rijnummers
# van de 8 koniginnen opslaan.
board = [0] * 8
while True:
# oplossing controleren
# koniginnen mogen niet op dezelfde rij staan:
rows_valid = True
for col in range(len(board) - 1):
if board[col] in board[col+1:]:
rows_valid = False
break
if rows_valid:
# koniginnen mogen niet in dezelfde diagonaal staan,
# top-left to bottom-right:
diagonal_tlbr = []
for col in range(len(board)):
# calculate diagonal:
diagonal_tlbr.append(col - board[col])
diagonal_tlbr_valid = True
for d in range(len(diagonal_tlbr) - 1):
if diagonal_tlbr[d] in diagonal_tlbr[d+1:]:
diagonal_tlbr_valid = False
break
if diagonal_tlbr_valid:
# koniginnen mogen niet in dezelfde diagonaal staan,
# bottom-left to top-right:
diagonal_bltr = []
for col in range(len(board)):
# calculate diagonal:
diagonal_bltr.append(col + board[col])
diagonal_bltr_valid = True
for d in range(len(diagonal_bltr) - 1):
if diagonal_bltr[d] in diagonal_bltr[d+1:]:
diagonal_bltr_valid = False
break
if diagonal_bltr_valid:
print("Valid solution:", board)
break
# set up next board:
col = -1
board[col] += 1
while col >= -len(board) and board[col] >= len(board):
board[col] = 1
col -= 1
board[col] += 1
if col < -len(board):
break
else:
print("No valid solution found!")
Schrijf een programma dat ...
a. de geneste lists in een list sorteert op lengte van de geneste list.
A = [
["a", "b", "c"], ["d", "e"],
["f", "g", "h"], ["d", "e"],
["i", "j", "k", "l"], ["m", "n"],
["o"]
]
# maak een nieuwe lijst, waarin de elementen van A
# gesorteerd zijn op lengte van de list
# (= [["o"], ["d", "e"], ["d", "e"], ["m", "n"],
# ["a", "b", "c"], ["f", "g", "h"], ["i", "j", "k", "l"]])
In [ ]:
# 9a
A = [
["a", "b", "c"], ["d", "e"],
["f", "g", "h"], ["d", "e"],
["i", "j", "k", "l"], ["m", "n"],
["o"]
]
sort_order = []
for i in range(len(A)):
sort_order.append((len(A[i]), i))
sort_order.sort()
result = []
for length, i in sort_order:
result.append(A[i])
print("Sorted by length of sublist:", result)
In [ ]: