Uitwerking Tentamen Programmeermethoden 6 augustus 2001

1.a. void wissel (double A[ ], int i, int j) {
       double temp = A[i];
       A[i] = A[j];
       A[j] = temp;
     }  // wissel
  b. void busort (double A[ ], int n) {
       int ronde, j;
       for (ronde = 1; ronde < n; ronde++)
         for (j = 0; j < n - ronde; j++)
           if ( A[j] > A[j+1] )
             wissel (A,j,j+1);
     }  // busort
  c. (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2
  d. Het let niet op de invoer: een reeds gesorteerd rijtje en een omgekeerd
     gesorteerd rijtje vergen bijvoorbeeld evenveel vergelijkingen.
     En kleine getallen achteraan komen maar langzaam op hun goede plek.
     Bubblesort vergelijkt helaas alleen directe buren.
     De complexiteit is kwadratisch, en er zijn betere algoritmen.
  e. void herstel (double A[ ], int n) {
       int i = 0, j;
       while ( A[i] < A[i+1] )
         i++;  // dit levert de gezochte i
       j = i;  // of j = i+1
       while ( A[j] > A[j+1] )
         j++;  // en dit de gezochte j; gelukkig wisten we dat j < n-1
       while ( i < j ) {
         wissel (A,i,j);
	 i++;
	 j--;
       }  // while
     }  // herstel

2.a. formeel: in functieheading, bijvoorbeeld int f (int & x, bool y) { ...
     actueel: bij aanroep, bijvoorbeeld r en y in z = f (r,y);
     call by value: waarde wordt doorgegeven aan locale kopie; actuele
       parameter verandert niet
     call by reference (met & erbij): variabele zelf wordt doorgegeven, en 
       kan dus ook veranderen (eigenlijk wordt het adres doorgegeven)
     globaal: kan overal gebruikt worden; bovenaan programma aangemaakt
     locaal: plaatselijk in functie geldig
  b. 1(true) 12 6  1 12 12  12 12 12 1
  c. 1 12 6   0 7 12   7 12 3 1
  d. 1 6 6   1 6 6  6 6 1
  e. Ja, mits de variabele x in geel maar call by value is. Het is namelijk
     geen "l-value", iets wat links mag staan bij een toekenning.

3.a. int hoeveel (int A[ ][n], int i) {
       int getal = 0, j;
       for ( j = 0; j < n; j++ )
         getal = 10 * getal + A[i][j];
       return getal;
     }  // hoeveel
  b. bool gelijk (int A[ ][n], int i, int & j, int & k) {
       for ( j = 0; j < i; j++ )
         for ( k = j; k < i; k++ )
	   if ( hoeveel (A,i) == hoeveel (A,j) + hoeveel (A,k) )
	     return true;
       j = 0;
       k = 0;
       return false;
     }  // gelijk
  c. int uniek (int A[ ][n], int m) {
       int tel = 0;
       bool okee;
       for ( i = 0; i < m; i++ ) {
         okee = true;
         for ( j = 0; j < m; j++ )
	   if ( i != j && hoeveel (A,i) == hoeveel (A,j) )
	     okee = false;
	 if ( okee )
	   tel++;
       }  // for
       return tel;
     }  // uniek

4.a. void voegtoe (vakje* & ingang, int nummer ) {
       vakje* nieuw = new vakje;
       nieuw->info = nummer;
       nieuw->volg = ingang;
       if ( ingang != NULL )
         nieuw->volgvolg = ingang->volg;
       else
         nieuw->volgvolg = NULL;
       ingang = nieuw;
     }  // voegtoe
  b. void verwijder (vakje* & ingang) {
       vakje* weg = ingang;
       if ( weg != NULL &&
            ( weg->volgvolg == NULL || weg->volgvolg->info > weg->info ) ) {
         ingang = ingang->volg;
	 delete weg;
       }  // if
     }  // verwijder
  c. void verhoog (vakje* ingang) {
       if ( ingang != NULL && ingang->volg != NULL 
            && ingang->volgvolg != NULL )
         ingang->info += ingang->volg->info + ingang->volgvolg->info;
     }  // verhoog
     Overigens is de test ingang->volg != NULL overbodig, omdat dat al
     door de test ingang->volgvolg != NULL wordt "afgevangen".
  d. Er moet bij a en b een & bij (dus call by reference), want de 
     ingangspointer zal gaan veranderen (bij b overigens niet in alle
     gevallen). Bij c hoeft het niet, want de ingangspointer verandert
     toch niet; het mag overigens wel.
  e. vakje* xde (vakje* ingang, int x) {
       vakje* p = ingang;
       while ( x > 2 ) {
         p = p->volgvolg;
	 x -= 2;
       }  // while
       if ( x > 1 )
         p = p->volg;
       return p;
     }  // xde