Uitwerking tentamen Programmeermethoden 24 februari 2010

OPGAVE 1
a. int hoevaak (int X, int A[ ], int n) {
     int i, tel = 0;
     for ( i = 0; i < n; i++ ) if ( A[i] == X ) tel++;
     return tel;
   }//hoevaak
b. void voegtoe (int A[ ], int i)  {
     int j = i - 1, temp;
     while ( j >= 0 && A[j] > A[j+1] ) {
       temp = A[j]; A[j] = A[j+1]; A[j+1] = temp; j--;
     }//while
   }//voegtoe
c. void uniek (int A[ ], int B[ ], int n) {
     int i, k = 0;
     for ( i = 0; i < n; i++ )
       if ( hoevaak (A[i],A,n) == 1 ) {
         B[k] = A[i]; voegtoe (B,k); k++;
       }//if
     for ( ; k < n; k++ ) B[k] = 0;
   }//uniek
d. In het beste geval 0 verwisselingen, namelijk als alle unieke getallen
   (if any) uit A in stijgende volgorde voorkomen.
e. In het slechtste geval: 1 + 2 + ... + (n-1) = n(n-1)/2 verwisselingen,
   als A uit allemaal verschillende getallen bestaat en aflopend gesorteerd
   is.

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. 1: 1, 3, 4, 6     2: 1, 3, 4, 6    3: 6, 6, 7, 6    6, 3 en 3
c. Dat mag niet: op de plek van a en b staat bij aanroep sven (p,q), 
   en daar moet een l-value (een variabele) staan.
d. Bij + ligt de volgorde van evaluatie van linekr en rechter argument
   niet vast. Als eerst sven (p,q) wordt gedaan:
   1: 1, 3, 4, 6    2: 3, -1, 3, 0    6, -1 en 2
   (na de eerste output geldt p = -1, na de tweede geldt ook q = -1)
   En als eerst sven (q,p) wordt berekend:
   1: 3, 1, 3, 0    2: 1, -1, 1, 0    0, -1 en 2
e. Dan moet ook bob boven sven gedefinieerd worden. En dat gaat via
   een prototype:
     int bob (int p, int q);

OPGAVE 3
a. int tel (int temper[ ][n]) {
     int aantal = 0, i, j; bool gr, kl;
     for ( i = 0; i < m; i++ ) {
       gr = kl = false;
       for ( j = 0; j < n; j++ ) 
         if ( temper[i][j] < 0 ) kl = true;
         else if ( temper[i][j] > 0 && temper[i][j] != 99 ) gr = true;
       if ( kl && gr ) aantal++;
     }//for
     return aantal;
   }//tel
b. bool schaatsbaan (int temper[ ][n], int i, int j, int p, int q) {
     if ( ( i == p && j == q ) || ( i != p && j != q ) ) return false;
     if ( i == p ) {
       for ( k = j; k <= q; k++ ) if ( temper[i][k] >= 0 ) return false;
       for ( k = q; k <= j; k++ ) if ( temper[i][k] >= 0 ) return false;
     }//if
     else { // j == q
       for ( k = i; k <= p; k++ ) if ( temper[k][j] >= 0 ) return false;
       for ( k = p; k <= i; k++ ) if ( temper[k][j] >= 0 ) return false;
     }//if
     return true;
   }//schaatsbaan
c. bool kruis (int temper[ ][n]) {
     int i, j;
     for ( i = 0; i < m; i++ ) for ( j = 0; j < n; j++ )
       if (   ( ( j+1 < n && schaatsbaan (temper,i,j,i,j+1) )
              || ( j > 0 && schaatsbaan (temper,i,j,i,j-1) ) )
           && ( ( i+1 < m && schaatsbaan (temper,i,j,i+1,j) )
              || ( i > 0 && schaatsbaan (temper,i,j,i-1,j) ) ) ) return true;
     return false;
   }//kruis

OPGAVE 4
a. void verwissel (hetgetal* & eerste) {
     hetgetal* p = eerste;
     if ( eerste != NULL && eerste->volg != NULL ) {
       eerste = eerste->volg; p->volg = eerste->volg; eerste->volg = p;
       p->point = eerste->point; eerste->point = p->info;
     }//if
   }//verwissel
b. void voegtoe (hetgetal* & eerste, int get) {
     hetgetal* nieuw = new hetgetal; nieuw->info = get;
     nieuw->volg = eerste;
     if ( eerste == NULL ) nieuw->point = 0;
     else nieuw->point = eerste->info;
     eerste = nieuw;
   }//voegtoe
c. void verwijder (hetgetal* eerste) {
     hetgetal* weg;
     if ( eerste != NULL && eerste->volg != NULL ) {
       eerste->point = eerste->volg->point;
       weg = eerste->volg; eerste->volg = weg->volg;
       delete weg;
     }//if
   }//verwijder
d. Bij a en b moet er een & bij (de ingangspointer gaat veranderen; bij
   a soms niet, overigens). Bij c hoeft het niet, de pointer verandert
   niet; het mag wel.
e. void corrigeer (hetgetal* & eerste) {
     hetgetal* p = eerste; hetgetal* q;
     while ( p->point == p->volg->info ) p = p->volgende;
     if ( p->volg->volg != NULL && p->volg->point == p->volg->volg->info ) { 
       q = eerste; eerste = eerste->volg; }//if
     else { q = p->volg; p->volg = q->volg; }//else
     delete q;
   }//corrigeer