Uitwerking tentamen Programmeermethoden 4 januari 2011

OPGAVE 1
a. int tel (int A[ ], int X, int n) {
     int i, teller = 0;
     for ( i = 0; i < n; i++ ) if ( A[i] == X ) teller++;
     return teller;
   }//tel
b. void wissel (int & x, int & y) { int tmp = x; x = y; y = tmp; }//wissel
   void welke3 (int A[ ], int & een, int & twee, int & drie, int n) {
     int i = 1; een = A[0];
     while ( A[i] == een ) i++;
     twee = A[i]; i++;
     while ( A[i] == een || A[i] == twee ) i++;
     drie = A[i];
     if ( een > twee ) wissel (een,twee);
     if ( twee > drie ) wissel (twee,drie);
     if ( een > twee) wissel (een,twee);
   }//welke3
c. void sorteer (int A[ ], int n) {
     int i, een, twee, drie, tel1, tel2;
     welke3 (A,een,twee,drie,n); tel1 = tel (A,een,n); tel2 = tel (A,twee,n);
     for ( i = 0; i < tel1; i++ ) A[i] = een;
     for ( ; i < tel1 + tel2; i++ ) A[i] = twee;
     for ( ; i < n; i++ ) A[i] = drie;
   }//sorteer
d. void busort (int A[ ], int n) {
     int i, ronde;
     for ( ronde = 1; ronde < n; ronde++ )
       for ( i = 0; i < n - ronde; i++ )
         if ( A[i] > A[i+1] ) wissel (A[i],A[i+1]);
   }//busort
e. De methode van c is lineair (O(n)), bubblesort is 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: x, y in  int f (int x, bool y) { ...
   Actueel: bij aanroep, bijvoorbeeld 7 en y in z = f (7,y);
b. R 10,8,10 en 2   R 10,8,10 en 1   R 10,8,10 en 0
   R 10,8,10 en -1  V 10,10 en -1    42 en -1
c. R 10,8,8 en 2    R 8,6,6 en 1     R 6,4,4 en 0
   V 2,4 en -1      Q 34             R 2,4,4 en -1
   V 4,4 en -1      36 en -1
   (NB Ook wordt goed gerekend de volgorde Q V 2,4 en -1 34)
d. Als het call by value is (zonder &) mag het, anders (call by reference, 
   met &) niet: y+z is geen l-value.
e. Omdat rolf victor aanroept, en victor ook rolf, moeten ze dus boven elkaar
   staan. Zonder prototype mag rolf victor (onder rolf) niet aanroepen.

OPGAVE 3
a. int maxi (int schat[ ][n], int & p, int & q) {
     int i, j, grhelp, gr = -1;
     for ( i = 0; i < m; i++ )
       for ( j = 0; j < n; j++ ) {
         grhelp = schat[i][j];
	 if ( i > 0 ) grhelp += schat[i-1][j];
	 if ( i < m-1 ) grhelp += schat[i+1][j];
	 if ( j > 0 ) grhelp += schat[i][j-1];
	 if ( j < n-1 ) grhelp += schat[i][j+1];
	 if ( grhelp > gr ) { gr = grhelp; p = i; q = j; }//if
       }//for
     return gr;
   }//maxi
b. bool vol (int schat[ ][n], int r) {
     int i;
     for ( i = 0; i < m; i++ ) if ( schat[i][r] == 0 ) return false;
     return true;
   }//vol
c. int langste (int schat[ ][n]) {
     int i, j, lengte, lang = 0;
     for ( i = 0; i < m; i++ ) {
       lengte = 0;
       for ( j = 0; j < n; j++ ) {
         if ( schat[i][j] % 2 != 0 ) {
	   lengte++; if ( lengte > lang ) lang = lengte; }//if
	 else lengte = 0;
       }//for
     }//for
     return lang;
   }//langste

OPGAVE 4.
a. void verwissela (duo* & lijst) {
     duo* een = lijst; duo* twee; duo* drie;
     if ( lijst != NULL && lijst->volg != NULL ) {
       twee = lijst->volg; drie = twee->volg; lijst = twee; 
       twee->vorig = NULL; twee->volg = een; een->vorig = twee; 
       een->volg = drie; if ( drie != NULL ) drie->vorig = twee;
     }//if
   }//verwissela
b. void verwisselb (duo* lijst) {
     char temp;
     if ( lijst != NULL && lijst->volg != NULL &&
          ( ( 'A'<= lijst->c1 && lijst->c1 <= 'Z' ) 
	  || ( 'A'<= lijst->c2 && lijst->c2 <= 'Z' ) ) {
       temp = lijst->c1; lijst->c1 = lijst->volg->c1; 
       lijst->volg->c1 = temp; temp = lijst->c2; 
       lijst->c2 = lijst->volg->c2; lijst->volg->c2 = temp;
     }//if
   }//verwisselb
c. void voegtoe (duo* & lijst, char cc1, char cc2) {
     duo* nieuw = new duo; nieuw->c1 = cc1; nieuw->c2 = cc2; 
     if ( lijst != NULL ) lijst->vorig = nieuw;
     nieuw->vorig = NULL; nieuw->volg = lijst; lijst = nieuw;
  }//voegtoe
d. Bij de functie van c verandert de ingangspointer, bij die van a
   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. void verwijder (duo* & lijst, int k) {
     duo* weg;
     while ( lijst != NULL && k > 0 ) {
       weg = lijst; lijst = lijst->volg; delete weg; k--;
     }//while
     if ( lijst != NULL ) lijst->vorig = NULL;
   }//verwijder