Basis: algoritmen

Deze pagina bevat uitvoerbare code. Activeren

De nacht van het nijlpaard

Nijlpaarden houden van een goede maaltijd, maar ze willen wel ruimte om zich heen. Elke nacht zet de kok maaltijden op een lange tafel. Aan één kant van de tafel zijn de plaatsen genummerd: 1, 2, 3, enzovoort. Op een plaats kan meer dan één maaltijd staan. De ceremoniemeester bepaalt hoeveel ruimte er tussen de nijlpaarden moet zijn, en zorgt dat er zoveel mogelijk nijlpaarden mee-eten. In deze opgave reken je uit hoeveel dat er zijn.

De regel

Een nijlpaard gaat zitten op een plaats waar een maaltijd staat. De afstand tussen twee nijlpaarden is het verschil van hun plaatsnummers, en die moet minstens gelijk zijn aan de afstand die de ceremoniemeester heeft gekozen. Op één plaats zit hoogstens één nijlpaard.

Gekozen afstand	Plaatsen met een maaltijd	Zoveel nijlpaarden eten mee	Bijvoorbeeld op
1	2, 3, 3	2	2 en 3
2	1, 3, 7	3	1, 3 en 7
4	1, 3, 5, 10, 12	3	1, 5 en 12

Bij afstand 2 zit er dus minstens één lege plaats tussen twee nijlpaarden. In het laatste voorbeeld kunnen er geen vier mee-eten: welke vier plaatsen je ook kiest, er liggen er altijd twee minder dan 4 uit elkaar.

De plaatsen staan in deze opgave altijd oplopend in de lijst.

Wat je gaat maken

Stap	Functie	Doet	Wat je oefent
1	far_enough	liggen twee plaatsen ver genoeg uit elkaar?	geen recursie
2	drop_too_close	haal de plaatsen weg die te dicht bij een nijlpaard liggen	één recursieve aanroep
3	hippo_dinner	hoeveel nijlpaarden kunnen er hoogstens mee-eten?	use it or lose it

Stap 1: far_enough(a, b, distance)

Geeft True als plaats b minstens distance verder ligt dan plaats a, en anders False. b is nooit kleiner dan a. Deze functie heeft geen recursie nodig.

Aanroep	Resultaat
far_enough(1, 3, 2)	True
far_enough(2, 3, 2)	False
far_enough(3, 3, 1)	False

Hint

Het verschil tussen de twee plaatsen is b - a.

# jouw oplossing

# jouw oplossing

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

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)

Er zit een nijlpaard op plaats place. places is een oplopende lijst met de plaatsen erna. Geeft de lijst terug zonder de plaatsen aan het begin die te dicht bij place liggen. Vanaf de eerste plaats die ver genoeg ligt, blijft de lijst staan.

Aanroep	Resultaat
drop_too_close(1, [3, 7], 2)	[3, 7]
drop_too_close(3, [3, 5, 8], 4)	[8]
drop_too_close(5, [], 2)	[]

Hint

Gebruik far_enough uit stap 1. Ligt de eerste plaats ver genoeg, dan ben je klaar: dan geef je de hele lijst terug. Omdat de lijst oplopend is, liggen de plaatsen daarna nog verder weg.

# jouw oplossing

# jouw oplossing

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) == []

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)

places is een oplopende lijst met de plaatsen waar een maaltijd staat. Geeft terug hoeveel nijlpaarden er hoogstens kunnen mee-eten als de afstand tussen twee nijlpaarden minstens distance moet zijn. Gebruik recursie.

Aanroep	Resultaat
hippo_dinner(1, [2, 3, 3])	2
hippo_dinner(2, [1, 3, 7])	3
hippo_dinner(4, [1, 3, 5, 10, 12])	3
hippo_dinner(3, [])	0

Hint

Kies bij de eerste plaats, zoals bij subset in het college:

• Use it: er gaat een nijlpaard op de eerste plaats zitten. Dat is er één, plus zoveel als er passen op de rest, nadat je met drop_too_close de plaatsen hebt weggehaald die te dicht bij de eerste liggen.

• Lose it: op de eerste plaats gaat niemand zitten. Dan tel je zoveel als er op de rest passen.

Geef het grootste van de twee terug.

# jouw oplossing

# jouw oplossing

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

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

Tot slot

Bij afstand 4 en maaltijden op 1, 3, 5, 10 en 12 eten er drie nijlpaarden mee. Of je de eerste plaats moet gebruiken, kon hippo_dinner niet vooraf weten. Pas door beide keuzes te proberen vond de functie het beste antwoord, precies zoals subset in het college.

hippo_dinner zegt hoeveel nijlpaarden er mee-eten, maar niet op welke plaatsen. Hoe je ook de gekozen elementen terugkrijgt, zie je aan het eind van het tweede college.

(Informatica Olympiade 2023-2024)