JGU Logo JGU Logo JGU Logo JGU Logo

Institut für Informatik

Michael Wand
David Hartmann
Sommersemester 2020 • DIGITAL

Erste Strukturen

Übung 3
Einführung in die Softwareentwicklung







Aufgabe Structs zur Datengruppierung

Letzte Änderung: 04. May 2020, 16:41 Uhr
20 Punkte — im Detail
Ansicht:   |  

In dieser Aufgabe werden wir eine solche Datenbankabfrage (natürlich stark vereinfacht) nachimplementieren. Dazu wird eine (synthetische, also nicht auf echten Messungen basierende) Datenbank als Textdatei vorgelegt.


  bacteria-final.zip (13 Mb, entpackt 79 Mb)

Die Datei ist folgendermaßen aufgebaut:


Um diese Werte sinnvoll zu repräsentieren, verwenden wir folgendes struct.


struct Bacterium {
    uint64_t id;
    std::string name;
    bool antibiotic_sensitivity[30];
};


Aufgaben
Denken Sie daran, dass Argumente in C++ bei der Übergabe standardmäßig kopiert werden. Verwenden Sie Referenzen, um dies zu verhindern.

  1. Schreiben Sie eine Funktion print_bacterium, die eine Instanz von Bacterium nimmt und diese lesbar auf der Konsole ausgibt.
  2. Schreiben Sie eine Funktion print_database, die die Textdatei einliest und jedes Bakterium mithilfe von print_bacterium auf der Konsole ausgibt. Sie können hier zusätzlich eine Hilfsfunktion schreiben, die eine einzelne Zeile aus der Datei einliest und ein einzelnes Bacterium zurückgibt.
  3. Wir brauchen noch ein Ähnlichkeitsmaß bzw. Distanzmaß für Bakterien. Schreiben Sie eine Funktion distance, die zwei Bakterien nimmt und zurückgibt, bei wie vielen Antibiotika sich die Reaktion auf das jeweilige Antibiotikum zwischen den Bakterien unterscheidet, d.h. an wievielen Stellen die Einträge in antibiotic_sensitivity nicht paarweise übereinstimmen.
  4. Erweitern Sie die Funktion print_database (große Teile können kopiert werden) zu einer Funktion namens find_closest so, dass diese zusätzlich ein einzelnes Bakterium b als Argument nimmt und das Bakterium zurückgibt, das b gemäß des zuvor definierten Distanzmaßes am ähnlichsten ist. (Kürzere Distanzen sind besser!)
  5. Ihnen liegen die folgenden drei bisher unbekannten Messungen für antibiotic_sensitivity vor. Finden Sie für alle drei Messungen mithilfe ihrer vorher implementierten Methoden ein bekanntes Bakterium mit der kürzesten Distanz zur jeweiligen Messung. Es reicht, wenn sie die Identifikationsnummer des gefundenen Bakteriums aufschreiben. 
    0 0 1 0 1 1 1 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1
0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 0 0
0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1
  6. Bonus: Für ein unbekanntes Bakterium wurden nicht alle Tests durchgeführt. Sie wissen nur, dass Antibiotika 0, 10, 12, 15 wirken und Antibiotika 7, 14, 29 nicht wirken. Sie könnten jetzt die Datenbank nach Bakterien filtern, die dieselbe Reaktion zeigen, aber das wären immer noch zu viele Ergebnisse. Sie überlegen stattdessen, weitere Tests mit anderen Antibiotika durchzuführen. Es kann hierbei passieren, dass alle noch möglichen Bakterien auf ein bestimmtes Antibiotikum gleich reagieren, was den Test mit diesem Antibiotikum sinnlos machen würde. Finden Sie die Nummern aller Antibiotika, auf die das zutrifft, d.h. alle Antibiotika, die gegen alle verbleibenden Bakterien wirken bzw. gegen alle verbleibenden Bakterien nicht wirken.

Diese Codeschnipsel könnten bei der Aufgabe behilflich sein.

writefile.cpp

#include <fstream>
#include <iostream>
int main(int argc, char * argv[])
{
    std::ofstream myfile("data.txt");

    int a = 42;
    int b = 7;
    int c = 789;
    int d = 8;
    myfile << a;
    myfile << " "; // Leerzeichen nicht vergessen
    myfile << b;
    myfile << std::endl; // return wird ignoriert beim Wiedereinlesen
    myfile << c << " " << d;

    return 0;
}

readfile.cpp

#include <fstream>
#include <iostream>
int main(int argc, char * argv[])
{
    std::ifstream myfile("data.txt");

    int a,b,c,d;
    myfile >> a >> b >> c;
    myfile >> d;

    std::cout << a << " " << b << " " << c << " " << d;

    return 0;
}

arrays.cpp

int main() {

    // Beispiel für fünf Fließkommawerte:
    double testDouble[5];

    // Mit geschweiften Klammern können Arrays initial belegt werden.
    double testDouble[] = {1.2, 1.6, -2.4};

    // Auf einzelne Elemente kann ebenfalls mit eckigen Klammern zugegriffen
    // werden, beispielsweise würde folgender Befehl das Element an Index 1 ein
    // vom Wert 1.6 auf 2.4 setzen.
    testDouble[1] = 2 * testDouble[0];
}





Aufgabe Ein größerer Ganzzahltyp

Letzte Änderung: 04. May 2020, 20:50 Uhr
20 Punkte — im Detail
Ansicht:   |  

Die Aufgabe ist einen 192-bit (positiven) Ganzzahlentyp zu definieren. Um den Einstieg dazu etwas zu vereinfachen haben wir den Header für Sie bereits vollständig implementiert. Außerdem geben wir zwei Konstruktoren vor.

#include <cstdint>

struct uint192 {
    uint64_t parts[3];

    uint192();
    uint192(uint64_t hi, uint64_t mid, uint64_t lo);

    void print_binary();
    void print_hex();
    void print_decimal();
};

uint192 operator +(const uint192 &lhs, const uint192 &rhs);
uint192 operator *(const uint192 &lhs, const uint192 &rhs);
uint192 operator <<(const uint192 &num, uint64_t shift);
uint192 operator >>(const uint192 &num, uint64_t shift);
bool operator ==(const uint192 &lhs, const uint192 &rhs);
bool operator !=(const uint192 &lhs, const uint192 &rhs);
bool operator <(const uint192 &lhs, const uint192 &rhs);
bool operator <=(const uint192 &lhs, const uint192 &rhs);
bool operator >(const uint192 &lhs, const uint192 &rhs);
bool operator >=(const uint192 &lhs, const uint192 &rhs);

So etwa könnte Ihre cpp-Datei aussehen:

#include "uint192.h"

uint192::uint192() : uint192(0, 0, 0) {}

uint192::uint192(uint64_t hi, uint64_t mid, uint64_t lo) {
    parts[0] = lo;
    parts[1] = mid;
    parts[2] = hi;
}

// YOUR CODE HERE

int main() {
    // ...
}



Bei der Bearbeitung empfehlen wir folgendes Vorgehen:

  1. Implementeren Sie den zusätzlichen Konstruktor mit nur einem Argument, der aus einem uint64_t das gleichwertige uint192 macht.
  2. Für die Addition müssen Sie sich zuerst überlegen, wie Sie den Übertrag zwischen zwei Stellen realisieren. Ein erster Ansatz könnte wie folgt aussehen (Beispiel für 16-Bit-Zahlen):

    uint16_t a = 43690; // C++14 erlaubt auch a = 0b1010101010101010;
uint16_t b = 32768; // C++14 erlaubt auch b = 0b1000000000000000;
uint16_t c = a + b; // c == 10922  oder  c == 0b0010101010101010;
uint16_t carry = ((a >> 15) + (b >> 15)) >> 1;


    Machen Sie sich an einigen Beispielen klar, was der Code macht.
    Der Code funktioniert jedoch unglücklicherweise nicht immer!

    1. Geben Sie eine Belegung für a und b an, für die der Code nicht den korrekten Übertrag liefert.
    2. Überlegen Sie sich einen anderen Weg, der Ihnen zuverlässig die Summe zweier uint64_t inklusive Übertrag liefert. (Erklären Sie kurz, etwa als gut gekennzeichneter Kommentar im Code, wie Ihre Methode funktioniert.)
    3. Implementieren Sie damit operator+.
    Selbsttest 
    uint192 a ( 3, ~7ull, ~42ull );
uint192 b ( 2, 21, 46 );
uint192 c ( 6, 14,  3 );
// es sollte gelten: a + b == c
  3. Die Shift-Operatoren kennen Sie noch vom letzten Blatt. Implementieren Sie operator<< und operator>> wie im Header vorgegeben. Denken Sie daran, dass jetzt Verschiebungen um mehr als 64 Bit möglich sind!
    Selbsttest     
    uint192 a ( 3, ~7ull, ~42ull );
uint192 b ( 15, (~7ull << 2) + 3, ~42ull << 2 );
uint192 c ( 0, ~1ull, 4611686018427387893ull );
// es sollte gelten: a << 2 == b
// es sollte gelten: a >> 2 == c
  4. Überlegen Sie sich, wie man die Multiplikation zweier Zahlen aus Shifts und Additionen zusammensetzen kann. Implementieren Sie auf diese Weise operator*.

    Hinweis:
    Erinnern Sie sich dazu an schriftliches Multiplizieren im Dezimalsystem:

    Rechne 214 * 123 = 26322

