Uitwerking tentamen Programmeermethoden 16 maart 2017

OPGAVE 1
a. int groter (int A[ ], int i, int n) {
     int j, teller = 0;
     for ( j = 0; j < n; j++ )
       if ( A[j] > A[i] )
         teller++;
     return teller;
   }//grotere
b. int mediaan (int A[ ], int n) {
     int i;
     for ( i = 0; i < n; i++ )
       if ( grotere (A,i,n) == n / 2 )
         return A[i];
   }//mediaan
c. void sorteer (int A[ ], int n) {
     int i, temp, pos;
     for ( i = 0; i < n; i++ ) { // of i < n-1
       pos = n - 1 - groter (A,i,n);
       while ( pos != i ) {
         temp = A[i]; A[i] = A[pos]; A[pos] = temp;
         pos = n - 1 - groter (A,i,n);
       }//while
     }//for
   }//sorteer
d. De functie groter doet n vergelijkingen tussen array-elementen per
   aanroep. Bij c worden er dat in totaal tussen n * n (precies bij een 
   al gesorteerd rijtje) en 2 * (n-1) * n. Dat is meer dan de gewone 
   bubblesort (die doet er n(n-1)/2), maar het blijft kwadratisch.

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. 0 3 1 5  1 1 3 7  2 3 1 5  3 1 3 7  7 1 3
c. 0 1 3 5  1 1 3 3  2 1 3 1  3 1 3 -1  -1 1 3 
d. 0 0 0 7  1 0 0 7  2 0 0 7  3 0 0 7  7  0
e. altijd 7, resp. 7 - 4(s-r)


OPGAVE 3
a. bool reis (int afstand[ ][n], int km) {
     int i, j, k;
     for ( i = 0; i < n-2; i++ )
       for ( j = i+1; j < n-1; j++ )
         for ( k = j+1; k < n; k++ )
           if ( afstand[i][j] + afstand[j][k] + afstand[k][i] == km ) 
	     return true;
     return false;
   }//reis
b. int verste (int afstand[ ][n], int i) {
     int k, ver = -1, verweg;
     for ( k = 0; k < n; k++ )
       if ( afstand[i][k] >= ver ) {
         ver = afstand[i][k]; verweg = k;
       }//if
     return verweg;
   }//verste
c. int hoever (int afstand[ ][n], int i) {
     int afst = 0, j;
     bool geweest[n];
     for ( j = 0; j < n; j++ ) geweest[j] = false;
     while ( ! geweest[i] ) {
       geweest[i] = true; j = verste (afstand,i);
       afst += afstand[i][j]; i = j;
     }//while
     return afst;
   }//hoever

OPGAVE 4
a. void verwijder (paard* & draai) {
     paard* vor; paard* vol;
     if ( draai != NULL && ! draai->bezet ) {
       vor = draai->vorige; vol = draai->volgende;
       if ( vor != draai ) {
         delete draai; draai = vol;
         vol->vorige = vor; vor->volgende = vol; }//if
       else { delete draai; draai = NULL; }//else
     }//if
   }//verwijder
b. void voegtoe (paard* & draai, bool paardbez) {
     paard* nieuw = new paard;
     nieuw->bezet = paardbez; nieuw->volgende = draai;
     nieuw->vorige = draai->vorige; draai->vorige = nieuw; 
     nieuw->vorige->volgende = nieuw; draai = nieuw;
   }//voegtoe
c. void wissel (paard* draai) {
     bool temp;
     if ( draai != NULL ) {
       temp = draai->bezet; draai->bezet = draai->volgende->bezet;
       draai->volgende->bezet = temp; }//if
   }//wissel
d. Bij a en b moet er een & bij, de ingangspointer gaat immers wijzigen.
   Bij c mag het, maar het hoeft niet. De ingangspointer wijzigt niet.
e. void draaiom (paard* draai) {
     paard* p = draai; paard* q;
     if ( draai == NULL ) return;
     do {
       q = p->volgende; p->volgende = p->vorige; 
       p->vorige = q; p = q;
     } while ( p != draai );
   }//draaiom