Uitwerking Opgaven Programmeermethoden, najaar 2020 - opgaven 49/53 Opgave 49 bool komtvoor (int A[ ], int n, int getal, int vanaf) { // komt getal in de n getallen van array A vanaf positie "vanaf" voor? if ( vanaf >= n ) return false; else if ( getal == A[vanaf] ) return true; else return komtvoor (A,n,getal,vanaf+1); } // komtvoor Ook mag de body slechts uit de volgende regel bestaan (boolese tests worden van links naar rechts geevalueerd): return ( ( vanaf < n ) && ( ( getal == A[vanaf] ) || komtvoor (A,n,getal,vanaf+1) ) ); Opgave 50 Afgezien van eventuele problemen met cin en cout, << en >>, krijgen we de volgende resultaten. a. Neem een iets korter voorbeeld: "abc." Er wordt uitgevoerd ".cba" b. Maar nu: "..cb" c. En nu: "...." De globale kar wordt een '.'! Opgave 51 a. class schilderij { private: int catalogusnummer; int jaar; char maker[30]; // of string ... }; // schilderij b. void afdrukken (schilderij bestand[ ], int max, int voor) { for ( int i = 0; i < max; i++ ) if ( bestand[i].jaar < voor ) cout << bestand[i].catalogusnummer << ... << endl; } // afdrukken c. void zoeken (schilderij bestand[ ], int max, int catnummer) { for ( int i = 0; i < max; i++ ) // beter een while-loop (lineair zoeken) if ( bestand[i].catalogusnummer == catnummer ) ... } // zoeken d. void bubblesortindex (schilderij bestand[max], int index[max]) { int i, j; // tellertjes for ( j = 0; j < max; j++ ) // initialiseren index[j] = j; for ( i = 1; i < max; i++ ) // max-1 rondes for ( j = 0; j < max - i; j++ ) if ( groter (bestand[index[j]].maker,bestand[index[j+1]].maker) ) wissel (index[j],index[j+1]); } // bubblesortindex De functie groter vergelijkt twee char-array's lexicografisch (de volgorde van het woordenboek). Object georienteerde programmeurs overladen hier de operator >, en schrijven dan bestand[...].maker > bestand[...].maker. Als het char*'s zijn, mag de functie strcmp uit string.h gebruikt worden: if ( strcmp (...[j]...,...[j+1]...) > 0 ) ... En met strings uit mag je gewoon > gebruiken. f. Uiteindelijk wordt het indexarray: j 0 1 2 3 4 5 6 index[j] 1 0 4 5 2 6 3 Opgave 52 a. Lineair zoeken naar 9: vergelijk met 1, 3 en 9; naar 21: vergelijk met 1, 3, 9, 10, 13, 17, 19 en 21; naar 18: vergelijk met 1, 3, 9, 10, 13, 17, 19, 21 en 28. Binair zoeken naar 9: vergelijk met 13, 3 en 9; naar 21: vergelijk met 13, 19 en 21; naar 18: vergelijk met 13, 19 en 17. Binair zoeken werkt alleen als de rij gesorteerd is! b. Bijvoorbeeld 2, 5, 7, 13, 15, 22, 29; (k=3) 1 vergelijking bij lineair zoeken, 3 vergelijkingen bij binair zoeken; algemeen: 1 respectievelijk k vergelijkingen. Als een element niet voorkomt vindt lineair zoeken dat na 2 tot de k-de - 1 vergelijkingen, binair zoeken na k stuks. Opgave 53 a. void bubblesort2 (int A[ ], int n) { // bubblesort; stoppen als er een ronde niet verwisseld is // de heading mag ook zijn: void bubblesort2 (int* A, int n) bool gewisseld = true; // is er gewisseld? int i = 1, // turft de rondes j; // array-index while ( gewisseld ) { gewisseld = false; for ( j = 0; j < n-i, j++ ) if ( A[j] > A[j+1] ) { wissel (A[j],A[j+1]); gewisseld = true; } // if i++; } // while } // bubblesort2 void bubblesort3 (int A[ ], int n) { //ingewikkelder versie bool gewisseld = true; // is er gewisseld? int links = 0, linksn = 0, // waar was de eerste wissel? rechts = n-1, rechtsn = n-1; // en waar de laatste? int j; // array-index while ( gewisseld ) { gewisseld = false; for ( j = links; j < rechts, j++ ) if ( A[j] > A[j+1] ) { wissel (A[j],A[j+1]); if ( !gewisseld ) linksn = j - 1; if ( linksn < 0 ) linksn = 0; rechtsn = j - 1; gewisseld = true; } // if links = linksn; rechts = rechtsn; } // while } // bubblesort3 b. In het slechtste geval (een omgekeerd gesorteerd rijtje) doen alle methoden maximaal veel werk. De gewone bubblesort doet overigens altijd evenveel werk, en wel kwadratisch veel vergelijkingen. In het beste geval, een rijtje dat al goed staat, doet de gewone bubblesort weer evenveel vergelijkingen, terwijl de andere varianten maar n-1 vergelijkingen doen (bij n elementen).