Uitwerking Tentamen Programmeermethoden 20 april 2001


1.a. int grokle (double A[ ], int t, bool gr) {
       int beste = 0; int i;
       for ( i = 1; i < t; i++ )
         if ( gr && A[i] > A[beste] ) beste  = i;
	 else if ( !gr && A[i] < A[beste] ) beste = i;
       return beste;
     }  // grokle
  b. void wissel (double A[ ], int i, int j) {
       double temp = A[i];
       A[i] = A[j];
       A[j] = temp;
     }  // wissel
  c. void sorteer (double A[ ], int n) {
       int t, indgro;
       for ( t = n; t > 0; t-- ) {
         indgro = grokle (A,t,true);
	 wissel (A,t-1,indgro);
       } // for
     }  // sorteer
  d. grokle (A,t,true) doet er (t-1); sorteer dus: (n-1) + (n-2) + ... 
     ... + 3 + 2 + 1, oftewel n(n-1)/2.
  e. (n-1) + (n-1) = 2(n-1)
  f. Vergelijk A[0] en A[1], en initialiseer x en y; voor elk volgend
     tweetal getallen 3 vergelijkingen; tesamen: 3n/2 - 2 voor even n.
     Voor oneven n: naar boven afronden.

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. De functie aaa verwisselt bij elke aanroep in feite de waardes van zijn
     argumenten; na 4 aanroepen zijn ze beide weer "zichzelf". Dus:
     0 3.0 1.0 5.0   1 1.0 3.0 7.0   2 3.0 1.0 5.0   3 1.0 3.0 7.0
     7.0 1.0 3.0
  c. Nu verandert er niet veel aan de parameters:
     0 1.0 3.0 5.0   1 1.0 3.0 3.0   2 1.0 3.0 1.0   3 1.0 3.0 -1.0
     -1.0 1.0 3.0
  d. Nu maakt een aanroep als aaa (x,x) zijn argument x gelijk aan 0! Dus:
     0 0.0 0.0 7.0   1 0.0 0.0 7.0   2 0.0 0.0 7.0   3 0.0 0.0 7.0
     7.0 0.0
  e. Met de vier &'s erbij: 
     double bbb2 (double& r, double& s) { return 7.0; }  // bbb2
     En zonder de vier &'s:
     double bbb2 (double r, double s) { return 7.0 - 4*(s-r); }  // bbb2

3.a. int hoe1vaak (int A[ ][n], int m, int X) {
       int i, j, teller = 0;
       for ( i = 0; i < m; i++ ) for ( j = 0; j < n; j++ )
         if ( A[i][j] == X ) teller++;
       return teller;
     }  // hoe1vaak
  b. int hoe2vaak (int A[ ][n], int m, int X, int i, int j) {
       int p, q, teller = 0;
       for ( p = 0; p < m; p++ ) for ( q = 0; q < n; q++ )
         if ( i != p && j != q && A[p][q] == X ) teller++;
       return teller;
     }  // hoe2vaak
  c. void uniek (int A[ ][n], int m, int& i, int& j) {
       int p, q, r, s; bool okee; 
       i = -1; j = -1;
       for ( p = 0; p < m; p++ ) for ( q = 0; q < n; q++ ) {
         // laat rij p en kolom q weg
	 okee = true;
         for ( r = 0; r < m; r++ ) for ( s = 0; s < n; s++ )
	   if ( r != p && s != q && hoe2vaak (A,m,A[r][s],p,q) != 1 )
	     okee = false;
	 if ( okee ) { i = p; j = q; }  // if
       }  // for
     }  // uniek

4.a. void voeg1toe (vakje* & ingang, int nummer) {
       vakje* nieuw = new vakje;
       nieuw->info = nummer;
       nieuw->nogeen = NULL;
       nieuw->volgende = ingang;
       ingang = nieuw;
     }  // voeg1toe
  b. void voeg2toe (vakje* & ingang1, int nummer1, 
                    vakje* & ingang2, int nummer2) {
       voeg1toe (ingang1,nummer1);
       voeg2toe (ingang2,nummer2);
       ingang1->nogeen = ingang2;
       ingang2->nogeen = ingang1;
     }  // voeg2toe
  c. void verwijder (vakje* & ingang) {
       vakje* weg = ingang;
       if ( ingang != NULL && ( ingang->nogeen == NULL ||
                                ingang->nogeen->info > ingang->info ) ) {
         ingang = ingang->volgende;
	 delete weg;
       }  // if
     }  // verwijder
  d. bool gelijk (vakje* ingang1, vakje* ingang2) {
       while ( ingang1 != NULL && ingang2 != NULL ) {
         if ( ingang1->info != ingang2->info ) return false;
         ingang1 = ingang1->volgende;
	 ingang2 = ingang2->volgende;
       }  // while
       return ( ingang1 == ingang2 );
     }  // gelijk
  e. Er moet bij a, b en c een & bij (dus call by reference), want de 
     ingangspointers zullen gaan veranderen (bij c overigens niet in alle
     gevallen). Bij d hoeft het niet, want de ingangspointers veranderen
     toch niet. Zou je het daar wel doen, dan zou de oplossing hierboven
     niet goed werken: de ingangspointers worden dan namelijk veranderd!