Uitwerking tentamen Programmeermethoden 3 augustus 2009

OPGAVE 1
a. void wissel (double A[ ], int i, int j) {
     double temp = A[i];
     A[i] = A[j];
     A[j] = temp;
   }//wissel
b. void bubblesort (double 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,i+1);
   }//bubblesort
c. double kde (double A[ ], int k) {
     int i, ronde;
     for ( ronde = 1; ronde <= k; ronde++ )
       for ( i = 0; i < n-ronde; i++ )
	 if ( A[i] > A[i+1] ) wissel (A,i,i+1);
     return A[n-k];
   }//kde
d. (n-1) + (n-2) + (n-3) + ... + (n-k) = k(2n-k-1)/2
e. double kde2 (double A[ ], int k) {
     int i, onthoud; bool eerste = true;
     for ( i = 0; i < n-1; i++ )
       if ( A[i] > A[i+1] ) {
	 if ( eerste ) {
	   onthoud = i; eerste = false; }//if
	 else {
	   wissel (A,onthoud,i+1); eerste = true; }//else
     if ( ! eerste ) wissel (A,onthoud,onthoud+1);
     return A[n-k];
   }//kde2

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 4   2 6   3 13   4 27   5 55   5 3 105  4 5   105   5 3 4
c. 1 4   2 6   3 15   4 34   5 73   5 4 146  4 5   146   5 4 146
d. 2 2   6 6   26 26  52 52  52 2 3   52   52 3 4
e. Nu nog niet. Wel als je boven hoevaak een prototype
   van paul toevoegt (en dan krijg je recursie):
     int paul (int x, int y);

OPGAVE 3
a. int klein (int A[ ][n], int & i, int & j) {
     int r, s, kleinste = n*n*n;
     for ( r = 0; r < n; r++ )
       for ( s = 0; s < n; s++ )
	 if ( 0 < A[r][s] && A[r][s] < kleinste ) {
	   kleinste = A[r][s]; i = r; j = s;
	 }//if
     return kleinste;
   }//klein
b. void maak0 (int A[ ][n]) {
     int i, j, r; int kl = klein (A,i,j);
     if ( kl != n*n*n )
       for ( r = 0; r < n; r++ ) {
         A[i][r] = 0; A[r][j] = 0; }//for
   }//maak0
c. int over (int A[ ][n]) {
     int i, j, w, waarde = n*n*n;
     w = klein (A,i,j);
     while ( w != n*n*n ) {
       waarde = w; maak0 (A); w = klein (A,i,j);
     }//while
     return waarde;
   }//over

OPGAVE 4
a. void hOOFD (Mens* groep) {
     if ( 'a' <= groep->naam && groep->naam <= 'z' )
       groep->naam = groep->naam + 'A' - 'a';
     else 
       groep->naam = groep->naam + 'a' - 'A';
     if ( groep->volgende != NULL )
       if ( 'a' <= groep->volgende->naam && groep->volgende->naam <= 'z' )
         groep->volgende->naam = groep->volgende->naam + 'A' - 'a';
       else 
	 groep->volgende->naam = groep->volgende->naam + 'a' - 'A';
   }//hOOFD
b. void verwijder (Mens* & groep) {
     Mens* temp;
     if ( ( groep != NULL ) && ( groep->naam != groep->verweg->naam ) ) {
       temp = groep; groep = groep->volgende; delete temp; }//if
    }//verwijder
c. void voegtoe (Mens* & groep, char naampje, int afstand) {
     Mens* nieuw = new Mens; nieuw->naam = naampje; 
     nieuw->volgende = groep; nieuw->hoever = afstand;
     if ( afstand == 0 ) nieuw->verweg = nieuw;
     else if ( afstand == 1 ) nieuw->verweg = nieuw->volgende;
     else nieuw->verweg = nieuw->volgende->volgende;
     groep = nieuw;
   }//voegtoe
d. Bij b en c moet er een & bij staan: de pointer groep kan (bij c zelfs
   zeker) veranderen. Bij a maakt het niet uit: de ingangspointer
   verandert toch niet. Staat er geen & bij, dan wordt er met een lokale
   kopie van groep gewerkt.
e. bool controle (Mens* groep) {
     int i; bool okee = true;
     Mens* p = groep; Mens* q;
     while ( p != NULL && okee ) {
       q = p;
       for ( i = 0; i < p->hoever && q != NULL; i++ ) q = q->volgende;
       if ( q != p->verweg ) okee = false;
       p = p->volgende;
     }//while
     return okee;
   }//controle