Basis: algoritmen¶

Deze pagina bevat uitvoerbare code.

De nacht van het nijlpaard¶

Opdracht: De nacht van het nijlpaard

Stap 1: `far_enough(a, b, distance)`¶

def far_enough(a, b, distance):
    """Geeft True als plaats b minstens distance verder ligt dan plaats a."""
    return b - a >= distance


assert far_enough(1, 3, 2) == True
assert far_enough(2, 3, 2) == False
assert far_enough(3, 3, 1) == False
assert far_enough(5, 10, 5) == True

Stap 2: `drop_too_close(place, places, distance)`¶

Zodra één plaats ver genoeg ligt, stopt de recursie: de plaatsen daarna liggen nog verder weg.

def drop_too_close(place, places, distance):
    """Geeft places zonder de plaatsen aan het begin die te dicht bij place liggen."""
    if places == []:  # basisgeval
        return []
    elif far_enough(place, places[0], distance):  # basisgeval: ver genoeg
        return places
    else:  # recursief geval: de eerste plaats ligt te dichtbij
        return drop_too_close(place, places[1:], distance)


assert drop_too_close(1, [3, 7], 2) == [3, 7]
assert drop_too_close(3, [3, 5, 8], 4) == [8]
assert drop_too_close(1, [3, 5, 10, 12], 4) == [5, 10, 12]
assert drop_too_close(5, [6, 7], 3) == []
assert drop_too_close(5, [], 2) == []

Stap 3: `hippo_dinner(distance, places)`¶

def hippo_dinner(distance, places):
    """Geeft hoeveel nijlpaarden er hoogstens mee-eten op de plaatsen in places."""
    if places == []:  # basisgeval
        return 0

    first = places[0]
    rest = places[1:]

    use_it = 1 + hippo_dinner(distance, drop_too_close(first, rest, distance))
    lose_it = hippo_dinner(distance, rest)
    return max(use_it, lose_it)


assert hippo_dinner(1, [2, 3, 3]) == 2
assert hippo_dinner(2, [1, 3, 7]) == 3
assert hippo_dinner(4, [1, 3, 5, 10, 12]) == 3
assert hippo_dinner(3, [4]) == 1
assert hippo_dinner(3, []) == 0