Uitwerking Tentamen Programmeermethoden 10 april 2000 - dag

1.a. void bubblesort (int A[ ], int n) {
       int i; int temp;
       for ( i = 1; i < n; i++ )  // n-1 rondes
         for ( j = 0; j < n-i; j++ ) 
           if ( A[j] > A[j+1] ) {
             temp = A[j]; A[j] = A[j+1]; A[j+1] = temp;
           }  // if
     }  // bubblesort
  b. void telsort (int A[ ], int n) {
       int tel[10]; int i, k, plek = 0;
       for ( k = 0; k < 10; k++ ) tel[k] = 0;
       for ( i = 0; i < n; i++ ) tel[A[i]]++;
       for ( k = 0; k < 10; k++ )
         for ( i = 0; i < tel[k]; i++ ) { 
	   A[plek] = k; plek++; 
	 }  // for
     }  // telsort
  c. void duo (int A[ ], int n, int & x, int & y) {
       int x0, y0, i, tel, gr = -1;
       // het kan efficienter met een array tel[10][10], vergelijk b
       // je krijgt dan onder meer tel[A[i]][A[i+1]]++;
       for ( x0 = 0; x0 < 10; x0++ )
         for ( y0 = 0; y0 < 10; y0++ )  {
	   tel = 0;
	   for ( i = 0; i < n-1; i++ )
	     if ( A[i] == x0 && A[i+1] == y0) tel++;
	   if ( tel > gr ) {
	     gr = tel; x = x0; y = y0;
	   }  // if
	 }  // for
     }  // duo
     // als er meerdere paren voldoen krijg je zo het "eerste" paar
  d. bubblesort: 1 + 2 + ... + (n-1) = n(n-1)/2
     telsort: 0 (!); alleen zinvol als er een klein bereik is,
     zoals hier de getallen 0,1,2,...,9 (want je moet een array 
     maken waarvan dit de indices zijn)
     
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
     globaal: kan overal gebruikt worden; bovenaan programma aangemaakt
     locaal: plaatselijk in functie geldig
  b. X X X 4    X X X X X 6    1 3 5 5 3    2 5 1  
  c. Als a <= 0: 0 keer; anders: als b <= 1 1 keer; anders: 2 keer
  d. X X X 4    4 1 3 3 5      1 1 3
  e. b-u is geen l-value (geen fatsoenlijke variabele)
  
3.a. bool reis (int af[n][n], int km) {
       int i, j, k;
       for ( i = 0; i < n-2; i++ )
         for ( j = i+1; j < n-1; j++ )
	   for ( k = j+1; k < n; k++ )
	     if ( af[i][j] + af[j][k] + af[k][i] == km ) return true;
       return false;
     }  // reis
  b. int verste (int af[n][n], int i) {
       int k, ver = -1, verweg;
       for ( k = 0; k < n; k++ )
         if ( af[i][k] > ver ) {
	   ver = af[i][k]; verweg = k;
	 }  // if
	 return verweg;
     }  // verste
  c. int hoever (int af[n][n], int i) {
       int afstand = 0, j;
       bool geweest[n];
       for ( j = 0; j < n; j++ ) geweest[j] = false;
       while ( ! geweest[i] ) {
         geweest[i] = true; j = verste (af,i); 
	 afstand += af[i][j]; i = j;
       }  // while
       return afstand;
     }  // hoever

4.a. void voegtoe (vakje* & ingang, int getal) {
       vakje* nieuw = new vakje;
       nieuw->info = getal;
       nieuw->vorige = NULL; nieuw->volgende = ingang;
       nieuw->eerste = nieuw;
       if ( ingang == NULL ) nieuw->laatste = nieuw;
       else {
         nieuw->laatste = ingang->laatste;
	 ingang->vorige = nieuw;
       }  // else 
       ingang = nieuw;
     }  // voegtoe
  b. void verwijder (vakje* & ingang) {
       vakje* weg = ingang;
       if ( weg != NULL && weg->info > 1000 ) {
         ingang = ingang->volgende; 
	 if ( ingang != NULL ) ingang->vorige = NULL;
	 delete weg;
       }  // if
     }  // verwijder
  c. void verwissel (vakje* ingang) {
       int temp;
       if ( ingang != NULL && ingang->volgende != NULL ) {
         temp = ingang->info; 
	 ingang->info = ingang->volgende->info;
	 ingang->volgende->info = temp;
       }  // if
     }  // verwissel
  d. Bij a en b moet er een & bij staan: de pointer ingang kan (bij a zelfs
     zeker) veranderen. Bij c maakt het niet uit: de ingangspointer
     verandert toch niet. Staat er geen & bij, dan wordt er met een lokale
     kopie van ingang gewerkt.
  e. int grsom (vakje* ingang) {
       int vast = ingang->eerste->info + ingang->laatste->info;
       vakje* loper = ingang->volgende;
       int temp, gr = 0;
       if ( ingang->volgende != NULL ) gr = ingang->volgende->info;
       while ( loper != NULL ) {
         temp = loper->vorige->info;
	 if ( loper->volgende != NULL ) temp += loper->volgende->info;
	 if ( temp > gr ) gr = temp;
         loper = loper->volgende;
       }  // while
       return ( vast + gr );
     }  // grsom