UITWERKING Hertentamen Programmeermethoden NA
27 januari 2017

OPGAVE 1

a.

def is_binair(B):
    for b in B:
        if b != 0 and b != 1:
            return False

    return True


b.

def decimaal(B):
    getal = 0

    for b in B:
        getal *= 2
        getal += b

    return getal


Alternatief: een loop op basis van machtsverheffen per vakje, bijvoorbeeld

   getal += B[i] * 2 ** ((len(B) - i - 1)

of:

   getal += B[len(B) - i - 1] * 2 ** i


c.

def optellen(B, C):
    '''Mogen ervan uitgaan dat B en C dezelfde lengte hebben en
    dat de voorste bit 0 is.'''
    A = [0] * (len(B))

    onthouden = 0
    for i in reversed(range(0, len(B))):
        tmp = B[i] + C[i] + onthouden
        onthouden = 0

        # Dit is de "eenvoudige" variant, het kan nog netter met modulo
        # rekenen.
        if tmp == 3:
            onthouden = 1
            A[i] = 1
        elif tmp == 2:
            onthouden = 1
            A[i] = 0
        else:
            A[i] = tmp

    return A


d.

def controle(B, C):
    b_dec = decimaal(B)
    c_dec = decimaal(C)

    tmp = optellen(B, C)
    tmp_dec = decimaal(tmp)

    return b_dec + c_dec == tmp_dec


e.

Opletten: gevraagd is een functie die *aflopend* sorteert, dus de
grootste komt vooraan.


def sorteren(G):
    for i in range(len(G)):
        for j in range(i + 1, len(G)):
            if G[i] < G[j]:
                G[i], G[j] = G[j], G[i]

Alternatief:

  for i in range(1, len(G)):
      for j in range(0, len(G) - i)):
          if G[j] < G[j+1]: ...


f.

def veelvouden(L):
    langste, grootste = 0, -1
    lengte = 0

    for el in L:
        if el % 3 == 0:
            lengte += 1
            if el > grootste:
                grootste = el
        else:
            lengte = 0

        if lengte > langste:
            langste = lengte

    return langste, grootste


OPGAVE 2

a.
Globale variabelen gelden in het gehele programma, en worden in de
regel helemaal bovenin aangemaakt.

Locale variabelen gelden (tijdelijk) alleen in de functie waarin ze
aangemaakt zijn.

Formeel: in functieheading, bijvoorbeeld x, y in def f(x, y):

Actueel: bij aanroep, bijvoorbeeld 3 en z in print func (3,z)


b.

Er wordt een bondige uitleg verwacht van hoe de code wordt uitgevoerd.
De uiteindelijke uitvoer is:

W 3 5 9
W 2 11 27
W 1 23 81
W 0 47 243
W 1 1 25
W 0 3 125
368 3 woef 4


c.

Vereenvoudig eerst "woezel":

  bla = p
  tel = (q - 3) + 1 => q - 2

"q" komt verder alleen voor in het print statement, dus kan worden
genegeerd.

  bla = p
  tel = q - 2
  while tel >= 0:   # q-2, q-1, ..., 0 => dus q - 1 keer
      bla *= p
      tel -= 1
  return bla

Wanneer tel == -1 of kleiner, dan wordt de loop niet uitgevoerd en
is de returnwaarde bla, dus p.
Wanneer tel == 0, dan wordt "bla = p" 1 maal met "p" vermenigvuldigd,
dus "p * p".
Wanneer tel == 1, dan gebeurt dit 2 maal, dus "p * p * p".
Wanneer tel == 2, dan gebeurt dit 3 maal, dus "p * p * p * p".

Nu relateren aan q. Wanneer q == 1 of kleiner, dan wordt het resultaat p.
Wanneer q == 2, dan tel = 0 en dan wordt het resultaat p^2. Voor q == 3,
tel = 1 en resultaat p^3. Enzovoort.

We zien dus dat voor q >= 1, de waarde "bla = p", "q-1" maal met "p" wordt
vermenigvuldigd:  p * p^(q-1) = p^(q)

Dan nu "pip":

  res = woezel((2 * a)/2, b+b-5) + woezel(b-2+2, 3)
  res = woezel(a, 2b - 5) + woezel(b, 3)

Er is gegeven dat b >= 3. Dus 2b - 5 = 2 * 3 - 5 = 1. Hieruit volgt
dat woezel altijd wordt aangeroepen met q >= 1, waardoor geldt dat
woezel p^(q) oplevert. Daarom kunnen we de volgende stap maken:

  res = a ** (b * 2 - 5) + b ** 3

Daarnaast geldt dat "0 * b + 1 = 0"  (altijd). Dus we komen uit op

def molletje(a, b):
    return a ** (b * 2 - 5) + b ** 3

d.
 1. Nee (a en b zijn beide functie-argumenten en dus al lokale variabelen)
 2. Nee (b is een functie-argument en dus al lokale variabele)
 3. Ja (p en c zijn geen functie-argumenten, dus kunnen de globale
        variabelen worden gebruikt.)
 4. Ja (l is in pip geen lokale variabele)


OPGAVE 3

a.  X[:, :]   of   X
b.  X[1, ::3] of X[1, :3:2]
c.  X[:, ::3] of X[:, :3:2]
d.  X[::2,1::3]
e.  X[0,:3] + X[1,:3] + X[2,:3]
of: np.sum(X[:,:3], axis=0)


OPGAVE 4

a.

def mijnen(M):
    aantal = 0
    for i in range(m):
        for j in range(n):
            if M[i,j] == -1:
                aantal += 1

    return aantal

b.

def buren(A, i, j, waarde):
    teller = 0
    gi, gj = -1, -1  # gevonden i en j

    for ii in range(i-1, i+2):
        for jj in range(j-1, j+2):
            if not (ii == i and jj == j) and \
               ii >= 0 and jj >= 0 and ii < m and jj < n:
                   if A[ii, jj] == waarde:
                       teller += 1
                       gi, gj = ii, jj

    return teller, gi, gj

Alternatief: if-condities allemaal uitgeschreven (een hoop gedoe).
Bij een if True *moeten* dan ook de coordinaten van een goede buur worden
onthouden!


c.

def hints(M):
    for i in range(m):
        for j in range(n):
            if M[i, j] != -1:
                M[i, j], di, dj = buren(M, i, j, -1)


d.

def opgelost(M, T):
    for i in range(m):
        for j in range(n):
            # Wanneer een mijn *geen* vlag heeft: puzzel niet opgelost.
            if M[i, j] == -1 and T[i, j] != 2:
                return False
            # Wanneer een niet-mijn een vlag heeft: niet opgelost.
            elif M[i, j] != -1 and T[i, j] == 2:
                return False

    return True


e.

def vlagbaar(M, T):
    for i in range(m):
        for j in range(n):
            if T[i,j] == 1:  # een al geopend vakje
                dicht, ii, jj = buren(T, i, j, 0)
                vlag, di, dj = buren(T, i, j, 2)

                if dicht == M[i, j] - vlag:
                    return ii, jj

    return -1, -1