Dies ist ein Archiv des alten Softwaretechnik Lehrstuhls der Universität des Saarlandes. Es ist nicht länger aktuell.

  

Übungen zum C++-Kurs
Schnelleinstieg in die imperative Programmierung mit C++

Lehrstuhl für Softwaretechnik (Prof. Zeller)
Universität des Saarlandes – Informatik
Informatik Campus des Saarlandes
Campus E9 1 (CISPA)
66123 Saarbrücken
E-mail: zeller @ cs.uni-saarland.de
Telefon: +49 681 302-70970

Deutschsprachige Startseite Page d'acceuil en français English home page
  

Hilfen zur Programmierumgebung

Literatur

Das C++-Buch, das wohl die meisten C++-Programmierer genährt hat, ist

Bjarne Stroustrup, “The C++ Programming Language”, Third Edition, Addison-Wesley, ISBN 0-201-88954-4.

Dieses Buch gibt es auch auf Deutsch und sollte in der Fachbereichsbibliothek verfügbar sein. Die meisten Beispiele in der Vorlesung und in den Übungen sind schamlos daraus abgekupfert. Auf Deutsch ist eine vierte Auflage erhältlich, die ich aber nicht kenne.

Nicolai M. Josuttis, “The C++ Standard Library. A Tutorial And Reference”, Addison-Wesley, ISBN 0-201-37926-0.

Die Standard C++-Bibliothek hält umfangreiche Funktionen bereit, die viele Aufgaben übernehmen kann. Gleichzeitig ist diese Bibliothek eines sehr komplexes Software-Werkzeug. Um effektiv mit der Bibliothek umzugehen, brauchen Sie ein Tutorial und eine Referenz. Das Buch von Josuttis bietet beides.

Eine vollständige Referenz für den C++-Sprachstandard, zusammen mit Erläuterungen, finden Sie in

Margaret Ellis, Bjarne Stroustrup, “The Annotated C++ Reference Manual”, ISBN 0-201-51459-1.

Warnung! Nichts für Anfänger!

Hier noch eine Online-Referenz zur Standard Template-Library

Bemerkungen

Diese Übungen werden nicht korrigiert oder benotet. In der Regel werden Sie selber wissen, ob Sie eine Aufgabe erfolgreich gelöst haben oder nicht. Bei Fragen wenden Sie sich bitte an die Betreuuer des Übungsbetriebs, der zu den angegebenen Terminen stattfindet.

Sie sollten immer genügend Stoff zum Üben hier vorfinden. Wenn Sie nicht alle Aufgaben lösen können, verfallen Sie nicht in Panik. Sind die Schwierigkeiten fachlicher Natur? Dann lesen Sie die Folien nochmal. Wenn Sie die Aufgabe immer noch nicht verstehen, fragen Sie unsere Bremser. Haben Sie Schwierigkeiten mit dem Compiler? Fragen Sie Ihre Kommilitonen und/oder unsere Bremser.

Von Zeit zu Zeit werden neue Übungen in die Abschnitte eingefügt. Schauen Sie also ruhig mal bereits bekannte Abschnitte durch, vielleicht finden Sie ja eine neue Aufgabe. Wenn Sie sich nicht erinnern können, die Aufgabe bereits gelöst zu haben, sollten Sie sie vielleicht einfach (noch einmal) versuchen.

Übungen

Beherrschung der Programmierumgebung

Aufgabe 1 (2003-04-28)

Tippen Sie folgendes C++-Programm unter dem Namen “Ex1.cc” ab und bringen Sie es zum Ablauf. Wenn Sie nicht cut-and-paste verwenden, sondern das Programm tatsächlich eintippen, werden Sie dabei vermutlich Fehler machen. Lassen Sie sich die Gelegenheit nicht entgehen! (Wenn Sie das Programm direkt beim ersten Mal fehlerfrei eingetippt haben—oder zu faul waren und doch cut-and-paste verwendet habe—, nehmen Sie einfache Änderungen am Programmtext vor, z.B., indem Sie einzelne Zeichen an verschiedenen Stellen löschen oder einfügen, und beobachten Sie, welche Fehlermeldung Sie bekommen.)
#include <iostream>

int main(int argc, const char *argv) {
  int sum;
  int a;
  int b;

  std::cout << "Please enter a and b: ";
  std::cin >> a >> b;
  sum = a*b;
  std::cout << "The sum of " << a << " and " << b << " is "
            << sum << std::endl;
  return 0;
}
  • Das Programm hat einen Fehler (den Sie sicherlich herausfinden, wenn Sie das Programm übersetzen und einige Male ausführen). Korrigieren Sie ihn.
  • Das Semikolon ist ein unscheinbares Zeichen. Was passiert, wenn Sie es mal weglassen?
  • Was passiert, wenn Sie “std::” weglassen?
  • Was passiert, wenn Sie “<< std::endl” weglassen?
  • Geben Sie Unsinn ein, wenn Sie zur Eingabe aufgefordert werden. Versuchen Sie es mal mit Kommazahlen oder mit Text.
  • Ersetzen Sie die Deklarationen von a und b durch Deklarationen mit Initialisierung:
      int a = 0;
      int b = 0;
    
    Geben Sie erneut Unsinn ein. Passiert jetzt etwas anderes?
  • Ersetzen Sie in den Deklarationen von a, b und sum das “int” durch “double”. Geben Sie jetzt Kommazahlen und Ganzzahlen ein.
  • Versuchen Sie statt * verschiedene andere Operatoren: /, %, &, |
  • (Hinweis: Fügen Sie für die letzten zwei Aufgabenteile die Zeile “std::cout.setf(std::ios::hex, std::ios::basefield);” vor der ersten Benutzung von std::cout ein.)
  • Versuchen Sie mal, ob Sie das Programm zum Ablauf bekommen, wenn Sie statt * den Operator < nehmen (Hinweis: Wenn Sie den Datentyp von sum entsprechend abändern, geht das. Dann ist natürlich sum kein passender Name mehr...)
  • Versuchen Sie mit dem GNU C++-Compiler mal folgendes: “g++ -E Ex1.cc -o Ex1.i”. Schauen Sie danach mal in die neu entstandene Datei “Ex1.i”. Finden Sie Ihren eigenen Code noch wieder? Wo kommt der ganze Rest her?
  • Wenn Sie Schwierigkeiten mit der vorangegangenen Aufgabe haben: Erzeugen Sie eine Datei “Ex2.h”, in die Sie folgendes schreiben:
    int i;
    
    Dann erzeugen Sie eine Datei “Ex2.cc”, in die Sie folgendes schreiben:
    #include "Ex2.h"
    
    int main(int argc, const char *argv[]) {
      i = 3;
    }
    
    Dann tippen Sie “g++ -E Ex2.cc -o Ex2.i” und schauen mal, was nun in Ex2.i steht. Ahnen Sie nun, was “#include” macht?

Typen und Deklarationen

Aufgabe 1 (2003-04-28)

Der sizeof-Operator nimmt einen Datentyp als Argument und liefert als Ergebnis die Größe des Datentyps als Vielfache von char. Nehmen Sie das folgende Programm als Beispiel und modifizieren Sie es, so daß Sie die Größen aller Ihnen aus der Vorlesung bekannten Datentypen erfahren. Diese Größen sind typisch, gelten aber nur für diese Ausführungsumgebung!

Verifizieren Sie, ob die angegeben Größen den in der Vorlesung angegebenen Ungleichungen genügen. (Siehe dazu die Folien.)

#include <iostream>

int main(int argc, const char *argv) {
  std::cout << "Size of int: " << sizeof(int) << std::endl;
}

Aufgabe 2 (2003-04-28)

Finden Sie heraus, welches die kleinsten und größten Werte für char sind.

Aufgabe 3 (2003-04-28)

Wie kann man mit den Ergebnissen aus Aufgabe 1 und einigen wenigen Experimenten herausfinden, was die größten und kleinsten Werte von int, long int, unsigned short usw. sind?

Sind die gewonnenen Erkenntnisse auf float, double und long double übertragbar?

Aufgabe 4 (2003-04-28)

Welches ist, auf dem von Ihnen verwendeten System, der längste gültige Name?

Aufgabe 5 (2003-04-28)

