UITWERKING Tentamen Programmeermethoden 6 januari 2020

OPGAVE 1
a. bool gem (int A[ ], int n) {
     int i, tel = 0;
     for ( i = 1; i < n-1; i++ )
       if ( A[i-1] + A[i+1] == 2 * A[i] ) tel++;
     return ( tel == 1 );
   }//gem
b. int stijg (int A[ ], int & b, int n ) {
     int i, langste = 1, lang = 1, begin = 0; b = 0;
     for ( i = 1; i < n; i++ )
       if ( A[i] > A[i-1] ) {
         lang++; if ( lang > langste ) { langste = lang; b = begin; } 
       }//if
       else { begin = i; lang = 1; }//else
     return langste;
   }//stijg
c. int kl (int A[ ],int n) {
     int b, s; s = stijg (A,b,n); if ( b == 0 ) b = s;
     if ( A[0] < A[b] ) return A[0]; else return A[b];
   }//kl
d. void bu (int A[ ], int n) {
     int i, j = 0, tmp; bool wissel = true;
     while ( wissel ) {
       wissel = false; j++;
       for ( i = 0; i < n-j; i++ ) // of i < n-1 (*)
         if ( A[i] < A[i+1] ) { // aflopend sorteren
	   tmp = A[i]; A[i] = A[i+1]; A[i+1] = tmp; wissel = true; }//if
     }//while
   }//bu
e. Al aflopend gesorteerd: n-1 vergelijkingen; 
   omgekeerd gesorteerd: n-1 + n-2 + ... + 1 = n(n-1)/2 = O(n^2)
   (bij (*): n(n-1))

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. 1011,8,2,4 LF 2020,1,4,8  (let op de 1011, i wordt 1 meer dan 1010)
c. 4,2,4,8 LF 6,2,4,8
d. 124125,2,2,2 LF 248248,2
e. Dan moet er een prototype van peter boven michael staan, en de tweede en
   derde parameter van peter moeten call bij value zijn (zonder &), 
   want a-1 en a-2 zijn geen l-value.

OPGAVE 3
a. int trip (int P[ ][n], int K[ ], int i, int & totaal){
     int goed, j;
     for ( j = 0; j < n; j++ ) 
       if ( i != j && ( j == 0 || ( i == 0 && j == 1 ) 
                        || 2*P[i][j] + K[j] < totaal ) ) { 
         totaal = 2*P[i][j] + K[j]; goed = j; }//if
     return goed;
   }//trip
b. bool driehoek (int P[ ][n]) {
     int i, j, k;
     for ( i = 0; i < n; i++ )
       for ( j = 0; j < n; j++ )
         for ( k = 0; k < n; k++ )
	   if ( P[i][j] > P[i][k] + P[k][j] ) return false;
     return true;
   }//driehoek
c. int kosten (int P[ ][n], int K[ ][n], int i) {
     int kost = 0; j; bool bezocht[n];
     for ( j = 0; j < n; j++ ) bezocht[j] = false;
     while ( ! bezocht[i] ) {
       bezocht[i] = true;
       do { j = ran ( ) % n; } while ( i == j );
       kost += P[i][j] + K[j]; i = j; }//while
     return kost - K[i];
   }//kosten

OPGAVE 4
a. void erbij (object* & ingang, int getal) {
     object* nieuw = new object; nieuw->info = getal;
     nieuw->onder = NULL;
     if ( ingang == NULL || ingang->onder != NULL ) {
       nieuw->rechts = ingang; ingang = nieuw; }//if
     else {
       ingang->onder = nieuw; nieuw->rechts = NULL }//else
   }//erbij
b. void verwijder (object* & ingang) {
     object* weg;
     if ( ingang != NULL ) {
       if ( ingang->onder == NULL ) {
         weg = ingang; ingang = ingang->rechts; delete weg; }//if
       else { delete ingang->onder; ingang->onder = NULL; }//if
     }//if
   }//verwijder
c. void som (object* ingang) {
     if ( ingang != NULL ) {
       if ( ingang->rechts != NULL )
         ingang->info += ingang->rechts->info;
       if ( ingang->onder != NULL )
         ingang->info += ingang->onder->info;
     }//if
   }//som
d. Bij a en b moet de ingangspointer (doorgaans) wijzigen, dus moet er een
   & bij; bij c maakt het niet uit, de ingangspointer wijzigt toch niet.
e. void print (object* ingang) {
     object* p = ingang; object* q; int tel;
     while ( p != NULL ) {
       tel = 0; q = p;
       while ( q != NULL ) {
         tel++; cout << tel << "-" << q->info; q = q->onder; }//while
       cout << endl;
       p = p->rechts;
     }//while
   }//print