UITWERKING Tentamen Programmeermethoden 30 juli 2012 OPGAVE 1 a. int telme (double A[ ], double X, int n) { int i, teller = 0; for ( i = 0; i < n; i++ ) if ( A[i] == X ) teller++; return teller; }//telme b. double gr (double A[ ], int n) { double groot = 0.0; int i; for ( i = 0; i < n-1; i++ ) if ( A[i] - A[i+1] > groot ) groot = A[i] - A[i+1]; else if ( A[i+1] - A[i] > groot ) groot = A[i+1] - A[i]; return groot; }//gr c. int wisseling (double A[ ], int n) { int i, teller = 0; 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] ) ) teller++; return teller; }//wisseling d. void buso (double A[ ], int n) { int i, ronde; double temp; for ( ronde = 1; ronde < n; ronde++ ) for ( i = 0; i < n-ronde; i++ ) if ( A[i] < A[i+1] ) { temp = A[i]; A[i] = A[i+1]; A[i+1] = temp; } }//buso e. De methode is niet efficient: het kost O(n-kwadraat) vergelijkingen, en dat kan beter. Je moet ook niet alleen directe buren vergelijken. 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. 5,3,100,4,1 1 1,100,1,1 c. 5,3,100,4,1 3 7,100,3,0 d. 42 1,98,42 e. Mag niet. Op de plek van een call-by-reference variabele moet ook echt een variabele staan bij aanroep, en niet een expressie als (y-98). OPGAVE 3 a. void goed (int Q[ ][n], int K[ ][n], int min, int & i, int & j) { int p, q, kosten = -1; i = -1; j= -1; for ( p = 0; p < n; p++ ) for ( q = 0; q < n; q++ ) if ( Q[p][q] >= min ) if ( kosten == -1 || K[p][q] < kosten ) { kosten = K[p][q]; i = p; j = q; }//if }//goed b. double ver (int Q[ ][n], int K[ ][n]) { int i, j; double totaal = 0.0; for ( i = 0; i < n; i++ ) for ( j = 0; j < n; j++ ) if ( K[i][j] > 10*Q[i][j] ) totaal += ( K[i][j] - 10*Q[i][j] ); else totaal += ( 10*Q[i][j] - K[i][j] ); return totaal / (n*n); }//ver c. int kosten (int Q[ ][n], int K[ ][n], int i, int j) { int bedrag = K[i][j]; bool klaar = false; while ( ! klaar ) { if ( j+1 < n && Q[i][j+1] > Q[i][j] ) { j++; bedrag += K[i][j]; } else if ( i+1 < n && Q[i+1][j] > Q[i][j] ) { i++; bedrag += K[i][j]; } else klaar = true; }//while return bedrag; }//kosten OPGAVE 4 a. void verwijder (duo* & begin) { duo* p = begin; if ( begin != NULL && ( begin->naam < '0' || begin->naam > '9' ) ) { //(*) begin = begin->volg; delete p; }//if }//verwijder b. void voegtoe (duo* & begin, char letter) { duo* p = new duo; if ( 'a' <= letter && letter <= 'z' ) letter = (char)(letter-'a'+'A'); p->naam = letter; p->alfa = NULL; p->volg = begin; begin = p; }//voegtoe c. void verwissel (duo* begin) { char naampje; duo* p; if ( begin != NULL && begin->volg != NULL ) { naampje = begin->naam; begin->naam = begin->volg->naam; begin->volg->naam = naampje; p = begin->alfa; begin->alfa = begin->volg->alfa; begin->volg->alfa = p; //en voor wat rare gevallen: if ( begin->alfa == begin ) begin->alfa = begin->volg; if ( begin->volg->alfa == begin->volg ) begin->volg->alfa = begin; }//if }//verwissel d. Bij a en b verandert (doorgaans) de pointer, dus moet er een & bij. Bij c mag het, de pointer verandert toch niet. Als de objecten bij c verwisseld worden, moet er wel een & bij. e. Voeg op plek //(*) toe: duo* q = begin; while ( q->alfa != p ) q = q->volg; q->alfa = p->alfa;