Zeichnen Sie einen gerichteten Graph, in dem die Knoten die fundamentalen Datentypen von C++ sind. Darin seien zwei Knoten T1 und T2 genau dann durch eine Kante verbunden, wenn alle Werte, die im Datentyp T1 darstellbar sind, auch im Datentyp T2 darstellbar sind.

Lösen Sie diese Aufgabe einmal für alle standardkonformen Implementierungen. Versuchen Sie auch, die Grenzen Ihrer besonderen Implementierung von C++ ausfindig zu machen und die Aufgabe für diesen besonderen Fall (der nicht unbedingt standardkonform sein muß!) zu lösen.

Nutzen Sie dafür Ihre Erkenntnisse aus den Aufgaben 1 bis 3.

Aufgabe 6 (2003-05-07)

Mit einer union können Sie mehrere verschiedene Datentypen am gleichen Ort durch Überlagerung speichern. Die Syntax ist dabei dieselbe wie bei struct. Zum Beispiel:
union FloatDouble {
  float f;
  double d;
};
Dieses Beispiel speichert an einer Speicheradresse entweder einen float (beim Zugriff auf den Member f) oder einen double (beim Zugriff auf den Member d).

  1. Finden Sie sizeof(double) heraus
  2. Schreiben Sie eine union, bei der Sie einen double mit einem Array von unsigned char passender Größe überlagern
  3. Schreiben Sie eine Funktion, mit der Sie das Array in hexadezimaler oder binärer Schreibweise ausgeben können
  4. Benutzen Sie diese Funktion, um die binäre Repräsentation einfacher double-Werte (z.B. 0.0, 1.0, 2.0, 1024.0, 0.5, 0.25, 0.3125) herauszufinden

Bonusaufgabe: Auf Intel-CPUs entspricht die Darstellung von Floating-Point-Werten dem IEEE-Standard 754. Lokalisieren Sie den Text des Standards oder ein vergleichbares Dokument) und vergleichen Sie Ihre Ergebnisse (Hinweis: Die Darstellung von Floating-Point-Werten gehorcht in Java per Definition diesem Standard. Möglicherweise finden Sie also in der Java-Sprachdefinition einige Hinweise.)

Aufgabe 7 (2003-05-07)

Schreiben Sie eine Funktion, die eine Gleitkommazahl in dezimaler Schreibweise von std::cin einliest. Schreiben Sie eine Funktion, die eine Gleitkommazahl auf std::cout ausgibt.

Verwenden Sie das Ergebnis aus Aufgabe 9, um herauszufinden, ob Ihre Funktionen idempotent sind, d.h., ob Sie eine Zahl ausgeben und wieder einlesen können, um dasselbe Bitmuster zu erhalten, bzw. ob Sie eine Zahl einlesen und danach ausgeben können, um dieselbe Ausgabe zu erhalten. (Wenn Ihnen das nicht gelingt, versuchen Sie erst mal den Rest der Aufgabe. Wenn Ihnen das auf Anhieb für alle Floating-Point-Werte gelingt, kommen Sie mal beim Lehrstuhl vorbei :-))

Versuchen Sie, den Artikel "How to Print Floating-Point Numbers Accurately" von Guy L. Steele ausfindig zu machen (steht in der Bibliothek...). Bei Steele ist das ganze Problem plötzlich nicht mehr so einfach...

Aufgabe 8 (2003-05-09)

Schreiben Sie eine Funktion, die die Werte in einem Array von float-Werten aufsummiert. Die Funktion soll einen Parameter haben für die Richtung, in der aufsummiert wird (von unten nach oben oder von oben nach unten).

Testen Sie Ihre Funktion mit folgendem Hauptprogramm:

#include <iostream>

enum Direction { down, up };

double sum (float array[], int n, Direction d) {
  // hier kommt Ihr Code hinein
}

int main(int argc, const char *argv[]) {
  const float eps = 1.19209290e-07F;
  float array[] = { eps, eps, 1.0F, 1.0F };
  float sum1 = sum(array, sizeof(array)/sizeof(array[0]), up);
  float sum2 = sum(array, sizeof(array)/sizeof(array[0]), down);

  std::cout.precision(10);

  std::cout << "sum 1 = " << sum1 << ", sum 2 = " << sum2 << std::endl;

  return 0;
}
Was macht der Ausdruck sizeof(array)/sizeof(array[0])?

