In een bedrijf worden dozen op een stapel gezet vooraleer ze verwerkt worden. In elke iteratie van het proces gebeurt het volgende:

• Machine 1 zet een aantal nieuwe dozen \(m\) op de stapel, waarbij \(m\) een willekeurig natuurlijk getal is uniform gekozen uit [1,6].
• Daarna neemt machine 2 een willekeurig aantal dozen \(q\) van de stapel en verwerkt ze. Hierbij is \(q\) uniform gekozen uit [1,n], met \(n\) de grootte van de stapel.

We vragen ons af hoeveel iteraties er gemiddeld nodig zullen zijn om \(N\) of meer dozen te verwerken op een initieel lege stapel.

Ontwerp en implementeer een algoritme met dynamisch programmeren voor dit probleem. Bereken hiermee de exacte verwachtingswaarde door gebruik te maken van de wet van de totale kans. Gebruik dus geen simulaties om dit getal te schatten.

Implementeer de interface BoxComputer¹ in een klasse genaamd DynamicBoxComputer. Schrijf een methode double expectedMoves(int desiredBoxes) die teruggeeft wat het verwachte aantal iteraties is tot het gegeven aantal dozen is verwerkt. Tip: je klasse moet niet bij elke functieoproep ‘blanco’ starten: berekende informatie die later ook correct blijft mag je natuurlijk hergebruiken.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen.