JGU Logo JGU Logo JGU Logo JGU Logo

Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel
Wintersemester 2020/21 • DIGITAL

Erste Strukturen

Übung 3
Einführung in die Softwareentwicklung







Aufgabe Structs zur Datengruppierung

Letzte Änderung: 23. November 2020, 11:37 Uhr
20 Punkte — im Detail
Ansicht:   |  

In der Biologie kann man Bakterien unter anderem daran identifizieren, welche Antibiotika gegen Sie wirksam sind und welche nicht (siehe auch https://de.wikipedia.org/wiki/Antibiogramm). Dazu sammelt man im Voraus die Reaktionen vieler bereits bekannter Bakterien auf mehrere Antibiotika und speichert diese in einer Datenbank. Will man jetzt ein unbekanntes Bakterium identifizieren, so testet man dessen Reaktion auf dieselben Antibiotika und sucht dann in seiner Datenbank nach Bakterien mit gleichen Eigenschaften.


In dieser Aufgabe werden wir eine solche Datenbankabfrage 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 folgende zwei structs.


struct antibiotic_sensitivities {
    bool sensitivity[30];
};

struct bacterium {
    uint64_t id;
    std::string name;
    antibiotic_sensitivities sensitivities;
};

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 read_database, die die Textdatei einliest und einen https://en.cppreference.com/w/cpp/container/vector mit den eingelesenen Bakterien zurückgibt. Sie können hier zusätzlich eine Hilfsfunktion schreiben, die eine einzelne Zeile aus der Datei einliest und ein einzelnes bacterium zurückgibt.
  3. Schreiben Sie eine Funktion print_database, die einen std::vector<bacterium> nimmt und jedes Bakterium mithilfe von print_bacterium auf der Konsole ausgibt.
  4. Wir brauchen noch ein Ähnlichkeitsmaß bzw. Distanzmaß für Bakterien. Schreiben Sie eine Funktion distance, die zwei Objekte vom Typ antibiotic_sensitivities 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 im Array nicht paarweise übereinstimmen.
  5. Schreiben Sie eine Funktion namens find_closest, die einen std::vector<bacterium> und ein einzelnes Objekt s vom Typ antibiotic_sensitivities als Argument nimmt und das Bakterium zurückgibt, das s gemäß des zuvor definierten Distanzmaßes am ähnlichsten ist. (Kürzere Distanzen sind besser!)
  6. Ihnen liegen die folgenden drei bisher unbekannten Messungen für 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
  7. 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.

Beispiele für Arrays und Datei-Eingabe und -Ausgabe:


writefile.cpp

#include <fstream>
#include <iostream>

int main() {
    std::ofstream myfile("data.txt");

    int a = 42;
    int b = 7;
    int c = 789;
    int d = 8;
    myfile << a << " " << b << std::endl;
    myfile << c << " " << d;

    return 0;
}

readfile.cpp

#include <fstream>
#include <iostream>


int main() {
    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() {

    // 5 uninitialisierte double-Werte
    double s[5];

    // initialisiertes Array der Länge 3
    double s[] = {1.2, 1.6, -2.4};

    // struct-Werte können der Reihe nach initialisiert werden
    antibiotic_sensitivities as = {
        // das hier ist das sensitivity-Array
        {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}
    };

    // auf einzelne Elemente kann mit eckigen Klammern zugegriffen werden
    s[1] = 2 * s[0];
}




Aufgabe Ein größerer Ganzzahltyp

Letzte Änderung: 07. December 2020, 14:33 Uhr
20 Punkte — im Detail
Ansicht:   |  

Um den Einstieg in die Implementierung 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() {
    // ...
}



  1. Implementeren Sie einen 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.
    Dieser Ansatz funktioniert aber für einige Eingaben nicht!

    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+.
    Code zum Testen 
    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!
    Code zum Testen     
    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*.

    Falls Ihnen kein Ansatz dafür einfällt, erinnern Sie sich 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.

    Bonus: Multiplikation durch Shifts und Additionen ist in diesem Fall nicht die effizienteste Lösung. Wenn Ihnen eine bessere 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<=. Wenn Sie sich Arbeit sparen wollen, überlegen Sie, welche Operationen an bereits implementierte Operatoren delegiert werden können.
  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 hilfreich zum Debuggen, meistens interessiert uns jedoch die Zahl in Dezimaldarstellung.

    Implementieren Sie also eine Funktion print_decimal, um die Zahl in Dezimaldarstellung auf der Konsole auszugeben. Sie können hierzu ein Verfahren implementieren, das üblicherweise in Hardware realisisert wird. Das ist allerdings eher umständlich. Daher schlagen wir Ihnen eine andere Lösung vor, die einfacher zu implementieren ist:

    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. Durch iteriertes Dividieren können Sie die Dezimalstellen einzeln extrahieren.

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