Uitwerkingen opgaven uit het dictaat Inleiding Programmeren in C++ voor Life Science & Technology Opgave 1 a. De functie sqrt komt uit math.h; bovenaan het programma moet dus de regel #include staan, of in de nieuwere versies van C++: #include . De functie geeft met een int(eger) of double als invoer een double als uitvoer. Resultaat is hier 2 (oftewel 2.0000). b. Wederom 2 (oftewel 2.0000). c. Er wordt dikwijls "automatisch" tussen char's (karakters) en int's geconverteerd. In sommige talen is daar een speciale omzetfunctie voor nodig, in C++ niet. Aangezien verder de karakters 'a', 'b', ... een oplopend (met stap 1) rangnummer hebben in de ASCII-tabel -en dat is de corresponderende getalswaarde- komt er het aantal letters "tussen" 'e' en 't' uit: 15 dus. Het minteken forceert als het ware de omzetting naar int's. d. De functie ceil rond naar boven (naar rechts op de getallenlijn) af. Resultaat is -99 (een double). e. En floor rondt naar beneden af. Dus -99. f. Dit geeft de double 100. g. Het is een expressie van type bool(ean). Met een waarheidstabel/tafel valt dan in te zien dat de uitdrukking equivalent is aan de exclusieve of: de XOR (oftewel p != q). Stel nu eens dat er een enkele = stond in plaats van een dubbele. Dan mag het opeens niet: de enkele = is een toekenning! Links staat namelijk iets waaraan niet mag worden toegekend (er staat geen "l-value"); expressies als 3*x+5 en !(p&&q) zijn altijd "r-values" (waarden) en mogen alleen RECHTS van de = komen te staan. Het zijn "l-values" als ze een geheugen-locatie aanduiden. Voorlopig zijn dat alleen variabele-namen. h. Rest bij deling van 10 door 3: een int, en wel 1. i. Naar beneden afgerond resultaat van de deling van 10 door 3: een int met waarde 3. Als minstens een van de twee betrokken getallen een double is, wordt het resultaat ook een double. Dit valt ook door "casting" af te dwingen: zo wordt (double) 3 de double 3.0000. Dan levert 10 / (double) 3 de double 3.3333 op. j. Aangezien / en % dezelfde prioriteit blijken te hebben, en "links- associatief" zijn, staat er eigenlijk ( 126 / 3 ) % 5, wat 42 % 5, en dus de int 2 is. Een operator $ is links-associatief als a $ b $ c betekent ( a $ b $ ) $ c. Zo is - (min) links-associatief: 3 - 4 - 5 = (3-4) - 5 = -1 - 5 = -6, en NIET 3 - (4-5) = 3 - -1 = 4. k. Het resultaat is false (ongeacht de waarden van p, q, r en s). q && !q is altijd false, p && false is ook weer false. Het linker argument van de OR, de ||, is dus false. Verder is s || !s altijd true, r || true is ook true, en !true is false. Het rechter argument van de OR is dus ook false. Nu is false || false ook weer false. Klaar. Met een waarheidstafel -met 16 rijen- kan dit ook worden ingezien. l. Het resultaat is de waarde van p. Immers, floor (-65.3) = -66, fabs (-65.3) is 65.3 (absolute waarde), -66 < 65.3 is true, en true && p is p. m. De functie odd (oneven) bestaat niet in C++/math.h. Zou dit wel zo zijn, dan kwam er true uit: k of k+1 is oneven - laten we hopen dat k+1 niet net te groot wordt. De functie odd kan zelf gemaakt worden als: int odd (int a) { return ( ( a % 2 ) == 1 ); } // Is a oneven? Tussen de accolades mag ook return ( a % 2 ); staan. Opgave 2 int main ( ) { int Fahrenheit; cout << "Geef temperatuur in Fahrenheit .."; cin >> Fahrenheit; cout << "In Celsius is dat: " << ( (double) 5 / 9 ) * ( Fahrenheit - 32 ) << endl; return 0; } // main Let er op dat 5 / 9 nul is! Moet er met gehele getallen gerekend worden, gebruik dan: cout << ( 5 * ( Fahrenheit - 32 ) ) / 9; Opgave 3 int main ( ) { int seconden, uren, minuten, secs; cout << "Voer tijd in seconden sinds middernacht in .."; cin >> seconden; uren = seconden / ( 60 * 60 ); minuten = ( seconden - 60 * 60 * uren ) / 60; secs = seconden % 60; cout << "De tijd is " << uren << ":" << minuten << ":" << secs << endl; return 0; } // main Opgave 4 Een lang verhaal. Er zijn allerlei soorten gehele getallen: er is het verschil signed/unsigned, en de drie kwalificaties short/geen/long. Verder kunnen ook char's voor rekenwerk gebruikt worden. Tot slot hangt het misschien zelfs wel af van de implementatie van C++. Laten we proberen te snappen waarom 2 tot de macht 31 - 1 in sommige implementaties van C++ het grootste gehele getal is. Stel dat je 4 bytes, ieder met 8 bits, hebt om een int in op te slaan. Er is een bit nodig voor het teken. Resteren 31 bits. Bij het grootste getal staan deze alle op 1. Zouden het er 3 zijn, dan hadden we (binair) 111 oftewel 4 + 2 + 1 = 7 = 8 - 1. Tel er maar 1 bij op, en je krijgt binair 1000. Bij 31 bits krijg je, na er 1 bij te hebben opgeteld, een 1 met 31 nullen er achter, en dat levert het genoemde getal. Overigens staan de grenzen in limits.h. Probeer ook eens de functie sizeof (type), die de grootte van het type in bytes geeft. Als je 1 optelt bij het grootste getal krijg je doorgaans het kleinste: de tekenbit wordt vaak omgeklapt door de overflow, vergelijk de 1000 van hierboven. Voor wat betreft de double's: zoek dit zelf eens uit. (Zie float.h) Opgave 5 Er wordt natuurlijk gewoon bedoeld if ( doorgaan ) ..., terwijl bovendien er nu een toekenning aan doorgaan wordt gedaan, waardoor de test de waarde van die toekenning (true) krijgt. Zou er while staan in plaats van if, dan krijg je een oneindige loop. Zelfs met == in plaats van = blijft het slap. Opgave 6 a. do S while ( E ) kan herschreven worden als S; while ( E ) S b. while ( E ) S kan herschreven worden als if ( E ) { S ; do S while ( E ) ; } Het kan niet zonder if, aangezien een while ( E ) S S soms nooit uitvoert (namelijk wanneer E initieel al false is), terwijl bij een do S while ( E ) de statements S minstens een maal uitgevoerd worden. Opgave 7 if ( a < b ) { // a < b if ( c < d ) { // a < b; c < d x = 1; } // if ( c < d ) else { // a < b; c >= d if ( a < c ) { // a < b; c >= d; a < c if ( b < d ) { // a < b; c >= d; a < c; b < d, // oftewel a < b < d; a < c; c >= d x = 2; } // if ( b < d ) else { // a < b; c >= d; a < c; b >= d x = 3; } // else }// if ( a < c ) else { // a < b; c >= d; a >= c, // oftewel a < b; a >= c >= d if ( a < d ) { // a < b; a >= c >= d; a < d; tegenstrijdig! if ( b < c ) { // x = 4; // Dit hele } // if ( b < c ) // else { // gedeelte kan x = 5; // } // else // dus weg! } // if ( a < d ) // else { // a < b; a >= c >= d; a >= d. // oftewel a < b; a >= c >= d x = 6; } // else } // else } // else } // if ( a < b ) else { // a >= b x = 7; } // else Duidelijk is dat x = 4 en x = 5 nooit worden uitgevoerd. Het aangegeven gedeelte (if ( a < d ) tot x = 6) kan weggelaten worden. Opgave 8 int main ( ) { int a, b, c; // drie getallen cout << "Geef het eerste getal "; cin >> a; cout << "En het tweede "; cin >> b; cout << "En het derde "; cin >> c; if ( ( a <= b ) && ( b <= c ) ) // zeer botte oplossing cout << a << b << c << endl; else if ( ( a <= b ) && ( c <= a ) ) cout << c << a << b << endl; else ... etcetera ... (nog drie if-statements / vier cout's) return 0; } // main Fraaier is gebruik te maken van de functie wissel (zie dictaat, Hoofdstuk 3.3); we krijgen dan -in plaats het grote if-statement-: if ( a > b ) wissel (a,b); if ( b > c ) wissel (b,c); if ( a > b ) wissel (a,b); In plaats de functie-aanroep mag ook (met hulpvariabele int hulp): if ( a < b ) { hulp = a; a = b; b = hulp; } // if Opgave 9 a. int main ( ) { int n; // in te lezen getal int res; // voor het resultaat cin >> n; // eigenlijk eerst testen of niet n < 0 res = 1; // "lege product" while ( n > 0 ) { res = res * n; n--; } // while cout << res << endl; return 0; } // main b. int main ( ) { // Een for-loop ligt het meest voor de hand: int n, res; // van te voren is het aantal herhalingen cin >> n; // (iteraties) eenvoudig te bepalen. res = 1; // Maar het is wellicht een kwestie van smaak ... for( ; n > 0; n--) res *= n; // oftewel res = res * n; cout << res << endl; return 0; } // main Let erop dat n hier veranderd is; er kan ook een hulpvariabele i worden gebruikt (op n initialiseren); je kunt deze i ook omhoog laten lopen. Bij de for is geen initialisatie nodig: voor de eerste ; staat niks! c. int main ( ) { int n, res = 1; cin >> n; if ( n > 0 ) { // n mag ook 0 zijn; zonder de if gaat het dan mis do { res *= n; n--; } while ( n > 0 ); } // if cout << res << endl; return 0; } // main Met een functie wordt het zoiets als int faculteit (int n) { ... als boven ... return res; } // faculteit Opgave 10 // druk aantal spaties af void spaties (int aantal) { // of nog char symbool ertussen int i; // tellertje for ( i = 1; i <= aantal; i++ ) cout << ' '; // en dan hier cout << symbool; } // spaties Opgave 11 int main ( ) { int getal, // om getal in te lezen totaal = 0, // voor het totaal van de getallen aantal = 0, // voor het aantal getallen minimum = INT_MAX, // voor het minimum van de getallen; // deze constante opzoeken in limits.h: // INT_MAX komt uit limits.h // mooier: initialiseren op het eerste getal maximum = 0; // voor het maximum van de getallen do { cout << "Geef een geheel getal (afsluiten met getal <= 0) .. "; cin >> getal; if ( getal > 0 ) { if ( getal > maximum ) maximum = getal; if ( getal < minimum ) minimum = getal; totaal += getal; aantal++; } // if } // do while ( getal > 0 ); cout << "Gemiddelde is: " << (double) totaal / aantal << endl << "Minimum is: " << minimum << endl << "Maximum is: " << maximum << endl; return 0; } // main Het for-statement is wellicht minder geschikt, het aantal herhalingen is immers van te voren absoluut niet bekend. Opgave 12 int main ( ) { int een, // het aantal eurocenten twee, // het aantal tweetjes, enzovoorts vijf, tien, twintig, vijftig; cout << "Geef bedrag in centen (tussen 1 en 99) .. "; cin >> centen; vijftig = centen / 50; // 0 of 1 centen = centen % 50; twintig = centen / 20; // 0, 1 of 2 centen = centen % 20; tien = centen / 10; // 0 of 1 centen = centen % 10; vijf = centen / 5; // 0 of 1 een = centen % 5; // 0, 1, 2, 3 of 4 // als je op 5 cent wilt afronden: if ( een >= 3 ) { // naar boven afronden vijf++; een = 0; } // if cout << vijftig << twintig << tien << vijf << een << endl; return 0; } // main Opgave 13 int main ( ) { const char afsluiter = ';'; // afsluitend karakter char karakter; // het ingelezen lettertje int expressie = 0, // waarde van de expressie getal, // waarde van het getal teken; // teken van het getal cout << "Geef expressie .. "; cin >> karakter; while ( karakter != afsluiter ) { if ( karakter == '-' ) teken = -1; else // een + blijkbaar teken = 1; cin >> karakter; // eerste cijfer van getal getal = 0; while ( ( '0' <= karakter ) && ( karakter <= '9' ) ) { getal = 10 * getal + karakter - '0'; cin >> karakter; } // while expressie = expressie + teken * getal; // of expressie += ... } // while cout << "Expressie evalueert naar " << expressie << endl; return 0; } // main Opgave 14 double sommetje (int n) { int teller, // teller van teller-de term noemer = 1; // en de noemer daarvan double som = 0; // de (deel)som for ( teller = 1; teller <= n; teller++ ) { noemer *= 2; som += (double) teller/noemer; // denk aan de "typecast" } // for return som; } // sommetje int main ( ) { int n; // aantal termen cout << "Geef aantal termen .. "; cin >> n; cout << "De som is: " << sommetje (n) << endl; return 0; } // main Het is verstandiger -zie Numerieke wiskunde- om met de laatste (kleinste) term te beginnen: het afronden pakt dan beter uit. Helaas moet dan eerst 2 tot de n-de worden uitgerekend ... Opgave 15 Het linker programma levert 2, 2 en daarna 2. Het rechter programma levert 105, 105 en daarna 105. Zonder & wordt dit -1, 2 en 1, respectievelijk 105, 10 en 10. Opgave 16 Eigenlijk maakt de functie alleen zijn tweede variabele 6. a. Afgedrukt worden: 1, 6 en 3. b. En nu: 6, 2 en 3. c. En nu: 1, 2 en 6. d. Op de plek van een call by reference parameter mag geen getal staan: hier moet een l-value, zeg maar een variabele, staan. Een foutmelding dus, en wel een die bij het compileren ontdekt wordt: een "compile-time-error". e. Afgedrukt worden: 6, 2 en 3. Opgave 17 F is een functie met een neveneffect (side effect): de meegegeven variabele verandert. De waarde van de expressie x + F(x) hangt er van af of eerst de linkeroperand of eerst de rechteroperand uitgerekend wordt - en in C++ is die volgorde niet voorgeschreven. Als eerst x bepaald wordt en daarna de waarde van F(x), dan wordt de waarde 18, anders 22. Hetzelfde geldt voor de expressie F(x) + x. De waarde van zo'n expressie is dus AFHANKELIJK van de gebruikte compiler. Conclusie: gebruik dit soort functies niet op deze manier. Als & weggelaten wordt, dan verandert de GLOBALE variabele x niet (alleen de LOCALE x verandert). Dan is de uitkomst altijd 18. En na afloop is de GLOBALE x nog steeds 7. Opgave 18 a. 3, 96, 19, 97, 6, 16 b. int G (int a, int b) { return (a-2)*(a+b+2) + 1; } // G c. Stel dat eerst f (a,b) wordt geevalueerd. Uitkomst 76, en a (oftewel x) is nu 4. Dan f (a,a), geeft 9, en a (dus ook x) is nu 3. Dat levert: 3, 85, 19, 86, 85, 19. Met eerst f (a,a) wordt dit: 3, 73, 19, 74, 73, 19. Het antwoord hangt af van de volgorde van optelling, die in C++ niet vastligt. Opgave 19 a. Eerste peter (p,q) geeft 8, de tweede 16. TWEE doorgangen door de for-loop. 4 27 4 35 2 6 b. Nu geeft peter (p,q) weer 8, en laagt q met 1 af; dus maar EEN doorgang door de for-loop. 3 11 3 17 11 3 c. Eerste p = p+...: p wordt 10 of 11 De tweede: p wordt 26 of 24, OF 27 of 25: de beide optellingen zouden in principe anders kunnen verlopen! Na afloop: a is 24 of 25 of 26 of 27. Het antwoord hangt dus af van de volgorde van optelling, die in C++ niet vastligt. Opgave 20 Overigens zit in math.h (of cmath) ook de functie pow. Nodig zijn de functies exp en log uit math.h (of cmath): double macht (double x, double y) { // bereken x**y = e**log(x**y) = e**(y*log(x)), waarbij ** // machtsverheffen betekent return exp (y * log(x)); } // macht int macht (double x, int y) { // overloading! int k; // tellertje double z = 1; // voor x**k for ( k = 1; k <= y; k++ ) z *= x; return z; } // macht Opgave 21 void drukaf (char letter) { if ( letter == 'a' ) { // of met een switch-statement cout << "****" << endl << "* *" << endl << "****" << endl << "* *" << endl << "* *" << endl; } // if else if ( letter == 'b' ) // etcetera ... } // letter Opgave 22 // druk aantal kar's af void symbool (int aantal, char kar) { // vergelijk Opgave 10 for (int i = 1; i <= aantal; i++) cout << kar; } // symbool void Pyramide (int hoogte) { const int marge = 10; // voor de kantlijn int aantalspaties, // hoeveel spaties op huidige regel? aantalsterretjes, // en hoeveel sterretjes? huidigehoogte; // en welke regel? if ( hoogte > 0 ) { for (huidigehoogte = hoogte; huidigehoogte > 0; huidigehoogte--) { aantalspaties = huidigehoogte - 1; aantalsterretjes = ( hoogte - huidigehoogte ) * 2 + 1; symbool (marge + aantalspaties, ' '); symbool (aantalsterretjes, '*'); cout << endl; } // for } // if } // Pyramide Opgave 23 Een eerste opzet is als volgt: char vorige = 'X'; // neem aan dat in tekst geen X staat char kar = invoer.get ( ); // invoer is de invoerfile while ( !invoer.eof ( ) ) { if ( kar == '\n' ) regelteller++; // telt de regels if ( vorige == 'e' && kar == 'r' ) { // bingo uitvoer << "ER"; vorige = 'X'; } // if else if ( vorige != 'X' ) uitvoer << vorige; vorige = kar; kar = invoer.get ( ); } // while Hier en daar moet nog wat worden aangevuld ... Opgave 24 Voor de liefhebbers. Het lijkt de eerste programmeeropgave wel. Opgave 25 // bereken het n-de Fibonacci-getal (n > 0 geheel) int fibo (int n) { int fiboN, fiboN1, fiboN2; // misschien is type long beter int termnummer; if ( n <= 2 ) return 1; // want eerste en tweede Fibonacci-getal zijn 1 else { fiboN1 = 1; fiboN2 = 1; for (termnummer = 3; termnummer <= n; termnummer++) { fiboN = fiboN1 + fiboN2; // som van de vorige twee, fiboN2 = fiboN1; // en doorschuiven maar fiboN1 = fiboN; } // for return fiboN; } // if } // fibo Opgave 26 // bereken de waarde van het n-de Hermite-polynoom in x (n >= 0) double Hermite (double x, int n) { double HerN, HerN1, HerN2; // voor huidige, vorige en voorvorige int termnummer; if ( n == 0 ) return 1; else if ( n == 1 ) return 2 * x; else { // n >= 2 HerN1 = 2 * x; HerN2 = 1; for (termnummer = 2; termnummer <= n; termnummer++) { HerN = 2 * x * HerN1 - 2 * ( termnummer - 1 ) * HerN2; HerN2 = HerN1; HerN1 = HerN; } // for return HerN; } // if } // Hermite Opgave 27 P moet gebruik maken van Q en R; deze moeten dus boven P gedeclareerd zijn. Dat wordt dan: Q ... of R ... R ... Q ... P ... P ... Met behulp van prototypes zijn er nog andere mogelijkheden. Een prototype van een functie bestaat alleen uit de eerste regel. Zo is een prototype van de functie Hermite uit de vorige opgave: double Hermite (double x, int n); of zelfs: double Hermite (double,int); Nadat zo'n prototype genoemd is, mag de functie vrijelijk gebruikt worden. Uiteraard moet de functie zelf dan ook nog een keer echt gemaakt worden, waarbij de complete eerste regel opnieuw vermeld wordt. Zo krijgen we als mogelijkheid (*) bijvoorbeeld: prototype van Q R ... P ... Q zelf ... Probeer te vermijden dat P een aanroep naar Q doet, en Q een aanroep naar P (recursie; bij situatie (*) zou dit overigens mogen ...). Meestal kan dit eenvoudiger worden opgelost. Opgave 28 a. int afstand, gewicht; double tarief; const int tarief15 = 120, tarief30 = 220, tarief45 = 310, tarief60 = 360, tarief75 = 400; const int extra60 = 20, extra75 = 30; if ( ( gewicht % 15 ) != 0 ) gewicht = ( gewicht / 15 ) * 15 + 15; switch ( gewicht ) { case 15: tarief = tarief15 / 100.0; break; case 30: tarief = tarief30 / 100.0; break; case 45: tarief = tarief45 / 100.0; break; case 60: tarief = (tarief60 + extra60 * (afstand / 1000)) / 100.0; break; default: tarief = (tarief75 + extra75 * (afstand / 1000)) / 100.0; } // switch Opgave 29 const int n = 100; void vullen (int array[ ], int n) { for ( i = 0; i < n; i++ ) array[i] = i * i; } // vullen void afdrukken (int array[ ], int n) { for ( i = 0; i < n; i++ ) cout << array[i]; } // afdrukken Aanroep: int A[n]; // hier "maken" we het array vullen (A,n); afdrukken (A,n); Opgave 30 We maken een array resultaat, waarbij het i-de element aangeeft hoeveel mensen het door i binair gecodeerde antwoord gaven; bijvoorbeeld resultaat[5] geeft aan hoeveel mensen 5 = 1*4 + 0*2 + 1*1 oftewel ja, nee, ja antwoordden. Bij de factor 4 staat het antwoord op de eerste (nulde) vraag, bij de factor 2 het antwoord op de tweede, en bij de factor 1 het antwoord op de derde vraag. void statistiek (bool uitslag[100][3], int resultaat[8]) { // de 3 moet er staan, de 100 wordt genegeerd door de compiler ... int index, persoon; for ( persoon = 0; persoon < 100; persoon++ ) { index = 0; if ( uitslag[persoon][0] ) index += 4; if ( uitslag[persoon][1] ) index += 2; if ( uitslag[persoon][2] ) index += 1; resultaat[index]++; } // for } // statistiek Opgave 31 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 32 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 33 Zie de werkcolleges. Opgave 34 #include #include using namespace std; int main ( ) { ifstream invoer ("invoer.txt",ios::in); ofstream uitvoer ("uitvoer.txt",ios::out); char regel[80]; // maximaal 80 karakters ... char karakter; int aantal = 0; // aantal karakters in huidige regel karakter = invoer.get ( ); while ( ! invoer.eof ( ) ) { if ( karakter == '\n' ) { for ( i = aantal - 1; i >= 0; i-- ) uitvoer.put (regel[i]); uitvoer.put ('\n'); aantal = 0; } // if else { regel[aantal] = karakter; aantal++; } // else karakter = invoer.get ( ); } // while invoer.close ( ); uitvoer.close ( ); return 0; } // main Opgave 35 en 36 Te bewerkelijk. Opgave 37 vermenigvuldig (int A[ ][n], int v[ ], int res[ ]) { int i, j; for ( i = 0; i < n; i++ ) { res[i] = 0; for ( j = 0; j < n; j++ ) res[i] += A[i][j] * v[j]; } // for } // vermenigvuldig Opgave 38 a. int schaakbord[8][8]; Bedenk per stuk een uniek nummer. Nu betekent schaakbord[7][2] == 6 bijvoorbeeld dat er op C1 een witte loper staat; de interpretatie van de rijen en kolommen kan uiteraard ook anders zijn. NB Bij de beschrijving van een spel-situatie moet er ook bij: - wie is aan zet - kan er nog gerocheerd worden - kan er en-passant geslagen worden. - eigenlijk de hele voorgeschiedenis (50-zetten-regel en meer!) b. Verschillende mogelijkheden tot verbetering wat geheugen betreft (het wordt niet leesbaarder) zijn: Nummer de velden van 1..64 en de stukken van 0..31: char schaakbord[32]; Hierbij codeert schaakbord[3] de positie van het vierde stuk, waarbij bijvoorbeeld 0 aangeeft dat het stuk reeds geslagen is. NB Hier is geen rekening gehouden met de aanwezigheid van meer dan een dame door promotie. c. Dambord: Neem 0 voor leeg, 1 voor wit en 2 voor zwart. Dan: int dambord[10][10]; // of [11][11] om nullen als index // te vermijden Verbetering: alleen de zwarte velden worden gebruikt, dus aantal velden beperken tot de helft, of de gewone damnotatie: int stuk dambord[51]; // 0-de element ongebruikt Opgave 39 a. void wedstrijd (int A[ ], int max, int& eenna, int& grootste) { // zoek indices grootste en op een na grootste getal uit array A int i; // om A af te lopen if ( A[0] > A[1] ) { grootste = 0; eenna = 1; } // if else { grootste = 1; eenna = 0; } // else for ( i = 2; i < max; i++ ) if ( A[i] > A[grootste] ) { eenna = grootste; grootste = i; } // if else if ( A[i] > A[eenna] ) eenna = i; } // wedstrijd b. Stel de getallen zijn (in C++ vaak van 0 tot en met 15 genummerd): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 10 26 28 27 32 31 21 26 15 38 23 13 17 45 18 31 Er zijn dus 16 spelers (getallen): s1=10, s2=26, ..., s16=31. De getallen geven steeds de speelsterkte aan. Laat s1 en s2 tegen elkaar spelen (vergelijk de getallen), s3 en s4, ..., s15 en s16. Dan in de volgende ronde de winnaars; dat zijn hier: s2, s3, s5, s8, s10, s11, s14 en s16. Dan spelen dus s2 en s3, s5 en s8, s10 en s11, s14 en s16. Nu gaan s3, s5, s10 en s14 winnen. In de volgende ronde spelen dan s3 en s5, en s10 en s14. Nu gaan s5 en s14 winnen; de finale gaat dan tussen s5 en s14. Uiteraard wint s14. Er zijn nu 15 wedstrijden gespeeld (vergelijkingen geweest): bij iedere wedstrijd mocht weer een speler naar huis. Om de op een na grootste te vinden (de op een na sterkste speler) moeten de verliezers van de uiteindelijke winnaar (s14 hier) nog een mini-toernooi spelen; dat zijn hier: s13=17, s16=31, s10=38 en s5=32. Dat kost nog eens 3 wedstrijden. Deze wedstrijden vinden helaas pas plaats als de finale al geweest is! Om dit uit te programmeren kost het veel te veel overhead: lijsten van verliezers, ... Overigens is hier niet de verliezende finalist, s5, de op een na grootste, maar de reeds eerder verslagen s10. In het algemeen: Als N = 2 tot de macht n, dan zijn er N-1 vergelijkingen/wedstrijden nodig om de beste te vinden en nog eens n-1 vergelijkingen om de op een na beste te bepalen. Opgave 40 int komtvoor (char woord[m], char verhaal[n]) { int i = 0, // om door verhaal heen te lopen j; // om door woord heen te lopen bool gevonden = false; while ( !gevonden && ( i + m <= n ) ) { gevonden = true; // optimist for ( j = 0; j < m; j++ ) // bot if ( woord[j] != verhaal[i+j] ) // pech gevonden = false; i++; } // while if ( gevonden ) return i - 1; else return -1; } // komtvoor Opgave 41 a. bool tweegelijke (char bord[8][8]) { // staan ergens twee dezelfde karakters naast of boven elkaar? int i, // voor de rijen j; // voor de kolommen bool gelijk = false; for ( i = 0; i < 8; i++ ) // naast elkaar for ( j = 0; j < 7; j++ ) if ( bord[i][j] == bord[i][j+1] ) gelijk = true; // en eventueel stoppen: return true for ( i = 0; i < 7; i++ ) // onder elkaar for ( j = 0; j < 8; j++ ) if ( bord[i][j] == bord[i+1][j] ) gelijk = true; // en eventueel stoppen: return true return gelijk; } // tweegelijke b. bool hoofdletters (char bord[8][8]) { // bestaat bord geheel uit hoofdletters? int i, // voor de rijen j; // voor de kolommen bool hoofd = true; for ( i = 0; i < 8; i++ ) for ( j = 0; j < 8; j++ ) if ( ! ( ( 'A' <= bord[i][j] ) && ( bord[i][j] <= 'Z' ) ) ) hoofd = false; // en eventueel stoppen met de loops return hoofd; } // hoofdletters d. int klinkerrij (char bord[ ][8]) { // er mag ook niks tussen de eerste [ ] // geef rijnummer van rij die geheel uit klinkers bestaat, // -1 als zo'n rij niet bestaat int i = 0, // voor de rijen j = 0, // voor de kolommen rij = -1; // voor de gezochte rij bool stoppen = false; // zijn we al klaar? while ( !stoppen && ( i < 8 ) ) if ( ( bord[i][j] == 'A' ) || ( bord[i][j] == 'E' ) || ( bord[i][j] == 'I' ) || ( bord[i][j] == 'O' ) || ( bord[i][j] == 'U' ) ) if ( j == 7 ) { // bingo stoppen = true; // of meteen return i; rij = i; } // if ( j == 7 ) else // volgende kolom j++; else { // medeklinker ==> vooraan volgende rij verder i++; j = 0; } // else return rij; } // klinkerrij Opgave 42 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 43 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 44 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). Opgave 45 void invoegsorteer (int A[ ], int n) { // sorteer A met invoegsorteer (insertion sort) int i, // i-de element straks steeds invoegen j, // om reeds gesorteerde stuk af te lopen temp; // om tijdelijk tussen te voegen getal te bevatten for ( i = 1; i < n; i++ ) { // voeg A[i] in op juiste plaats temp = A[i]; j = i - 1; while ( ( j >= 0 ) && ( A[j] > temp ) ) { A[j+1] = A[j]; j--; } // while A[j+1] = temp; } // for } // invoegsorteer Opgave 46 a. void bergop (int A[ ], int i, int n) { int temp = A[i], j = i + 1; while ( ( j < n ) && ( A[j] < temp ) ) { A[j-1] = A[j]; j++; } // while A[j-1] = temp; } // bergop b. void sorteer (int A[ ], int n) { // die int n is er wel netjes bij int i; for ( i = n - 2; i >= 0; i-- ) bergop (A,i,n); } // sorteer c. 1 vergelijking om 2 op te bergen, 2 voor het getal 3, 3 voor 4, ..., n-2 voor n-1, en n-1 voor n. Samen: 1+2+3+...+n-1 = n(n-1)/2. d. Slechtste geval: evenveel. Beste geval: 1,2,3,...,n: deze methode doet er n-1, de 'gewone' bubblesort doet er altijd n(n-1)/2: veel slechter dus.