Uitwerking Opgaven Programmeermethoden, najaar 2020 - opgaven 39b/43

Opgave 39

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 (eerste aanzet)

   class grootgetal {
     public: ...
       int geefcijfers (int i) { return inhoud[i]; }   // reader
       void telop (grootgetal& een, grootgetal& twee); // ik = een + twee
     private:
       int inhoud[MAX]; // elk array-element bevat vier cijfers:
       // het getal is inhoud[0] + inhoud[1]*10000 + inhoud[2]*100000000 + ...
       bool teken;  // true voor positieve getallen, false voor negatieve
   }  // grootgetal

   void grootgetal::telop (grootgetal& een, grootgetal& twee) {
   // voorlopig alleen voor positieve getallen; ik = een + twee
     int hulp;       // voor tussenresultaat
     int carry = 0;  // voor overdracht, is 0 of 1
     int k;          // tellertje om array af te lopen
     for ( k = 0; k < MAX; k++ ) {
       hulp = een.geefcijfers (i) + twee.geefcijfers (i) + carry;
       inhoud[k] = hulp % 10000;
       carry = hulp / 10000;
     }  // for
     if ( carry > 0 )
       cout << "OVERFLOW" << endl;
   }  // grootgetal::telop

Opgave 41

a. void grootgetal::omzetten (long getal) {
     for ( int i = 0; i < MAX; i++ ) {
       inhoud[i] = getal % 10000;
       getal = getal / 10000;
     }  // for
     if ( getal != 0 )
       cout << "Getal te groot!" << endl;
   }  // grootgetal::omzetten

b. long grootgetal::terug ( ) {
   // eigenlijk letten op LONG_MAX, zie limits.h
     long res = 0;
     for ( int i = MAX - 1; i >= 0; i-- )
       res = 10000 * res + inhoud[i];
     return res;
   }  // grootgetal::terug

c. groot.omzetten (1234);            // groot van klasse grootgetal
   cout << groot.terug ( ) << endl;  // moet 1234 zijn

Opgave 42

   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;  // of cout << Ja, index = " << i-1 << endl;
     else
       return -1;  // of cout << "Nee" << endl;
   }  // komtvoor

   Het is handiger om de cout's niet in deze functie te stoppen, de
   functie wordt nu algemener toepasbaar.

Opgave 43

a. bool tweegelijke (char bord[8][8]) {  // [ ][8] mag ook ...
   // 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][8]) {
   // 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