Enige opmerkingen/tips bij de derde programmeeropgave.


1. Voor een flink aantal testgevallen: 
zie http://www.liacs.nl/home/mwitsenb/Algoritmiek

2. Er dient een 2-dimensionaal array handen gevuld te worden. Hierin
correspondeeert handen[i][j] met het probleem waarin personen i t/m j
(i<j) elkaar (zonder te kruisen) twee aan twee een hand moeten geven. 
We zoeken een oplossing (bestaande uit (j-i+1)/2 paren handenschudders)
waarvoor het aantal handengevende paren dat 
hetzelfde studeert maximaal is. Handen[i][j] is dat maximale aantal.

3. Aangezien i<j hoeft alleen de rechter bovendriehoek van het 
gebruikte array gevuld te worden. En overigens bestaat er sowieso 
alleen maar een oplossing als j-i+1, het aantal personen in de cirkel, 
even is.

3. Het array-element handen[i][j] wordt bepaald door j een voor een alle
personen k (k=i,i+2,..,j-1) een hand te laten geven. Het probleem
corresponderend met handen[i][j] wordt daarmee voor elke k teruggebracht
tot twee deelproblemen (corresponderend met twee arrayelementen).  
Door over deze k te maximaliseren vind je het gevraagde optimale aantal.

4. Je kunt het array kolom voor kolom vullen, of rij voor rij, of diagonaal
voor diagonaal,... Let wel goed op de volgorde van de berekening: wat heb je 
nodig om handen[i][j] te bepalen? Dus wat moet je al berekend hebben 
voordat je handen[i][j] kunt berekenen?

5. De makkelijke gevallen: onder andere handen[i][i+1]. Daar hebben we te 
maken met 2 personen, dus een optimaal aantal is eenvoudig te geven.

6. Voor het vinden van een optimale oplossing zelf is het het makkelijkst
om nog een array paren bij te houden, die tegelijk met handen gevuld wordt.
In paren[i][j] komt dan degene te staan die in een optimale oplossing de
hand van j schudt. 

7. Merk op dat als het optimale aantal "goede paren handengevers" 0 is,
elke serie paren die aan de restricties voldoet een oplossing is 
corresponderend met die 0; bijvoorbeeld ook (1,2)(3,4)(5,6),...,(n-1,n).

8. Het afdrukken van een optimale oplossing kun je het makkelijkst recursief
doen, gebruikmakend van het array paren.

9. Vergeet niet in het verslag duidelijk uit te leggen hoe je aan je aan 
je recurrente betrekking komt, hoe je door het array loopt en waarom zo,
etcetera. Zie voor de beoogde inhoud van je verslag de opdracht zelf.