Uitwerking tentamen Programmeermethoden 2 augustus 2010

OPGAVE 1
a. bool evenveel (int A[ ], int n) {
     int i, telpos = 0, telneg = 0;
     for ( i = 0; i < n; i++ )
       if ( A[i] >= 0 ) telpos++; else telneg++;
     return ( telpos == telneg ); // of: telpos == n/2
   }//evenveel
b. int epo (bool negpos, int A[ ], int start, int n) {
     int i;
     for ( i = start; i < n; i++ ) 
       if ( ( negpos && A[i] >= 0 ) || ( ! negpos && A[i] < 0 ) ) return i;
     return n;
   }//epo
c. void omenom (int A[ ], int n)  {
     int i, j, temp;
     for ( i = 0; i < n; i++ )
       if ( ( i % 2 == 0 && A[i] < 0 ) || ( i % 2 != 0 && A[i] >= 0 ) ) {
         j = epo (i % 2 == 0,A,i+1,n);
	 temp = A[j]; A[j] = A[i]; A[i] = temp;
       }//if
   }//omenom
d. (n/2-1) + (n/2-2) + ... + 1 + n = n(n/2+3)/4
e. 1 + 2 + ... + (n-1) = n(n-1)/2 vergelijkingen, wat meer is --- maar
   in ordegrootte zijn beide O(n^2).

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 3 en z in cout << func (3,z);
b. T1,2,4 (4x)  4,1,2,5,5   4,1,2,4
c. T1,2,4       1,2,4,2,3   1,2,4,1
d. de bovengrens van de for-loop wordt dan steeds maar groter: oneindige loop,
   of het stopt omdat variabelen dan negatief worden.
e. 0,0,0,1,0   4,1,2,0
f. thierry is geen int-functie, dus het mag niet;
   anders wel OK, mits de eerste parameter van henry call-by-value is (geen &).

OPGAVE 3
a. int kisten (int K[ ][n]) {
     int aantal = 0, i, j;
     for ( i = 0; i < m; i++ )
       for ( j = 0; j < n; j++ )
         aantal += K[i][j];
     return aantal;
   }//kisten
b. int top (int K[ ][n], int & maxi, int & p, int & q) {
     int aantal = 0, i, j; maxi = 0; p = 0; q = 0;
     for ( i = 0; i < m; i++ )
       for ( j = 0; j < n; j++ )
         if ( ( i == 0 || K[i][j] > K[i-1][j] )
	      && ( i == m-1 || K[i][j] > K[i+1][j] )
	      && ( j == 0 || K[i][j] > K[i][j-1] )
	      && ( j == n-1 || K[i][j] > K[i][j+1] ) {
	   aantal++;
	   if ( K[i][j] > maxi ) { maxi = K[i][j]; p = i; q = j; }//if
	 }//if
     return aantal;
   }//top
c. bool ingang (int K[ ][n], int i, int j) {
     return ( ( i == 0 || i == m-1 || j == 0 || j == n-1 ) && K[i][j] == 0 );
   }//ingang
d. bool tezien (int K[ ][n]) {
     int toppen, maxi, p, q, i, j; toppen = top (K,maxi,p,q);
     for ( i = 0; i < m; i++ )
       for ( j = 0; j < n; j++ )
         if ( ingang (K,i,j) && ( p == i || q == j ) )
	   return true;
     return false;
   }//tezien

OPGAVE 4
a. void verwijder (persoon* ingang) {
     persoon* weg;
     if ( ingang != NULL && ingang != ingang->volg ) {
       weg = ingang->volg; ingang->volg = weg->volg; delete weg;
     }//if
   }//verwijder
b. void voegtoe (persoon* & ingang, char name, int age) {
     persoon* nieuw = new persoon; nieuw->naam = name; nieuw->lt = age;
     nieuw->volg = ingang; (*) ingang = nieuw;
   }//voegtoe
c. void sorteer (persoon* & ingang) {
     persoon* hulp; persoon* hulp2;
     if ( ingang != NULL && ingang != ingang->volg 
          && ingang->naam > ingang->volg->naam ) {
       hulp = ingang->volg; hulp2 = ingang->volg->volg;
       if ( ingang != hulp2 ) ingang->volg = hulp2;
       hulp->volg = ingang; ingang = hulp;
     }//if
   }//sorteer
d. Bij b en c moet er een & bij (de ingangspointer gaat veranderen; bij c 
   niet altijd). Bij a hoeft het niet, de pointer verandert niet; het mag wel.
e. persoon* delaatste (persoon* ingang) {
     persoon* hulp = ingang;
     if ( ingang == NULL ) return NULL;
     while ( hulp->volg != ingang ) hulp = hulp->volg;
     return hulp;
   }//delaatste
f. (*): if ( ingang != NULL ) {
          persoon* laat = delaatste (ingang); laat->volg = nieuw; 
	}//if
        else nieuw->volg = nieuw;