Bonusfrage 1: Die Zahl eps hat die Eigenschaft, die kleinste positive Zahl mit 1 + epseps zu sein. Wieso ist das relevant dafür, daß die Summen in verschiedenen Richtungen unterschiedlich berechnet werden?

Bonusfrage 2: Wie groß ist der relative Fehler (also der prozentuale Unterschied zwischen den berechneten Lösungen und der korrekten Lösung)?

Bonusfrage 3: Angenommen, alle aufzusummierenden Werte sind größer als Null. Mit welcher Aufsummierungsstrategie bekommt man den relativen Fehler möglichst klein?

Structs

Arrays und Pointer

Aufgabe 1 (2003-04-29)

Schreiben Sie Deklarationen für die folgenden Objekte:
  • Ein Pointer auf ein Zeichen
  • Ein Array von 10 Ganzzahlen
  • Ein Zeiger auf ein Array von Zeichen
Initialisieren Sie jedes Objekt.

Aufgabe 2 (2003-04-29)

Vertauschen Sie zwei Ganzzahl-Variablen. Benutzen Sie dazu folgendes Muster:
#include <iostream>

int main(int argc, const char *argv[]) {
  int a;
  int b;

  std::cout << "Please enter a and b: ";
  std::cin >> a >> b;
  /* Fill in the code here! */
  std::cout << "After the swap, a = " << a << ", b = " << b << std::endl;
}

Schreiben Sie nun eine Funktion, die zwei Variablen vertauscht. Benutzen Sie dazu folgendes Muster:

#include <iostream>

void swap(int* a, int* b) {
  /* Fill in the code here! */
}

int main(int argc, const char *argv[]) {
  int a;
  int b;

  std::cout << "Please enter a and b: ";
  std::cin >> a >> b;
  /* Fill in the code here, use swap() defined above! */
  std::cout << "After the swap, a = " << a << ", b = " << b << std::endl;
}

Aufgabe 3 (2003-04-29)

Welche Größe hat folgendes Objekt?
char str[] = "a short string";
Würde sich etwas an der Größe ändern, wenn man char[] durch char* ersetzte? (Hinweis: Die Antwort lautet “ja”. Die Frage ist natürlich, warum. Zusätzlicher Hinweis: Die Größe eines Objekts und eines Zeigers auf das Objekt hängen nicht notwendigerweise zusammen.)

Funktionen

Aufgabe 1 (2003-04-29)

