Uitwerking Opgaven Programmeermethoden, najaar 2020 - opgaven 44/48

Opgave 44

a. bool BestaatHoriWoord (char P[m][n], int i, int j) {
     return ( P[i][j] != '#' ) && ( j == 0 || P[i][j-1] == '#' ) &&
            ( j != n-1 && P[i][j+1] != '#' );
   }  // BestaatHoriWoord
  
b. void Nummeren (char P[m][n], int nummers[m][n]) {
     int i, j, teller = 1;
     for ( i = 0; i < m; i++ )
       for ( j = 0; j < n; j++ )
         if ( BestaatHoriWoord (P,i,j) || BestaatVertiWoord (P,i,j) ) {
           nummers[i][j] = teller;
           teller++;
         }  // if
	 else
           nummers[i][j] = 0;
   }  // Nummeren

c. void Woord (char P[m][n], int w) {
     int i, j, k;
     int nummers[m][n];
     Nummeren (P,nummers);
     for ( i = 0; i < m; i++ )
       for ( j = 0; j < n; j++ )
         if ( nummers[i][j] == w && BestaatHoriWoord (P,i,j) ) {
           k = j;
           while ( k < n && P[i][k] != '#' ) {
	     cout << P[i][k];
             k++;
           }  // while
         }  // if
   }  // Woord

Opgave 45

a. int Meeste (int T[ ][n], int m) {
     int i, j, besteklant, telabo, gr = -1;
     for ( i = 0; i < m; i++ ) { // check klant i
       telabo = 0;
       for ( j = 0; j < n; j++ )
         if ( T[i][j] != 0 )
           telabo++;
       if ( telabo > gr ) {
         gr = telabo;
         besteklant = i;
       }  // if
     }  // for
     return besteklant;
   }  // Meeste      
   
b. void Schuifaan (int T[ ][n], int m) {
     int i, j, k;
     for ( i = 0; i < m; i++ ) { // doe klant i
       k = 0; 
       for ( j = 0; j < n; j++ )
         if ( T[i][j] != 0 ) {
           T[i][k] = T[i][j];
           if ( k < j )
             T[i][j] = 0;
           k++;
         }  // if
     }  // for
   }  // Schuifaan

c. int Hoeveel (int T[ ][n], int m) {
     int Nummers[1000]; int i, j, k, teller = 0;
     for ( k = 0; k < 1000; k++ )  // of k vanaf 1
       Nummers[k] = 0;
     for ( i = 0; i < m; i++ ) 
       for ( j = 0; j < n; j++ )
         if ( T[i][j] != 0 )
           Nummers[T[i][j]]++;
     for ( k = 0; k < 1000; k++ )  // of k vanaf 1
       if ( Nummers[k] > 1 )
         teller++;
     return teller;
   }  // Hoeveel

Opgave 46

a. Enkele mogelijkheden:
   1. Temperatuur buiten.
   2. Datum.
   3. Tijd in honderdste seconden (niet zo listig als deze steeds na
      een zelfde tijdsinterval (for-loop ...) wordt uitgelezen!).
   4. sin(1), sin(sin(1)), ...
   5. Kwadrateer herhaald de middelste vier cijfers van het vorige
      getal; begin bij een getal naar keuze.
   6. Vermenigvuldig, deel, reken modulo 5, neem een sinus, en doe nog
      wat van dat soort zaken; meestal ontstaat er een zeer simpele
      reeks!
   7. Decimalen van PI.
   Moraal: 1. random bestaat niet; 2. kies niet random een methode om
   random-getallen te fabriceren.
   Beter is de bij b geschetste methode, zie dictaat Hoofdstuk 5.5.3!
b. Achtereenvolgens 1, 8, 13, 12, 9, 0, 5, 4, 1, 8 enzovoorts.
   Nadeel: reeks gaat zich zeker herhalen, en als je "pech" hebt
   zelfs zonder alle mogelijke getallen te hebben opgeleverd.
   Voordeel: eenvoudige berekening; controleerbaar (= herhaalbaar).
c. Theoretisch is het beter om y = ( a * x + 1 ) % m, met m een macht
   van 2 en a % 8 == 5, te nemen (vraag niet waarom). Zie dictaat, 5.5.3.
   Bijvoorbeeld y = ( 5 * x + 1 ) % 16;

Opgave 47

   double macht1 (double x, int y) {
   // bereken x tot de y-de recursief
     if ( y == 0 )
       return 1;
     else
       return x * macht1 (x,y-1);
   }  // macht

   Deze methode kost y vermenigvuldigingen van double's.

   double macht2 (double x, int y) {
   // bereken x tot de y-de recursief, iets slimmer
     double helft;
     if ( y == 0 )
       return 1;
     else {
       helft = macht2 (x,y/2);  // om niet twee keer dezelfde aanroep te doen
       if ( y % 2 == 0 )  // y even: hier sparen we flink wat *-en uit
         return helft * helft;
       else
         return x * helft * helft;  // of: return x * macht2 (x,y-1);
     }  // else
   }  // macht2

   Deze methode kost zo'n lg y (logaritme met grondtal 2) vermenigvuldigingen.

Opgave 48

a. long fiborec (int n) {
   // bereken n-de Fibonacci-getal recursief; niet handig
     if ( n < 2 )
       return 1;
     else
       return fiborec (n-1) + fiborec (n-2);
   }  // fiborec

   Overigens is dit uiterst inefficient: vele waarden worden herhaald
   uitgerekend, wat zeer veel tijd gaat kosten (Fibonacci-effect of
   waterval-effect)! Zie verder het dictaat, Hoofdstuk 5.12.

b. double Hermiterec (int n, double x) {
   // bereken recursief waarde van n-de Hermite-polynoom in punt x
     if ( n == 0 )
       return 1;
     else
       if ( n == 1 )
         return 2 * x;
       else
         return 2*x*Hermiterec (n-1,x) - 2*(n-1)*Hermiterec (n-2,x);
   }  // Hermiterec