UITWERKING Tentamen Programmeermethoden 28 maart 2012

OPGAVE 1
a. double gem (int A[ ], int n) {
     int i, som = 0;
     for ( i = 0; i < n; i++ )
       som += A[i];
     return static_cast<double> (som) / n;
   }//gem
b. bool gesorteerd (int A[ ], int n) {
     int i;
     for ( i = 0; i < n-1; i++ )
       if ( A[i] > A[i+1] ) return false;
     return true;
   }//gesorteerd
c. void wissel (int A[ ], int i, int j) {
     int temp;
     if ( 0 <= i && i < n && 0 <= j && j < n && 
          ( ( i < j && A[i] > A[j] ) || ( i > j && A[i] < A[j] ) ) ){
       temp = A[i]; A[i] = A[j]; A[j] = temp;
     }//if
   }//wissel
d. void sorteer (int A[ ], int k, int n) {
     int i, j, tel = 0;
     while ( ! gesorteerd (A,n) )
       for ( tel = 1; tel <= k; tel++ )
         wissel (A,ran ( ) % n,ran ( ) % n);
   }//sorteer
e. Elke aanroep van gesorteerd doet steeds minstens een vergelijking,
   en de laatste aanroep doet er precies n-1.
   En het kost minstens n/2 (naar beneden afgerond: t = floor(n/2)) 
   gelukkige aanroepen van wissel (met steeds 1 vergelijking).
   Dit vereist ceil(t/k) rondes met elk k van deze aanroepen.
   Tesamen: minimaal n-1 + (k+1)*ceil(floor(n/2)/k) vergelijkingen.

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 r en y in z = f (r,y);
b. 21, 3 en 3        13 en 2       15, 3 en 4
c. 21, 3 en 7        7 en 3        10, 7 en 3
d. 998, 998 en 998   1006 en 1006  2012, 3 en 8
e. Dan moet boven eva nog een prototype van floris worden gezet:
     int floris (int x, int y);
   Er is dan wel sprake van recursie.

OPGAVE 3
a. bool driehoek (int K[ ][n]) {
     int i, j, k;
     for ( i = 0; i < n; i++ )
       for ( j = 0; j < n; j++ )
         for ( k = 0; k < n; k++ )
	   if ( K[i][j] > K[i][k] + K[k][j] )
	     return false;
     return true;
   }//driehoek
b. void lager (int K[ ][n]) {
     int i, j;
     for ( i = 0; i < n; i++ )
       for ( j = 0; j < n; j++ )
         K[i][j] = static_cast<int> (0.8 * K[i][j] + 0.5);
   }//lager
c. int totprijs (int K[ ][n], int i) {
     bool geweest[n]; int bedrag = 0, laagst, j;
     for ( j = 0; j < n; j++ ) geweest[j] = false;
     while ( ! geweest[i] ) {
       geweest[i] = true;
       if ( i == 0 ) laagst = 1; else laagst = 0;
       for ( j = 0; j < n; j++ )
         if ( i != j && K[i][j] < K[i][laagst] ) laagst = j;
       bedrag += K[i][laagst];
       i = laagst;
     }//while
     return bedrag;
   }//totprijs

OPGAVE 4
a. void verwijder (pr* & begin) {
     pr* weg = begin;
     if ( begin != NULL && begin->prijs % 2 == 0 ) {
       begin = begin->volg1;
       delete weg;
     }//if
   }//verwijder
b. void voegtoe (pr* & begin, int prijsje) {
     pr* nieuw = new pr;
     nieuw->prijs = prijsje; nieuw->volg1 = begin;
     if ( begin == NULL ) {
       nieuw->volg2 = NULL; nieuw->volg3 = NULL; }//if
     else { 
       nieuw->volg2 = begin->volg1; nieuw->volg3 = begin->volg2; }//else 
     begin = nieuw;
   }//voegtoe
c. void verwissel (pr* & begin) {
     pr* een; pr* twee;
     if ( begin != NULL && begin->volg1 != NULL ) {
       een = begin; twee = begin->volg1;
       een->volg3 = twee->volg3; een->volg2 = twee->volg2;
       twee->volg3 = twee->volg2; twee->volg2 = twee->volg1;
       begin = twee; een->volg1 = twee->volg1; twee->volg1 = een;
     }//if
   }//verwissel
d. In dit geval moet er steeds een & bij: de pointer gaat namelijk
   veranderen. Als bij c alleen de prijs-inhouden verwisseld worden,
   hoeft het niet.
e. pr* laatste (pr* begin) {
     pr* loper = begin;
     while ( loper != NULL ) {
       if ( loper->volg3 != NULL ) loper = loper->volg3;
       else if ( loper->volg2 != NULL ) return loper->volg2;
       else if ( loper->volg1 != NULL ) return loper->volg1;
       else return loper;
     }//while
     return NULL;
   }//laatste