Definieren, implementieren und testen Sie folgende Funktionen:
  • Eine Funktion times2, die einen int als Parameter erhält und die das Doppelte des Parameters zurückliefert
  • Eine Funktion times2, die einen double als Parameter erhält und die das Doppelte des Parameters zurückliefert. Was passiert, wenn Sie beide Funktionen in derselben Datei definieren?
  • Eine Funktion countBits, die einen unsigned long als Parameter erhält und die Anzahl der eins-Bits in der binären Repräsentation dieser Zahle zurückliefert
  • Eine Funktion isPowerOf2, die einen unsigned long als Parameter erhält und true liefert, wenn es sich bei dem Parameter um eine Potenz von 2 handelt und false sonst. (Hinweis: Wenn x eine von 0 verschiedene ganze Zahl ist, wie hängen dann die binären Repräsentationen von x und x - 1 zusammen, falls x eine (bzw. keine) Potenz von 2 ist?

Aufgabe 2 (2003-05-05)

Zum Begriff der Rekursion: Definieren und implementieren Sie die Fakultäts- und die Fibonaccifunktion. Definieren und implementieren Sie auch die Ackermannfunktion (x und y sind natürliche Zahlen mit x ≥ 0 und y ≥ 0):
  • A(0,y) = y+1
  • A(x+1,0) = A(x,1)
  • A(x+1,y+1) = A(x, A(x+1,y))

Implementieren Sie nicht nur die Rekursion selbst, sondern auch Funktionen, bei denen Sie die Rekursion am Bildschirm verfolgen können, z.B. anhand der Einrücktiefe:

Entering Fib(3)
  Entering Fib(2)
    Entering Fib(1)
    Returning 1
    Entering Fib(0)
    Returning 1
  Returning 2
  Entering Fib(1)
  Returning 1
Returning 3

Aufgabe 3 (2003-05-05)

Bei der Implementierung der Ackermannfunktion oder auch der Fibonaccifunktion wird Ihnen schnell auffallen, daß sehr viele Werte redundant berechnet werden. Um solche Berechnungen zu beschleunigen, gibt es eine Technik namens memoization. Finden Sie heraus (z.B. durch eine Internetrecherche), was das ist und implementieren Sie das für die Fibonaccifunktion und die Ackermannfunktion. Versuchen Sie, herauszufinden, um wieviel die neue Implementierung schneller ist, als die alte. (Hinweis: Verwenden Sie bei der Fibonaccifunktion eine std::map<int, int>. Verwenden Sie diesen Datentyp auch bei der Ackermannfunktion und kodieren Sie ein Zahlenpaar (x,y) durch die Zahl 2x + 3y. Bei den Wertepaaren (x,y), für die A(x,y) noch in einen int paßt, ist hier kein Überlauf zu erwarten. Alternativ können Sie auch eine std::map<std::string, int> verwenden. Dann müssen Sie sich aber auch überlegen, wie Sie ein Zahlenpaar in einen String und wieder zurück kodieren.)

Aufgabe 4 (2003-05-05)

Nutzen Sie die Online-Referenz zur STL und finden Sie heraus, wie man den Datentyp std::map<> benutzt. Schreiben Sie dazu ein Programm, das eine Textdatei in Strings einliest und eine Map dazu benutzt, um zu zählen, wie häufig ein String in der Datei vorgekommen ist. Sortieren Sie die Ausgabe. So sollte z.B. die Eingabedatei
happy with what you have to be happy with
zur Ausgabe
be 1
happy 2
have 1
to 1
what 1
with 2
you 1
führen. Hinweis: Wenn Sie Template-Typen benuzen wollen, müssen Sie beim gcc 2.95 mit der Option “-lstdc++” linken. Ab gcc 3 geht das auch ohne Extra-Option.

Aufgabe 5 (2003-05-06)

Nehmen Sie sich die Folien zur Hand und extrahieren Sie daraus den vollständigen Taschenrechner. Bringen sie ihn zum Ablauf. Welche include-Anweisungen benötigen Sie noch?

Aufgabe 6 (2003-05-06)

Die Verarbeitung des Taschenrechners ist ziemlich empfindlich gegenüber Leerzeichen. Beispielsweise gilt a=3 als Name, a = 3 jedoch als Ausdruck. Modifizieren Sie den Taschenrechner so, daß Leerzeichen nur noch innerhalb von Namen oder Zahlen wichtig sind. Dazu müssen Sie get_token() ändern.

Aufgabe 7 (2003-05-07)

Zerlegen Sie den Taschenrechner wie in der Vorlesung angegeben in Module und bauen Sie das Projekt mit Hilfe eines Makefiles und bringen Sie es zum Ablauf.

Aufgabe 8 (2003-05-07)

Schreiben Sie eine Funktion print(int, int), die einen int-Wert auf std::cout ausgibt. Der zweite Parameter soll dabei die Basis b angeben, zu der der erste Parameter ausgegeben werden soll (1 < b ≤ 36). Die Default-Basis sei 10.

Schreiben Sie ihr Programm so, daß auch negative Zahlen ausgegeben werden können. Welche Probleme treten dabei auf den typischen Zweierkomplementmaschinen auf? (Hinweis: Der Wertebereich eines int ist nicht symmetrisch um 0.)

Templates

Aufgabe 1 (2003-05-09)

Nehmen Sie das Stack-Beispiel aus der Vorlesung (Folie Nr. 130) und bringen Sie es zum Ablauf. Provozieren Sie in einem Beispielprogramm sowohl die StackFull- als auch die StackEmpty-Exception

Aufgabe 2 (2003-05-09)

Erweitern Sie Ihre Klasse aus Aufgabe 1 um eine Methode bool isEmpty() const, die true zurückgibt, wenn der Stack leer ist, sonst false. Implementieren Sie eine analoge Methode isFull().

Impressum Datenschutzerklärung

<webmaster@st.cs.uni-saarland.de> · http://www.st.cs.uni-saarland.de//edu/einst/c++-uebungen.php · Stand: 2018-04-05 13:40