Uitwerking Tentamen Programmeermethoden 7 januari 1997


1.a. void GrKl (array A, int& Gr, int& Kl) {
       int i;
       Gr = A[0];
       for ( i = 1; i < n; i++ )
         if ( A[i] > Gr )
           Gr = A[i];
       Kl = A[0];
       for ( i = 1; i < n; i++ )
         if ( A[i] < Kl )
           Kl = A[i];
     }  // GrKl

  b. void GrKl2 (array A, int& Gr, int& Kl) {
       int i, j, kl, gr;
       if ( A[0] > A[1] ) {
         Gr = A[0]; Kl = A[1]; }  // if
       else {
         Gr = A[1]; Kl = A[0]; }  // else
       for ( i = 2; i < n-1; i+=2 ) {
         j = i+1;
         if ( A[i] > A[j] ) {
           gr = A[i]; kl = A[j]; }  // if
         else {
           gr = A[j]; kl = A[i]; }  // else
         if ( gr > Gr )
           Gr = gr;
         if ( kl < Kl ) 
           Kl = kl;
       }  // for
       if ( n % 2 != 0 ) {  // oneven n; laatste array-element apart
         if ( A[n-1] > Gr )
           Gr = A[n-1];
         if ( A[n-1] < Kl )
           Kl = A[n-1];
       }  // if
     }  // GrKl2

  c. 2(n-1) (iets slimmere versie, die plek grootste onthoudt: 2n-3).

  d. n even: 1 + (n-2)*3/2; n oneven: 1 + (n-3)*3/2 + 2.
     Kortom: ceiling(3n/2) - 2, waarbij ceiling naar boven afrondt.

  e. Zoek herhaald grootste en kleinste (en -aanpassing functie- hun array-
     indices, en dat in een deelarray), en wissel deze met laatste en eerste 
     array-element. Het array wordt nu voor en achter een element korter. 
     Herhaal dit n/2 keer ((n-1)/2 keer voor oneven n).

2.b. 1, 3, 140, 5, 141, 2, 5 (een (x,x) geeft 120).

  c. int Twee (int x, int y) {
       return 4 * x * ( x + 2 ) + y - 1;
     }  // Twee

  d. Stel dat eerst een (x,x) wordt geevalueerd. Uitkomst 121, en x 
     onveranderd 11. Dan een (r,x), geeft 20. Dat levert:
     2, 3, 141, 5, 141, 5, 141.
     Met eerst een (r,x) wordt dit: 2, 3, 120, 5, 120, 5, 120.
     Het antwoord hangt af van de volgorde van optelling, die in C++ niet 
     vastligt.


3.a. bool RoodAanDeBeurt (VierOpEenRij V) {
       int i, j, telR = 0, telZ = 0;
       for ( i = 0; i < m; i++ ) for ( j = 0; j < n; j++ )
         if ( V[i][j] == 'R' )
           telR++;
         else
           if ( V[i][j] == 'Z' )
             telZ++;
       return ( telR == telZ );
     }  // RoodAanDeBeurt

  b. int Rij (VierOpEenRij V, int k) {
       int i = m-1;
       while ( i >= 0 && V[i][k] != '#' ) i--;
       return i;
     }  // Rij

  c. bool Wint (VierOpEenRij V, char kleur) {
       int i, j; bool okee = false;
       for ( i = 0; i < m; i++ ) for ( j = 0; j < n-3; j++ )
         if ( V[i][j] == kleur && V[i][j+1] == kleur 
              && V[i][j+2] == kleur && V[i][j+3] == kleur )
           okee = true;
       return okee;
     }  // Wint

4.a. void Hoofd (Wagon* Trein) { 
       // neem aan dat de namen kleine letters zijn
       *(Trein->bijnaam) = Trein->naam + 'A'-'a';
       if ( Trein->volgende != NULL )
         *(Trein->volgende->bijnaam) = Trein->volgende->naam + 'A'-'a';
     }  // Hoofd

  b. void Voegtoe (Wagon*& Trein, char kar1, char kar2) {
       Wagon* p = new Wagon;
       p->naam = kar1;
       p->volgende = Trein;
       Trein = p;
       p->bijnaam = new char;
       *(p->bijnaam) = kar2;  
     }  // Voegtoe

  c. void Verwijder (Wagon*& Trein) {
       Wagon* p = Trein;
       if ( Trein != NULL && Trein->naam != 'K' ) {
         Trein = Trein->volgende;
         delete p->bijnaam;
         delete p; }  // if
     }  // Verwijder

  d. Bij b en c moet er een & bij staan: de pointer Trein kan (bij b 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 Trein gewerkt.

  e. int Aantal (Wagon* Trein) {
       int teller = 0;
       Wagon* p = Trein;
       while ( p != NULL ) {
         if ( p->volgende != NULL && *(p->volgende->bijnaam) == p->naam )
           teller++;
         p = p->volgende; }  // while
       return teller;
     }  // Aantal