Uitwerking tentamen Programmeermethoden donderdag 17 december 2009

OPGAVE 1
a. double gem (int A[ ], int n) {
     int i; double som = 0; for ( i = 0; i < n; i++ ) som += A[i];
     return som / n;
   }//gem
b. bool groter (int X, int t, int A[ ], int n) {
     int tel = 0, i;
     for ( i = 0; i < n; i++ )
       if ( A[i] > X ) { tel++; if ( tel > t ) return false; }//if
       else if ( tel+n-i-1 < t ) return false;
     return true;
   }//groter
c. int mediaan (int A[ ], int n) {
     int i;
     for ( i = 0; i < n; i++ )
       if ( groter (A[i],n/2,A,n) ) return A[i];
   }//mediaan
d. void sort (int A[ ], int n) {
     int i, ronde, temp;
     for ( ronde = 1; ronde < n; ronde++ )
       for ( i = 0; i < n-ronde; i++ )
         if ( A[i] > A[i+1] ) { 
	   temp = A[i]; A[i] = A[i+1]; A[i+1] = temp; }//if
   }//sort
e. Beide methodes zijn ongeveer even efficient. Het sorteren kost
   altijd (n-1)+...+2+1 = n(n-1)/2 vergelijkingen. Als de mediaan
   achteraan staat, kost de methode van c ongeveer evenveel.
   Staat de mediaan op plek 0, dan kost het n-1 vergelijkingen.
   De methode van c is dus vaak (wat) beter.

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 7 en y in z = f (7,y);
b. Som   3 en 3   Product   3 en 12   Product   3 en 48   51, 3 en 0
c. Som   2 en 3   Product   2 en 9    11, 2 en 9
d. Als ( i < b) op de plaats staat van een call by reference parameter (met &)
   mag het niet: daar moet namelijk een "l-value" staan. Bij call by value
   mag het wel.
e. De bovengrens van de for-loop wordt dan groter en groter, er ontstaat
   een oneindige loop, die misschien gebroken wordt doordat a over
   INT_MAX heen schiet en dan negatief wordt.

OPGAVE 3
a. void uitbreiden (int bebouwing[ ][n], int i, int j, int X) {
     if ( bebouwing[i][j] != X ) return;
     if ( i > 0 && bebouwing[i-1][j] == 0 ) bebouwing[i-1][j] = X;
     if ( i < m-1 && bebouwing[i+1][j] == 0 ) bebouwing[i+1][j] = X;
     if ( j > 0 && bebouwing[i][j-1] == 0 ) bebouwing[i][j-1] = X;
     if ( j < n-1 && bebouwing[i][j+1] == 0 ) bebouwing[i][j+1] = X;
   }//uitbreiden
b. bool bereikbaar (int bebouwing[ ][n], int i, int j, int p, int q) {
     int temp = bebouwing[i][j], r, a, b; bool okee;
     bebouwing[i][j] = -1;
     for ( r = 1; r <= m*n; r++ ) // of zolang er nog iets gebeurde
       for ( a = 0; a < m; a++ ) for ( b = 0; b < n; b++ )
         uitbreiden (bebouwing,a,b,-1);
     okee = ( p > 0 && bebouwing[p-1][q] == -1 )
            || ( p < m-1 && bebouwing[p+1][q] == -1 )
	    || ( q > 0 && bebouwing[p][q-1] == -1 )
	    || ( q < n-1 && bebouwing[p][q+1] == -1 );
     bebouwing[i][j] = temp;
     for ( a = 0; a < m; a++ ) for ( b = 0; b < n; b++ )
       if ( bebouwing[a][b] == -1 ) bebouwing[a][b] = 0;
     return okee;
   }//bereikbaar
c. bool goedzo (int bebouwing[ ][n]) {
     int i, j, p, q;
     for ( i = 0; i < m; i++ ) for ( j = 0; j < n; j++ )
       for ( p = 0; p < m; p++ ) for ( q = 0; q < n; q++ )
         if ( bebouwing[i][j] != 0 && bebouwing[p][q] !=  0 
            && ( i != p || j != q )
	    && ! bereikbaar (bebouwing,i,j,p,q) ) return false;
     return true;
   }//goedzo

OPGAVE 4
a. void verwissel (dag* jan2010) {
     int tempint; char tempchar;
     if ( jan2010 != NULL && jan2010->volg != NULL &&
          jan2010->datum > jan2010->volg->datum ) {
       tempchar = jan2010->naam; jan2010->naam = jan2010->volg->naam;
       jan2010->volg->naam = tempchar; tempint = jan2010->datum; 
       jan2010->datum = jan2010->volg->datum; jan2010->volg->datum = tempint;
     }//if
   }//verwissel
   Alternatief (en dan met er een & bij):
       dag* p = jan2010->volg; jan2010->volg = p->volg; p->volg = jan2010;
       p->vorig = NULL; jan2010->vorig = p; jan2010 = p; 
       if ( jan2010->volg != NULL ) jan2010->volg->vorig = jan2010;
b. void voegtoe (dag* & jan2010, char nm, int dt) {
     dag* nieuw = new dag; 
     nieuw->vorig = NULL; nieuw->naam = nm; nieuw->datum = dt;
     if ( jan2010 != NULL ) jan2010->vorig = nieuw;
     nieuw->volg = jan2010; jan2010 = nieuw;
   }//voegtoe
c. void verwijder (dag* jan2010) {
     dag* p;
     if ( jan2010 != NULL && jan2010->volg != NULL ) {
       p = jan2010->volg;
       if ( p->volg != NULL ) p->volg->vorig = jan2010;
       jan2010->volg = p->volg; delete p; }//if
   }//verwijder
d. Bij b moet er een & bij (de ingangspointer gaat veranderen). Bij a en c
   hoeft het niet (bij a wel als je de pointers verwisselt).
e. dag* kleiner (dag* jan2010) {
     dag* p = jan2010;
     while ( p != NULL ) {
       if ( p->vorig != NULL && p->vorig->datum > p->datum ) return p;
       p = p->volg; }//while
     return NULL;
   }//kleiner