* |        1  2  3
--+-----------------
2 |  2  4  6
1 |     1  2  3
4 |        4  9  2
--+----------------- +
 2  6  3  2  2


    Versuchen Sie, in dem Beispiel zu erkennen, wo Shifts und wo Additionen verwendet werden.

    Für TüftlerInnen: Schriftliche Multiplikation, wie oben dargestellt ist leider nicht sonderlich effizient. Wenn Ihnen also eine andere Lösung zur Multiplikation einfällt, dürfen Sie auch diese stattdessen implementieren.
  5. Implementieren Sie die Vergleichsoperatoren, also operator==, operator!=, operator>, operator>=, operator< und operator<=.
    (Der Aufwand für diese Funktionen sollte sehr gering sein.)
  6. Natürlich wollen wir unsere Zahl auch lesbar ausgeben. Implementieren Sie zu diesem Zweck
    1. print_binary, um die Zahl in Binärdarstellung auf der Konsole auszugeben sowie
    2. print_hex, um die Zahl in Hexadezimaldarstellung auf der Konsole auszugeben.
  7. Zuletzt wollen wir etwas sinnvolles mit unserer Zahl machen. Die Fakultät von 45 lässt sich nicht in einem uint64_t speichern, wohl aber in einem uint192. Schreiben Sie eine Funktion uint192 factorial(uint64_t n), die die Fakultät von n in einem uint192 berechnet.

    Geben Sie in Ihrer main-Methode die Fakultät von 45 aus.
  8. Bonus: Die Zahl in Binär bzw. Hexadezimaldarstellung auszugeben ist zwar schön und gut, meistens interessiert uns jeoch die Zahl in Dezimaldarstellung.

    Implementieren Sie also eine Funktion print_decimal, um die Zahl in Dezimaldarstellung auf der Konsole auszugeben. Wir verlangen an dieser Stelle natürlich nicht einen effizienten Algorithmus, der die Aufgabe löst, eigenständig zu entwerfen und dann zu implementieren. Alternativ schlagen wir zwei sehr einfach zu verstehende und zu implementierende Möglichkeiten vor:

    • Konstruktives Durchprobieren (dies ist kein Fachbegriff) Sei \(x\) die 192-Bit Zahl, die wir als Dezimalzahl darstellen wollen.
      • Wir suchen die Dezimalstellen von der größten Möglichen zur kleinsten (Zehner) einfach ab. Um eine Zahl \(10^d\) mit unserem Zahlensystem zu konstruieren benötigen wir lediglich die Operatoren * und einen Repräsentanten für die Zahl \(10\).
      • Für jede dieser Dezimalstellen finde das größte \(k\) sodass \(k\cdot 10^d < x\) (\(d\) sei die größte darstellbare Dezimalstelle). Dazu kann man Beispielsweise die \(k\)-fache Addition einer der generierten Dezimalstellen verwenden.
      • Gebe \(k\) aus und suche dann die nächste Dezimalstelle.
    • Division durch 10 mit Rest In den unten bereitgestellten Dateien befindet sich ein struct names uint192divmod10. Dieses implementiert die Division eines uint192 durch 10 mit Rest. Möchte man eine Zahl n durch 10 dividieren, kann man mittels uint192divmod10 result(n); ein uint192divmod10-Objekt anlegen und dann über result.quotient und result.remainder auf den Quotienten und den Divisionsrest zugreifen. Dadurch können Sie die Dezimalstellen einzeln extrahieren.

      Diese Codeschnipsel könnten bei der Aufgabe behilflich sein.

      uint192divmod10.h

      #include <cstdint>

struct uint192divmod10 {
    uint192 quotient;
    uint64_t remainder;

    explicit uint192divmod10(const uint192 &dividend);
};


      uint192divmod10.cpp

      #include "uint192.h"

#include <iostream>

// für die Bonusaufgabe
constexpr uint64_t HALF = static_cast<uint64_t>(0xffffffffull);
constexpr uint64_t SHIFT = static_cast<uint64_t>(32u);
uint192divmod10::uint192divmod10(const uint192 &dividend) {
    remainder = 0;
    for (uint64_t i = 0; i < 3; ++i) {
uint64_t part = 2 - i;
uint64_t upper_dividend = remainder << SHIFT | dividend.parts[part] >> SHIFT;
uint64_t upper_quotient = upper_dividend / 10;
remainder = upper_dividend % 10;
uint64_t lower_dividend = remainder << SHIFT | (dividend.parts[part] & HALF);
uint64_t lower_quotient = lower_dividend / 10;
remainder = lower_dividend % 10;
quotient.parts[part] = upper_quotient << SHIFT | lower_quotient;
    }
}
// Bonusaufgabe Ende