Uitwerking tentamen Programmeermethoden 23 februari 2011

OPGAVE 1
a. int telkl (int A[ ], int X, int n) {
     int i, teller = 0;
     for ( i = 0; i < n; i++ ) if ( A[i] <= X ) teller++;
     return teller;
   }//telkl
b. int tel (int A[ ], int X, int n) {
     return ( telkl (A,X,n) - telkl (A,X-1,n) );
   }//tel
c. bool perm (int A[ ], in B[ ], int n) {
     int i;
     for ( i = 0; i < n; i++ )
       if ( tel (A,A[i],n) != tel (B,A[i],n) ) return false;
     return true;
   }//perm
d. void sorteer (int A[ ], int B[ ], int n) {
     int i, j, aantal, positie;
     for ( i = 0; i < n; i++ ) {
       positie = telkl (A,A[i],n); aantal = tel (A,A[i],n);
       for ( j = 0; j < aantal; j++ ) B[positie-j-1] = A[i];
     }//for
   }//sorteer
e. De methode van d is vergeljkbaar met bubblesort: kwadratisch aantal
   vergelijkingen (maar wel meer).

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: x, y in  int f (int x, bool y) { ...
   Actueel: bij aanroep, bijvoorbeeld 7 en y in z = f (7,y);
b. S 3 3 2   S 2 6 1   S 1 9 0   S 3 3 2   S 2 6 1   S 1 9 0   
   1 18 3   18 4 en 2
c. int John (int a, int b) { return ( a + b ) * ( a - 1 ); }//John
   (Sarah (x,y) levert x * y op.)
d. De volgorde van evaluatie bij optellen (+) ligt in C++ niet vast.
   Eerst Sarah (b,a):   S 3 3 2   S 2 6 1   S 1 9 0   1 9 3   9 9 en 3
   Eerst Sarah (a,a):   S 3 3 2   S 2 5 1   S 1 6 0   1 6 3   6 6 en 3
e. Als het call by value is (zonder &) mag het, anders (call by reference, 
   met &) niet: y-x en y+x zijn geen l-values.

OPGAVE 3
a. void opvolger (char puzzel[ ][n], char letter, int & p, int & q) {
     int i, j; char zover = (char)((int)('z') + 1); p = -1; q = -1;
     for ( i = 0; i < m; i++ ) for ( j = 0; j < n; j++ )
       if ( letter < puzzel[i][j] && puzzel[i][j] < zover ) {
         zover = puzzel[i][j]; p = i; q = j;
       }//if
   }//opvolger
b. void alpha (char puzzel[ ][n]) {
     int i, j, t; char letter = (char)((int)('a') - 1);
     for ( t = 0; t < m*n; t++ ) {
       opvolger (puzzel,letter,i,j); letter = puzzel[i][j]; cout << letter;
     }//for
   }//alpha
c. bool komtvoor (char puzzel[ ][n], char een, char twee) {
     int i, j;
     for ( i = 0; i < m; i++ ) for ( j = 0; j < n-1; j++ )
       if ( ( puzzel[i][j] == een && puzzel[i][j+1] == twee )
            || ( puzzel[i][j] == twee && puzzel[i][j+1] == een ) )
	 return true;
     for ( i = 0; i < m-1; i++ ) for ( j = 0; j < n; j++ )
       if ( ( puzzel[i][j] == een && puzzel[i+1][j] == twee )
            || ( puzzel[i][j] == twee && puzzel[i+1][j] == een ) )
	 return true;
     return false;
   }//komtvoor

OPGAVE 4.
a. void voegtoe (element* & matrix, int jaar1, int jaar2) {
     element* nieuw1 = new element; element* nieuw2 = new element;
     nieuw1->jaar = jaar1; nieuw2->jaar = jaar2;
     nieuw1->onderboven = nieuw2; nieuw2->onderboven = nieuw1;
     nieuw1->rechts = matrix;
     if ( matrix != NULL ) nieuw2->rechts = matrix->onderboven;
     else nieuw2->rechts = NULL;
     matrix = nieuw1;
   }//voegtoe
b. void verwissel (element* matrix) {
     int temp;
     if ( matrix != NULL ) {
       if ( matrix->rechts == NULL 
            || matrix->rechts->jaar < matrix->onderboven->jaar ) {
         temp = matrix->onderboven->jaar; 
	 matrix->onderboven->jaar = matrix->jaar; matrix->jaar = temp;
       }//if
       else {
         temp = matrix->rechts->jaar; matrix->rechts->jaar = matrix->jaar;
	 matrix->jaar = temp;
       }//else
     }//if
   }//verwissel
c. void verwijder (element* & matrix) {
     element* weg = matrix;
     if ( matrix != NULL ) {
       matrix = matrix->rechts; delete weg->onderboven; delete weg;
     }//if
   }//verwijder
d. Bij de functie van a verandert de ingangspointer, bij die van c
   doorgaans ook: er moet dus een & bij. Bij de functie van b verandert
   de ingangspointer niet, en hoeft er geen & bij (het mag wel).
e. int verschil (element* & matrix) {
     int resultaat = -1; element* loper = matrix;
     while ( loper != NULL ) {
       if ( loper->jaar - loper->onderboven->jaar > resultaat )
         resultaat = loper->jaar - loper->onderboven->jaar;
       else if ( loper->onderboven->jaar - loper->jaar > resultaat )
         resultaat = loper->onderboven->jaar - loper->jaar;
       loper = loper->rechts;
     }//while
     return resultaat;
   }//verschil