Uitwerking tentamen Programmeermethoden 3 januari 2019 OPGAVE 1 a. int klein (int A[ ], int & i, int X, int n) { int j, kl = -1; i = -1; for ( j = 0; j < n; j++ ) if ( A[j] > X && ( kl == -1 || A[j] < kl ) ) { i = j; kl = A[j]; } return kl; }//klein b. bool alt (int A[ ], int n) { int i; for ( i = 1; i < n-1; i++ ) if ( ( A[i-1] < A[i] && A[i] < A[i+1] ) || ( A[i-1] > A[i] && A[i] > A[i+1] ) ) return false; return true; }//alt c. void sorteer (int A[ ], int n) { int i, j, kl, X = 0; for ( i = 0; i < n-1; i++ ) { X = klein (A,j,X,n); A[j] = A[i]; A[i] = X; // of A[i] en A[j] verwisselen }//for }//sorteer d. Deze functie doet altijd n(n-1) of n^2 of 2n^2 vergelijkingen, terwijl bubblesort er n(n-1)/2 over doet, dus is slechter. Maar beide doen er O(n^2), dus valt ook te verdedigen dat ze even goed (of slecht) zijn. 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. 1001,2006,6 2019,3,1 (met een LineFeed = regelovergang) c. 2 5 8 11 d. 1001,4,4 15,3,1 e. Dan moet er een prototype van sien boven ot staan, en de eerste parameter van sien moet call-by-value (dus zonder &) zijn: ot (r) is geen l-value. OPGAVE 3 a. double gem (int prijs[ ][n], int i) { int j, som = 0; for ( j = 0; j < i; j++ ) som += prijs[j][i]; for ( j = i+1; j < n; j++ ) som += prijs[i][j]; // of j = i; return static_cast (som) / n; // of (double) som }//gem b. bool alle (int prijs[ ][n], int reis[ ], int & kosten) { int i, j; kosten = 0; bool ok = true; for ( i = 1; i < n; i++ ) { if ( reis[i] == -1 ) return false; if ( reis[i-1] < reis[i] ) kosten += prijs[reis[i-1]][reis[i]]; else kosten += prijs[reis[i]][reis[i-1]]; for ( j = 0; j < i; j++ ) if ( reis[j] == reis[i] ) ok = false; }//for return ok; }//alle c. void duur (int prijs[ ][n], int reis[ ], int i) { int j, index, goed, nr = 1; bool bezocht[n]; for ( j = 0; j < n; j++ ) bezocht[j] = false; reis[0] = i; while ( ! bezocht[i] ) { bezocht[i] = true; goed = 0; for ( j = 0; j < i; j++ ) if ( prijs[j][i] > goed ) { goed = prijs[j][i]; index = j; } for ( j = i+1; j < n; j++ ) if ( prijs[i][j] > goed ) { goed = prijs[i][j]]; index = j; } if ( ! bezocht[index] ) { reis[nr] = index; nr++; }//if i = index; }//while while ( nr < n ) { reis[nr] = -1; nr++; }//while }//duur OPGAVE 4 a. void voegtoe (object* & ingang, int getal) { object* nieuw = new object; nieuw->info = getal; nieuw->volg1 = NULL; nieuw->volg2 = ingang; // of andersom if ( ingang != NULL ) if ( ingang->volg1 == NULL ) ingang->volg1 = nieuw; else ingang->volg2 = nieuw; ingang = nieuw; }//voegtoe b. void verwijder (object* & ingang) { object* weg = ingang; if ( ingang != NULL ) { if ( ingang->volg1 == NULL ) ingang = ingang->volg2; else ingang = ingang->volg1; if ( ingang != NULL ) if ( ingang->volg1 == weg ) ingang->volg1 = NULL; else ingang->volg2 = NULL; delete weg; }//if }//verwijder c. void hoogop (object* ingang) { if ( ingang != NULL && ingang->info % 2 != 0 && ( ingang->volg1 != NULL || ingang->volg2 != NULL ) ) if ( ingang->volg1 != NULL ) ingang->info += ingang->volg1->info; else ingang->info += ingang->volg2->info; }//wissel 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 repareer (object* ingang) { object* p = ingang; object* vorig = NULL; while ( p != NULL ) { if ( p->volg1 == vorig ) { p->volg1 = p->volg2; p->volg2 = vorig; }//if vorig = p; p = p->volg1; }//while }//repareer