Uitwerking Tentamen Programmeermethoden 10 maart 2016

OPGAVE 1
a. bool gesorteerd (int A[ ], int n) {
     int i;
     for ( i = 0; i < n-1; i++ ) if ( A[i] > A[i+1] ) return false;
     return true;
   }//gesorteerd
b. int hoe (int A[ ], int n ) {
     int i, teller = 0;
     for ( i = 2; i < n; i++ ) if ( A[i] == A[i-1] + A[i-2] ) teller++;
     return teller;
   }//hoe
c. void bouw (int A[ ], int n, int X, int Y) { // n >= 2
     int i;  // met hoe-waarde: n-2
     A[0] = X; A[1] = Y;
     for ( i = 2; i < n; i++ ) A[i] = A[i-1] + A[i-2];
   }//bouw
d. void busort (int A[ ], int n, int k) {
     int ronde, i, 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
       if ( ronde % k == 0 && gesorteerd (A,n) ) return;
     }//for
   }//busort
e. Bij een al gesorteerd rijtje: k doorgangen (rondes), en 1 controle, dus:
   n-1 + n-2 + ... + n-k + (n-1) = k(2n-k-1)/2 + n-1.
   Bij een omgekeerd gesorteerd rijtje n-1 doorgangen, en controles, dus:
   n-1 + ... + 2 + 1 + (n-1)(n-1)/k = (n-1)(n/2+(n-1)/k).

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. 5,3,5   4,3,5   3,3,5   5,3,3   36   5,6,3
c. Algemeen w (u+v+(w-1)/2) --> 3 (u+v+1)
d. 5,3,5   2,5,5   4,5,2   4,5,2   36   4,5,2
e. 4,4,4   3,3,3   2,2,2   2,2,2   27   2,6,3 
f. Als er een prototype van sergio boven ennio staat. En de twee eerste 
   parameters van sergio moeten call-by-value zijn (want 42 is geen l-value).
   En je krijgt een warning, want je negeert de return-waarde van sergio.

OPGAVE 3
a. bool land (int L[ ][n], int & rij) {
     int i, j; bool okee; rij = -1;
     for ( i = 0; i < m; i++ ) {
       okee = true;
       for ( j = 0; j < n; j++ ) if ( L[i][j] == 0 ) okee = false;
       if ( okee ) rij = i;
     }//for
     return ( rij != -1 );
   }//land
b. int toppen (int L[ ][n], int & hoog) {
     int i, j, aantal = 0; hoog = 0;
     for ( i = 1; i < m-1; i++ ) for ( j = 1; j < n-1; j++ )
       if ( L[i][j] >= L[i-1][j] && L[i][j] >= L[i+1][j]
	    && L[i][j] >= L[i][j-1] && L[i][j] >= L[i][j+1] ) {
	 aantal++;
	 if ( L[i][j] > hoog ) hoog = L[i][j];
       }//if
     return aantal;
   }//toppen
c. int zee (int L[ ][n], int i, int j) {
     int tel = 1; bool doorgaan = true; L[i][j] = -1;
     while ( doorgaan) {
       doorgaan = false;
       for ( i = 0; i < m; i++ ) for ( j = 0; j < n; j++ )
	 if ( L[i][j] == -1 ) {
	   if ( i-1 >= 0 && L[i-1][j] == 0 ) { 
	     L[i-1][j] = -1; tel++; doorgaan = true; }//if
	   if ( i+1 < m && L[i+1][j] == 0 ) { 
	     L[i+1][j] = -1; tel++;  doorgaan = true; }//if
	   if ( j-1 >= 0 && L[i][j-1] == 0 ) { 
	     L[i][j-1] = -1; tel++;  doorgaan = true; }//if
	   if ( j+1 < n && L[i][j+1] == 0 ) { 
	     L[i][j+1] = -1; tel++;  doorgaan = true; }//if
         }//if
     }//while
     for ( i = 0; i < m; i++ ) for ( j = 0; j < n; j++ )
       if ( L[i][j] == -1 ) L[i][j] = 0;
     return tel;
   }//zee

OPGAVE 4
a. void voegtoe (mens* & eerste, int mensnr, char mensnm) {
     mens* nieuw = new mens;
     nieuw->nr = mensnr; nieuw->naam = mensnm; 
     nieuw->volg = eerste; nieuw->vvorig = NULL;
     if ( eerste != NULL && eerste->volg != NULL ) eerste->volg->vvorig = nieuw;
     eerste = nieuw;
   }//voegtoe
b. void verwijder (mens* eerste) {
     mens* weg;
     if ( eerste != NULL && eerste->volg != NULL ) {
       weg = eerste->volg; eerste->volg = weg->volg; delete weg;
       if ( eerste->volg != NULL ) {
         eerste->volg->vvorig = NULL;
	 if ( eerste->volg->volg != NULL )
	   eerste->volg->volg->vvorig = eerste;
       }//if
     }//if
   }//verwijder
c. void verwissel (mens* & eerste) {
     mens* p = eerste; mens* q;
     if ( eerste != NULL && eerste->volg != NULL 
          && eerste->naam > eerste->volg->naam ) {
       q = eerste->volg; p->volg = q->volg; q->volg = p;
       eerste = q;
     }//if
   }//verwissel
d. Bij a en c moet: de ingangspointer kan daar gaan veranderen. Bij b hoeft het
   niet (het maakt overigens niet uit), de ingangspointer verandert toch niet.
e. mens* achteraan (mens* eerste, int t) {
     mens* p = eerste; int i;
     if ( eerste != NULL ) { //overbodige test
       while ( p->volg != NULL ) p = p->volg;
       for ( i = 0; i < t/2; i++ ) p = p->vvorig;
       if ( p == NULL ) { p = eerste; }//if
       else if ( t % 2 == 0 ) p = p->volg;
       return p;
     }//if
   }//achteraan