UITWERKING TENTAMEN 14 maart 2019

OPGAVE 1
a. void klgr (int A[ ], int start, int einde, int & kl, int & gr) {
     int i = start;
     if ( A[i] > A[i+1] ) { gr = i; kl = i+1; }//if
     else { gr = i+1; kl = i; }//else
     for ( i = start + 2; i <= einde; i++ )
       if ( A[i] > A[gr] ) gr = i;
       else if ( A[i] < A[kl] ) kl = i;
   }//klgr
b. bool palindroom (int A[ ], int n) {
     int i;
     for ( i = 0; i < n/2; i++ )
       if ( A[i] != A[n-1-i] ) return false;
     return true;
   }//palindroom
c. void sorteer (int A[ ], int n) {
     int start, gr, kl, temp;
     for ( start = 0; start < n/2; start++ ) {
       klgr (A,start,n-1-start,kl,gr);
       temp = A[start]; A[start] = A[kl]; A[kl] = temp;
       if ( kl != start || gr != n-1-start ) {
         temp = A[n-1-start]; A[n-1-start] = A[gr]; A[gr] = temp;
       }//if
     }//for
   }//sorteer
d. Beide methoden zijn O(n^2), dus even goed/slecht. Preciezer: de methode
   van c doet (via a) n-1 + n-2 + ... + 1 = n(n-1)/2 vergelijkingen in 
   het slechtste geval, net als bubblesort (altijd).

OPGAVE 2
a. Globale variabelen gelden in het gehele programma, en worden helemaal
   bovenin aangemaakt. Locale variabelen gelden (tijdelijk) alleen in de
   functie waarin ze aangemaakt zijn.
   Variabelen kunnen call by value en call by reference worden 
   meegegeven aan een functie. Bij call by value gaat alleen de waarde 
   van de parameter naar de functie, alwaar een locale variabele deze
   waarde opvangt, en er met deze locale variabele wordt verder 
   gerekend. De oorspronkelijk variabele behoudt zijn waarde. Bij call 
   by reference (&) gaat als het ware de variabele zelf naar de functie,
   en kan dan ook blijvend veranderd worden. Eigenlijk wordt het adres 
   (de reference) doorgegeven. Formeel: in functieheading, bijvoorbeeld 
   x, y in  int f (int x, bool y) { ...
   Actueel: bij aanroep, bijvoorbeeld r en y in z = f (r,y);
b. 13,6,2,5 <LF> 19,4,5 <LF> (<LF> is LineFeed)
c. 13,7,4,6 <LF> 20,4,6 <LF>
d. 13,5,6,6 <LF> 18,6,1 <LF>
e. Dan moet er een prototype van april boven maart staan, en de eerste en
   tweede parameter van maart en de eerste van april moeten call bij value 
   zijn (zonder &), want april (maart (p,y),y) is geen l-value, etc.

OPGAVE 3
a. double loop (int P[ ][n], int i, int w) {
     int j, passagiers = 0; double som = 0;
     for ( j = 0; j < n; j++ ) {
       if ( j - w > 0 ) som += P[i][j] * ( 10 + 20 * ( j - w ) );
       else som += P[i][j] * ( 10 + 20 * ( w - j ) );
       passagiers += P[i][j];
     }//for
     return som / passagiers;
   }//loop
b. void verdeel (int P[ ][n], int i, int w) {
     int kl, i1, w1;
     if ( P[i][w] > 10 ) {
       if ( i >= 1 ) { kl = P[i-1][w]; i1 = i-1; w1 = w;}//if
       else { kl = P[i+1][w]; i1 = i+1; w1 = w; }//else
       if ( w >= 1 && P[i][w-1] < kl ) { 
         kl = P[i][w-1]; i1 = i; w1 = w-1; }//if
       if ( w < n-1 && P[i][w+1] < kl ) { 
         kl = P[i][w+1]; i1 = i; w1 = w+1; }//if
       if ( i < m-1 && P[i+1][w] < kl ) { 
         kl = P[i+1][w]; i1 = i+1; w1 = w; }//if
       P[i1][w1] += 10; P[i][w] -= 10;
     }//if
   }//verdeel
c. int beste (int P[ ][n], int & afst) {
     int i, w, langste;
     for ( w = 0; w < n; w++ ) {
       langste = loop (P,0,w);
       for ( i = 1; i < m; i++ )
         if ( loop (P,i,w) > langste ) langste = loop (P,i,w);
       if ( w == 0 || langste < afst ) { 
         afst = langste; antwoord = w; }//if  
     }//for
     return antwoord;
   }//beste

OPGAVE 4
a. void voegtoe (object* & ingang, char kar) {
     object* nieuw = new object; 
     if ( 'a' <= kar && kar <= 'z' ) kar = (char) ( kar - 'a' + 'A' );
     nieuw->info = kar; nieuw->volgA = ingang; nieuw->volgB = ingang;
     ingang = nieuw;
   }//voegtoe
b. void verwijder (object* & ingang) {
     object* weg = ingang;
     if ( ingang != NULL && '0' <= ingang->info && ingang->info <= '9' 
          && ( ingang->info - '0' ) % 2 == 0 ) {
       if ( ingang->volgA == NULL ) ingang = ingang->volgB;
       else ingang = ingang->volgA;
       delete weg;
     }//if
   }//verwijder
c. void pasaan (object* ingang) {
     if ( ingang != NULL 
          && ( ingang->volgA != NULL || ingang->volgB != NULL ) )
       if ( ingang->volgA != NULL ) ingang->volgA->info = ingang->info;
       else ingang->volgB->info = ingang->info;
   }//pasaan
d. Bij a en b moet de ingangspointer (doorgaans) wijzigen, dus moet er een
   & bij; bij c maakt het niet uit, de ingangspointer wijzigt toch niet.
e. void repareer (object* ingang) {
     object* p = ingang; object* q;
     while ( p != NULL ) {
       q = ingang;
       while ( q != p ) {
         if ( q == p->volgA ) p->volgA = p->volgB;
         if ( q == p->volgB ) p->volgB = p->volgA;
	 q = q->volgA;
       }//while
       p = p->volgA;
     }//while
   }//repareer