Ruprecht Karls Universität Heidelberg

UebungAufgaben

From Informatik-Vorkurs
Jump to: navigation, search

Auf dieser Seite sind alle Übungen zusammengestellt, die im Kurs gemacht werden. Ich habe bewusst alles auf eine lange Seite gepackt, so dass Sie alle Übungen auf einmal ausdrucken können.

Übung 1: Einloggen & Unix

  • Loggen Sie sich mit Ihrem URZ Account ein.
  • Öffnen Sie ein Terminal (In der Tool Liste unter Zubehör).
  • Schauen Sie nach, welche Files es schon gibt.
  • Erzeugen Sie ein neues Verzeichnis cppkurs (z.B.).
  • Wechseln Sie in das Verzeichnis.
  • Erzeugen Sie darin ein Unterverzeichnis v1 und wechseln Sie dort hin.
  • Starten Sie einen Editor, z.B. gedit, legen Sie ein neues File an, geben Sie etwas Text ein und speichern Sie das File.
  • Welche Dateien gibt es jetzt im Verzeichnis? Ändern Sie etwas und speichern Sie wieder. Welche Files gibt es jetzt?
  • Wechseln Sie ins Verzeichnis cppkurs und legen Sie dort ein weiteres Unterverzeichnis v2 an.
  • Kopieren Sie die Files in v1 nach v2. Schauen Sie von cppkurs aus nach, ob die Files in v2 angekommen sind.
  • Wechseln Sie nach v2 und schauen Sie sich von hier aus an, welche Files es in v1 gibt. Löschen Sie v1.
  • Gehen Sie in den Editor. Ist das File in v2 korrekt angekommen?

Übung 2: Hallo Welt

  • Erzeugen Sie sich (z.B.) in cppkurs ein Unterverzeichnis uebung2 und wechseln Sie dorthin.
  • Öffnen Sie ein File HalloWelt.cc und geben Sie den Code aus der Vorlesung ein. Kopieren Sie nicht, sondern geben Sie alles selbst ein. Überlegen Sie, was jede Zeile macht!
  • Übersetzen Sie das Programm. Wenn Sie Fehler erhalten, arbeiten Sie sie von oben her ab. Lernen Sie, die Meldungen zu verstehen....
  • Binden Sie das Programm und starten Sie es mit ./HalloWelt.
  • Spielen Sie nun mit der Ausgabe. Geben Sie mehrere Teile mit std::cout << xxx << yyy <<... aus (xxx,yyy können Zeichenketten, ganze Zahlen oder Kommazahlen (mit Dezimalpunkt) sein). Erzeugen Sie mehrere Zeilen mit std::endl.

Musterlösung

Übung 3: Kleines Einmaleins

  • Erzeugen Sie sich ein neues Verzeichnis fĂŒr diese Übung.
  • Benutzen Sie zunĂ€chst eine for (...; ...; ...) {...} Schleife, um die Zahlen von 1 bis 10 auszugeben.
  • Probieren Sie es mit einer do {...} while (...); und mit einer while (...) {} Schleife. Was ist hier am elegantesten / einfachsten / sinnvollsten?
  • Was mĂŒssen Sie tun, um die Zahlen untereinander bzw. nebeneinander ausgeben?
  • Nutzen Sie nun eine doppelte Schleife, um das kleine Einmaleins von 1x1 bis 9x9 in Form einer Matrix auszugeben, also
 1  2  3  ...  9
 2  4  6  ... 18
 ...
 9 18     ... 81
  • Nutzen Sie fĂŒr die Laufvariablen sinnvolle Namen, z.B. ix, iy oder izeile, ispalte.
  • IHR Einmaleins sieht wahrscheinlich noch nicht schön aus, da die 'kleinen' Zahlen weniger Platz brauchen als die 'großen' Zahlen. Wir wollen daher die Zahlen mit genau drei Stellen Breite auszugeben (also __1 bzw. _81). Suchen Sie im Internet, z.B. unter http://www.cplusplus.com, nach einer einfachen Möglichkeit. Ist der Befehl .precision richtig? (Tipp: nein, aber der richtige Befehl ist nicht weit...)
  • FĂŒhren Sie Konstanten const int NX = ...; const int NY = ...; zu Beginn des Programms ein, so dass die GrĂ¶ĂŸe einfach verĂ€ndert werden kann. Probieren Sie das z.B. mit 4x3 aus, also:
 1  2  3  4
 2  4  6  8
 3  6  9 12
  • Was mĂŒssen Sie tun, damit die '1' nicht links oben, sondern links unten steht?

Musterlösung

Übung 4: Wurzel aus Zwei

Das Newtonverfahren erlaubt es, die Nullstelle einer Funktion f(x) zu finden, also die Lösung von f(x)=0. Dazu beginnt man bei einer NÀherungslösung x1, berechnet den Funktionswert f(x1) und die Steigung an dieser Stelle m=f'(x1). Die durch den Punkt (x1,f(x1)) gehende Gerade mit der Steigung m schneidet die x-Achse an einer neuen Stelle x2, die (meist) nÀher an der gesuchten Nullstelle liegt.

  • Machen Sie eine Skizze zur obigen Beschreibung und stellen Sie eine Formel auf, mit der x(i+1) aus x(i) berechnet werden kann.
  • Wie mĂŒssen Sie f(x) wĂ€hlen, damit die Nullstelle die Quadratwurzel aus einer Zahl C ist?
  • Schreiben Sie ein Programm, das die Quadratwurzel aus 2 mit dem Newtonverfahren berechnet. Iterieren Sie zunĂ€chst genau 10 Mal (for-Schleife!) und geben Sie die Werte aus.
  • Iterieren Sie dann so lange, bis sich die Zahl 'kaum noch' verĂ€ndert, oder bis das Quadrat des Ergebnisses 'nahe' an 2 liegt.
  • Achten Sie bei der Abbruchbedingung darauf, dass der Korrekturwert auch negativ sein kann!
  • Was passiert, wenn Sie zu 'strenge' Genauigkeitsanforderungen stellen? Stellen Sie sicher, dass Ihr Programm nach einer maximalen Anzahl von Iterationen immer abbricht.
  • Geben Sie auch aus, wie viele Iterationen nötig waren.
  • Wie können Sie die dritte Wurzel berechnen?

FĂŒr Interessierte: Die direkte Newton Iteration fĂŒr sqrt(c) mit f(x) = x²-c benötigt bei jeder Iteration eine Division durch x. Das ist insbesondere bei sehr langen oder prĂ€zisen Zahlen rechenaufwĂ€ndig. Alternativ kann man ausnutzen, dass sqrt(c) = c / sqrt(c) ist und zunĂ€chst 1/sqrt(c) berechnen, was auf den ersten Blick schwieriger erscheint... Es geht aber z.B. mit f(x) = 1/x² - c, wobei nun jede Iteration nur noch eine (triviale) Division durch 2 benötigt! Insgesamt bekommt man sqrt(c) so viel schneller! → Musterlösung

Übung 5: Teiler

  • Schreiben Sie ein Programm, das fĂŒr die Zahlen N = 2..20 alle Teiler (!=N) ermittelt. Die Ausgabe soll so aussehen:
Zahl:  2  Teiler: 
Zahl:  3  Teiler: 
Zahl:  4  Teiler: 2
...
Zahl:  6  Teiler: 2 3
...
Zahl: 20  Teiler: 2 4 5 10

(Den Rest bei der Division von zwei ganzen Zahlen a, b bekommt man mit a % b.)

  • Was mĂŒssen Sie Ă€ndern, damit auch 1 und N als Teiler angezeigt werden?

Musterlösung

Übung 6: GrĂ¶ĂŸe von int bestimmen

Bestimmen Sie die Anzahl Bits in einer Variable vom Typ int.

  • Beginnen Sie dazu z.B. mit einer 1 (denn bei der ist das Bit ganz rechts ja gesetzt) und schieben Sie so lange nach links, bis Sie Null erhalten (man erhĂ€lt also 1, 2, 4, 8, ...).
  • Geben Sie die die Zwischenergebnisse aus. Warum ist die letzte Zahl negativ? Was passiert bei einem unsigned int?
  • ZĂ€hlen Sie mit, wie oft Sie schieben mussten.
  • Probieren Sie auch aus, wie groß ein short int oder ein char oder ein long long int sind.

Musterlösung

Übung 7: Zahlen im Einmaleins (Zahlen Abhaken, Version 1)

Wie viele verschiedene Produkte kommen im kleinen Einmaleins (1×1 bis 10×10) vor?

  • Wir nutzen dazu ein Feld (array) aus bool Werten an, in dem alle gefundenen Produkte markiert werden.
  • Wie groß muss das Feld sein?
  • Setzen Sie zunĂ€chst alle Elemente auf false.
  • Markieren Sie dann alle Elemente.
  • ZĂ€hlen Sie, wie viele es sind.
  • Achten Sie darauf, dass Sie nicht auf einen verbotenen Index des Arrays zugreifen!
  • Nutzen Sie nun anstelle von bools einen enum Typ mit den Werten NICHT_GEFUNDEN und GEFUNDEN, um das Programm lesbarer zu machen.
  • FĂŒr ganz Schnelle: Die GrĂ¶ĂŸe der Matrix soll nun ĂŒber die Tastatur eingegeben werden. Mit dem Befehl std::cin >> n; unterbricht die ProgrammausfĂŒhrung und eine Zahl aus der Tastatur wird der Variable n zugewiesen. (Um die unterschiedlichen EintrĂ€ge zu zĂ€hlen sollte das bool-Feld spĂ€ter 'dynamisch' angelegt werden. Im Moment können Sie eine maximale GrĂ¶ĂŸe definieren und sicherstellen, dass die Eingabe nicht grĂ¶ĂŸer ist.)

Musterlösung

Übung 8: Sortieren

Weil wir schon so weit sind, hier was zum Nachdenken und 'Konsolidieren':

Sie sollen ein Feld aus N=10 Zahlen aufsteigend sortieren. Dazu gibt es SEHR viele Möglichkeiten. Wir machen es einfach, aber ineffizient:

  • Starten Sie bei der ersten Position des Feldes, merken Sie sich den Wert dort, und suchen Sie das Feld dann bis zum Ende nach kleineren Zahlen durch.
  • Sollten Sie einen kleineren Wert finden, so merken Sie sich den Wert und die Position.
  • Nach Durchsuchen des Feldes tauschen Sie den kleinsten Wert mit dem ersten Wert. Damit ist sicher gestellt, dass die erste Zahl 'richtig' ist.
  • Wiederholen Sie das, indem Sie von der zweiten, dritten, .. Position starten, bis das Feld ganz abgearbeitet ist.

Zum Speichern der Elemente definieren Sie sich z.B. ein Feld number[] = {9,4,4,1,10,...} mit GENAU 10 EintrÀgen. Definieren Sie sich auch eine Konstante SIZE=10, um den Code lesbarer und wartbarer zu machen.

Musterlösung

Übung 9: Spirale zeichnen

Wir wollen ein Postscript File erzeugen, das eine Spirale zeichnet. (Postscript ist ein spezielles Fileformat, das z.B. von vielen Druckern verstanden wird, so dass Sie solch ein File direkt drucken können.)

  • Erzeugen Sie ein File test.ps mit folgendem Inhalt (Sie können den Text direkt aus Ihrem Browser ins File kopieren).
 %!PS-Adobe-3.0 EPSF-3.0
 %%BoundingBox: 0 0 595 842
 2.835 dup scale
 5 dup translate 
 0.1 setlinewidth
 newpath 0 0 moveto 0 287 lineto 200 287 lineto 200 0 lineto closepath stroke     
 100 143.5 translate
 showpage
  • Dies ist ein korrektes Postscript File, das Sie z.B. mit gv test.ps & oder evince test.ps & anschauen können, und das Sie auch auf einem Postscript Drucker ausgeben können. Mehr ĂŒber die Programmiersprache Postscript können Sie z.B. [hier] finden.
  • Schreiben Sie nun ein Programm, das dieses File erzeugt, d.h. nach Ablauf des Programms soll sich ein neues File im Directory befinden. Benutzen Sie dazu einen ofstream. Schauen Sie im Web (http://www.cplusplus.com/reference/iostream/ofstream/) nach, wie man ein File öffnet (Tipp: ofstream f, f.open("...");). Die Ausgabe erfolgt wie bisher auf die Konsole mit f << "text...";. Achtung: Damit das Postscript File richtig funktioniert, muss das erste Kommando ('%!PS...') in einer eigenen Zeile stehen. (Die anderen Befehle sind unkritisch.)
  • Eine Linie erzeugt man in Postscript (vereinfacht) mit x1 y1 moveto x2 y2 lineto stroke (x1-y2 sind natĂŒrlich Zahlenwerte!). In unserem Fall liegt der Ursprung in der Blattmitte und der Wertebereich fĂŒr x und y ist etwa ±100. Die Zeichenbefehle mĂŒssen vor dem showpage Kommando und hinter dem translate Befehl eingefĂŒgt werden (entfernen Sie nichts aus dem File!). Probieren Sie das von Hand aus.
  • Schreiben Sie eine Funktion, die eine Linie von einem Punkt (x1/y1) zu einem Punkt (x2/y2) zeichnet. Ändern Sie damit Ihr Programm ab, so dass es mehrere Linien zeichnet. Den nötigen ofstream definieren Sie entweder global (also oberhalb von main()), oder Sie ĂŒbergeben ihn als Parameter, den Sie durch linie(ofstream & f, ...) deklarieren.
  • Zeichen Sie eine Spirale. Arbeiten Sie dazu in Polarkoordinaten und setzen Sie z.B. r(phi) = a + b * phi. Rechnen Sie dann r(phi) in (x/y) um. cos(x) und sin(x) bekommen Sie nach Einbinden von #include <cmath>. Die notwendige for-Schleife können Sie direkt mit einem float schreiben: for (float phi=0; phi < 2 * M_PI; phi+=0.1){...}. Um mit kurzen LinienstĂŒcken arbeiten zu können definieren Sie sich z.B. xalt/yalt und yneu/yneu, berechnen jeweils die neuen Werte, zeichnen eine Linie von alt nach neu und weisen dann neu auf alt zu.
  • Evtl.: Definieren Sie sich nun einen Typ Punkt mit einer x- und einer y-Koordinate und verwenden Sie diesen Typ.
  • Evtl.: Lagern Sie das Zeichnen der Spirale in eine weitere Funktion aus, die Sie z.B. ZeichneSpirale(f, x, y, r, nturn, richtung) aufrufen. richtung könnte dabei ein enum mit möglichen Werten RECHTSRUM oder LINKSRUM sein.

Musterlösung

Übung 10: Vector Routinen

Die folgende Übung ist nicht sehr spannend, aber nĂŒtzlich. Sie sollen damit etwas Routine in der Definition von Funktionen und im Überladen von Operatoren bekommen. Wir wollen einen Datentyp 'zweidimensionaler Vektor' definieren, der eine x- und eine y-Komponente hat.

  • Definieren Sie vor dem Hauptprogramm die Struktur xyvect.
  • Deklarieren Sie im Hauptprogramm zwei Instanzen des Typs xyvect, weisen Sie Komponenten zu und geben Sie Komponenten aus.
  • Definieren Sie vor dem Hauptprogramm eine Funktion PrintVector, die den xyvect auf der Konsole ausdruckt. Vereinfachen Sie Ihr Hauptprogramm.
  • Definieren Sie nun eine Funktion ClearVector, die beide Komponenten auf Null setzt. Probieren Sie das im Hauptprogramm aus, indem Sie zunĂ€chst die Komponenten 'von Hand' auf (1,1) setzen, den Vektor ausgeben, und dann ClearVector rufen.

Wir wollen nun dieses Problem systematischer angehen und die Vector Funktionen in ein seperates File auslagern:

  • Legen Sie die Files xyvect.h, xyvect.cc und vector_test.cc an. Im header -file xyvect.h wird deklariert, was es alles gibt. In xyvect.cc werden die Vektor-Routinen implementiert. In vector_test.cc wenden wir die Routinen an.
  • Definieren Sie die Struktur xyvect im xyvect.h file .
  • Deklarieren Sie dort auch die folgenden Operatoren / Funktionen.
    • Eine Funktion betrag(xyvect) (Ergebnistyp?).
  • Implementieren Sie nun diese Funktionen in xyvect.cc. #includen Sie zu Beginn des xyvect.cc - Files den Header xyvect.h (mit #include "xyvect.h"), denn der enthĂ€lt ja die Definition der Struktur.
  • Schreiben Sie nun in vector_test.cc ein main() - Programm, das die obigen Funktionen verwendet.
  • Beachten Sie: Die beiden *.cc Files werden jetzt getrennt compiliert und dann mit g++ -o test vector_test.o xyvect.o zusammen gebunden.

FĂŒgen Sie nun weitere Operatoren hinzu:

    • Einen + Operator (wie ist der Ergebnistyp?).
    • Einen * Operator fĂŒr float * xyvect (Ergebnistyp?).
    • Einen * Operator fĂŒr xyvect * xyvect (Ergebnistyp?).
    • Einen stream Operator <<.

Definieren Sie im Hauptprogramm zwei Vektoren und einen Skalar und probieren Sie die obigen Operationen aus. Probieren Sie (fĂŒr ein float x und einen Vektor v) aus: x * v bzw. v * x. → Musterlösung

Übung 11: Wurf

In dieser Übung sollen Sie numerisch berechnen, fĂŒr welchen Abwurfwinkel phi die Wurfdistanz maximal wird. Wir werfen also eine Masse vom Ursprung pos=(0,0) aus mit einem Startwinkel phi (gegen die Horizontale) und einer Startgeschwindigkeit (Betrag) von 10 m/s los. FĂŒr kleine Zeitschritte dt=0.1s berechnen wir, wie sich die Position pos und die Geschwindigkeit v (im Einfluß des Schwerefeldes der Erde) verĂ€ndern. Wir wiederholen dies, bis die y-Koordinate von pos negativ wird.

  • Nutzen Sie die xyvect Routinen, um das Problem zu lösen. Definieren Sie sich z.B. drei Vektoren s, v, a (fĂŒr Position, Geschwindigkeit und Beschleunigung), die Sie mit den richtigen Werten (zu Beginn des Wurfs) initialisieren. Beachten Sie, dass die Winkelfunktionen in der <cmath> Bibliothek Argumente in Bogenmaß (rad) erwarten! Dann wiederholen Sie s = s + v * dt, v = v + a * dt.
  • Schreiben Sie nun eine Schleife, die mit ansteigenden Winkeln wirft. Erzeugen Sie eine Ausgabe der Form Winkel = ... Grad, Wurfweite = ... Meter. Berechnen Sie zunĂ€chst Winkel zwischen 5 und 90 Grad in Schritten von 5 Grad.
  • Lagern Sie die Ausgabe fĂŒr einen Winkel (mit Berechnung der Wurfweite) in eine Funktion aus!

Musterlösung

Übung 12: Zahlen abhaken mit Klasse

In Übung 7 wurde ein array aus bool verwendet, um zu vermerken, welche Zahlen gefunden wurden. Wir wollen nun eine Klasse ScoreBoard schreiben, in der wir einzelne Elemente 'abhaken' können. Benutzen Sie als Hauptprogramm folgenden Code:

#include <iostream>
#include "ScoreBoard.h"               // Deklaration des Scoreboards

int main()
{
  const int N = 10;                   // GrĂ¶ĂŸe
  const int NN = N * N;
  ScoreBoard SB;                      // Scoreboard erschaffen & initialisieren
  
  for (int iy = 1; iy <= N; iy++) {
    for (int ix = 1; ix <= N; ix++) {
      std::cout.width(3);
      std::cout << ix * iy;           // Wert ausgeben
      SB.set(ix * iy - 1);            // Eintrag markieren
    }
    std::cout << std::endl;
  }
  
  std::cout << "Es gibt " << SB.count() << " verschiedene Produkte." << std::endl;
  return 0;
}
  • Legen Sie die files ScoreBoard.cc und ScoreBoard.h an.
  • Deklarieren Sie in ScoreBoard.h die Klasse ScoreBoard mit den benötigten Methoden und Datenelementen (vergessen Sie den Konstruktor nicht!). Die Markierungen sollen zunĂ€chst wieder in einem array von bool abgelegt werden, das Sie am Besten im private deklarieren. Arbeiten Sie zunĂ€chst mit einer festen GrĂ¶ĂŸe des Scoreboards, die hier 100 sein muss, also bool arr[100]. (Das ist nicht schön, da die GrĂ¶ĂŸe des Einmaleins und des Scoreboards 'passen' mĂŒssen. Wir verbessern das spĂ€ter durch dynamische Erzeugung des Arrays mit beliebiger GrĂ¶ĂŸe.)
  • In ScoreBoard.cc implementieren Sie nun die Klasse.
  • Im Konstruktor mĂŒssen Sie alle EintrĂ€ge des Arrays löschen (Schleife!).
  • Die Methode set(i) soll den i-ten Eintrag markieren. Stellen Sie evtl. sicher, dass bei unerlaubten Argumenten (<0 oder >=100) nichts passiert.
  • Die Methode count soll die Anzahl der gesetzten EintrĂ€ge zurĂŒckgeben.
  • Probieren Sie das nun aus! Übersetzen Sie das Hauptprogramm und ScoreBoard.cc getrennt und binden Sie beide zusammen.

Sie können nun versuchen, die GrĂ¶ĂŸe des Scoreboards variabel zu machen, indem Sie das Array dynamisch anlegen

  • Um sich die GrĂ¶ĂŸe zu merken, benötigen Sie eine weitere (private) Klassenvariable unsigned int size.
  • Der Konstruktor hat nun ein Argument, den maximalen Eintrag im Scoreboard. Diesen merken Sie sich in size. Das Array deklarieren Sie als bool * arr in ScoreBoard.h. Im Konstruktor erschaffen Sie dann das Array mit arr = new bool[size] und löschen anschließend den Inhalt.
  • In set(int) nutzen Sie nun size zur Sicherheitsabfrage.
  • Sie benötigen nun auch einen Destruktor, der den Speicherplatz des Array mit delete[] arr; wieder frei gibt (das Array 'zerstört').

FĂŒr ganz Schnelle: Erzeugen Sie nun eine Kopie ScoreBoard2.cc und ScoreBoard2.h und verĂ€ndern Sie die Klasse so, dass pro Eintrag nur noch ein Bit benötigt wird. Legen Sie dazu die Bits in ints ab, in denen Sie jeweils das richtige Bit setzten. Da ein int 32 Bit hat, benötigen Sie fĂŒr 96 EintrĂ€ge also z.B. nur 3 ints.

  • Berechnen Sie, wie viele ints Sie brauchen (Vorsicht!)
  • Passen Sie den Konstruktor an.
  • Ändern Sie set. Kommen Sie evtl. ohne Division aus (&, >>)?
  • Ändern Sie count. Das ZĂ€hlen der gesetzten Bits ist ein Problem, fĂŒr das es einige sehr schlaue Tricks gibt, die unter Tipps & Tricks zusammengestellt sind.
  • Was Ă€ndert sich in Ihrem Einmaleins Programm, wenn Sie ScoreBoard2 nutzen?

Musterlösung

  • Erzeugen Sie nun das ScoreBoard im Hauptprogramm dynamisch. Was Ă€ndert sich?

Übung 13: Das Spiel des Lebens

Im 'Spiel des Lebens' (http://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens) befinden sich auf den Feldern einer Schachbrett-Ebene einzelne 'Individuen', die von Generation zu Generation ĂŒberleben oder sterben. Was mit einem Individuum geschieht hĂ€ngt vom Zustand seiner 8 Nachbarfelder ab (das Feld des Individuum zĂ€hlt also nicht mit):

  • Wenn weniger als 2 oder mehr als 3 Nachbarn vorhanden sind, stirbt ein Individuum (es verschwindet).
  • Wenn genau 3 Nachbarn um ein leeres Feld herum vorhanden sind, so wird ein neues Individuum geboren (oder das dort schon vorhandene ĂŒberlebt).

Schreiben Sie ein Programm, das diesen Ablauf umsetzt.

  • Definieren Sie sich eine Welt aus NX x NY Feldern. Betrachten Sie die Welt als zyklisch geschlossen (Torus): Der linke Nachbar von ix=0 ist nicht mehr ix=-1 (das es nicht gibt), sondern ix=NX-1 etc. Auf diese Art und Weise hat man am Rand keine SonderfĂ€lle. Die richtigen Indizes bekommen Sie durch eine Modulo Operation. ACHTUNG: Da -1 % N kein sinnvolles Ergebnis ergibt, kann man z.B. (ix + NX - 1) % NX schreiben.
  • Beachten Sie bei der Berechnung der neuen Generation, dass Sie die Welt erst verĂ€ndern können, wenn Sie ALLE Nachbarschaften gezĂ€hlt haben!
  • Implementieren Sie eine Klasse mit folgendem Headerfile T_life.h:
const int NX = 10;
const int NY = 8;
class T_life {
public:
       T_life (void);            // Konstruktor. Soll die Welt löschen.
  void print  (void);            // Die Welt ausdrucken
  void set    (int ix, int iy);  // Setze ein Individuum (Bereich prĂŒfen!)
  void iterate(void);            // iterate once
  void iterate(int n);           // iterate n times
private:
  bool world_old[NX][NY];        // Aktuelle Welt      
  bool world_new[NX][NY];        // NĂ€chste Iteration
};
  • Probieren Sie das an einzelnen Individuen, einem Block aus 2x2, einem Block aus 1x3 und dem 'Gleiter' (s. Webseite oben) aus!
  • Evtl.: Definieren Sie eine weitere Klassenmethode, die eine Figur ins Feld setzt, also z.B. void place(int ix, int iy, T_Shape shape), wobei T_Shape ein enum ist, der verschiedene Formen identifiziert.
  • Evtl.: Wahrscheinlich berechnet Ihr Programm fĂŒr jedes Feld die Summe der 8 Nachbarn (das ist nahe liegend), es sind also pro Generation 8×NX×NY Zugriffe auf 'world' notwendig. Das ist sehr ineffizient, da die Welt in der Praxis fast leer ist. Überlegen Sie, ob man sich stattdessen die Nachbarschaftssummen merken könnte und diese nur dann verĂ€ndert, wenn ein Individuum entsteht oder stirbt. Hinweise dazu bekommen Sie auf der Tipps & Tricks Seite.

Musterlösung

Übung 14: Labyrinth

In der Vorlesung wurde ein Programm erstellt, mit dem man durch Zimmer gehen kann:

#include <iostream>
#include <string>
using namespace std;

class room {
public:
  room (string n) {name = n; N = this; S = this; O = this; W = this;};
  string name;
  room * N, * S, * O, * W;
};

int main() 
{
  room r1("Bad");
  room r2("Esszimmer");
  room r3("Wohnzimmer");
  room r4("Schlafzimmer");
  r1.N = &r2; r2.W = &r1; r2.O = &r3;
  r3.N = &r4; r4.S = &r2; r4.O = &r3;
  room * here = &r1;
  bool done = false;
  do {
    cout << "Sie sind im " << here->name << ". Es gibt Wege nach";
    if (here->O != here) cout << " O";
    if (here->W != here) cout << " W";
    if (here->N != here) cout << " N";
    if (here->S != here) cout << " S";
    cout << ". Wohin? (X:exit)" << endl;
    string in;
    cin >> in;
    switch (toupper(in[0])) {           // in[0] ist der erste Buchstabe der Eingabe.
      case 'N': here = here->N; break;  // toupper() konvertiert zu einem Großbuchstaben
      case 'S': here = here->S; break;
      case 'O': here = here->O; break;
      case 'W': here = here->W; break;
      default: done = true; cout << "Tschuess!\n"; break;
    }
  } while (!done);
}
  • Kopieren Sie sich das Programm in ein .cc file und probieren Sie es aus.
  • Rekonstruieren Sie den Zimmerplan aus dem Programm und malen Sie ihn auf!
  • In welchem Zimmer starten wir? Beginnen Sie stattdessen im Schlafzimmer!
  • FĂŒgen Sie einen Ausgang hinzu. Diesen können Sie wie ein normales Zimmer definieren. Beenden Sie das Programm, wenn der Spieler den Ausgang erreicht hat.
  • Lagern Sie die erste Ausgabe ('Sie sind im ... es gibt Wege ...') in die room Klasse in eine Methode PrintInfo(void) aus.
  • Bisher sind die ri vom Typ room. Verwenden Sie fĂŒr r1, r2 nun stattdessen Zeiger auf room, also room * r1. Was mĂŒssen Sie Ă€ndern? Was ist 'schöner'? Verwandeln Sie alle ri in Zeiger!
  • In einem Spiel sollen manche Zimmer nur wenige Male besucht werden dĂŒrfen. FĂŒgen Sie den Zimmern einen ErlaubteBesuche Eintrag hinzu. Initialisieren Sie ihn geeignet und sorgen Sie fĂŒr das richtige Verhalten beim Spiel.

Freiwillig:

  • Lagern Sie auch das Nachschlagen des nĂ€chsten Raumes (als Funktion eines Buchstabens) in die Klasse aus.
  • Es soll nun ein Zimmer mit 100 AusgĂ€ngen geben. Mit der derzeitigen Struktur geht das nicht, da wir immer genau vier AusgĂ€nge nach N,S,O,W haben. Die Anzahl und die Namen der AusgĂ€nge sollen jetzt variabel sein. Definieren Sie einen Typ 'door' mit einem Namen und einem Zeiger auf das dahinterliegende Zimmer (oder NULL, wenn dahinter kein Zimmer ist). FĂŒgen Sie den Zimmern nun eine variable Menge TĂŒren hinzu, z.B. indem Sie z.B. eine list aus der STL nutzen. Bauen Sie das Programm entsprechend um.

Musterlösung

Übung 15: Taschenrechner in der Kommandozeile

Wir wollen nun einen einfachen Taschenrechner calc programmieren, der + und x in Umgekehrt Polnischer Notation (UPN) verarbeitet, der also z.B. bei calc 1 2 + den Wert 3 ausgibt, oder bei calc 1 2 3 x + den Wert 7 ausgibt.
Wenn Sie Ihr Programm calc in der Kommandozeile mit nachfolgenden Parametern aufrufen, also z.B. calc 3 2 +, so werden diese als Array von C-Strings (char *) ĂŒbergeben. Das nullte Element (im Beispiel) im Array ist calc, das erste Element 3, dann 2 und so weiter. Die Deklaration von main und die Extraktion der Parameter geht z.B. so:

 int main (int argc, char* argv[])
 {
   cout << "Anzahl parameter = " << argc << endl;
   for (int i=0; i<argc; i++)
     cout << "Parameter" << i << ": " << argv[i] << endl;
 }

Die Strings können Sie mit der Funktion atoi in integers verwandeln.

  • Probieren Sie das aus. Finden Sie heraus, was Sie #includen mĂŒssen, damit der Compiler atoi findet.
  • Was macht atoi mit Buchstaben?
  • Suchen Sie nach einer Ă€hnlichen Routine, mit der Sie floats einlesen können.

Erste Version des Taschenrechners (mit array)

  • Wir legen die eingegebenen Zahlen zunĂ€chst in einem Array ab. Legen Sie die LĂ€nge als const int N = 10 Konstante fest und deklarieren Sie ein float array.
  • Wenn Sie einen Operator (+ oder x) finden, wenden Sie ihn auf die letzten zwei Zahlen an (falls mindestens 2 Zahlen vorhanden sind!). Um zu prĂŒfen, ob das eingegebene (i-te) Element einer der Operatoren ist, können Sie z.B. den ersten Buchstaben von argv[i] anschauen, also z.B. argv[i][0]=='x' prĂŒfen.
  • ACHTUNG: Die Shell (Ihr Eingabefenster) wertet manche Zeichen aus, bevor sie an Ihr Programm ĂŒbergibt. Daher kann man NICHT den Buchstaben * verwenden. Verwenden Sie zur Multiplikation stattdessen z.B. x!
  • Wenn das eingegebene Element kein Operator ist, so ist es eine Zahl, die Sie konvertieren und ins Array einfĂŒllen. Achten Sie darauf, dass das Array nicht ĂŒberlĂ€uft.
  • Nach Abarbeiten aller Eingabeelemente geben Sie den 'obersten' Wert im Array aus (falls das Array nicht leer ist).
  • PrĂŒfen Sie, dass problematische Eingaben sinnvoll behandelt werden, z.B. calc 3 + oder einfach calc ohne Argumente.

Zweite Version des Taschenrechners (mit dynamisch angelegter Liste)

Die erste Version ist unschön, da die LĂ€nge des Arrays festliegt. Bei kurzen Eingaben ist das Verschwendung, lange Eingaben funktionieren nicht. Wir wollen daher einen Stapel (stack) programmieren, in den die Elemente wie auf einem BĂŒcherstapel aufeinander gelegt werden. Die Operationen verarbeiten die obersten Elemente.

  • Definieren Sie die Struktur
struct StackElement {
  StackElement * below;
  float          value;
};
  • Legen Sie im Hauptprogramm einen Pointer auf ein StackElement mit dem Namen top an, der zunĂ€chst NULL ist. top zeigt immer auf das oberste StackElement im Stapel. Die Zeiger below in den StackElementen zeigen jeweils auf das darunter liegende Element. Der Zeiger des untersten Elements ist NULL.
  • Bei einer Zahleneingabe erzeugen Sie ein neues StackElement mit ... = new StackElement. Weisen Sie value die Zahleneingabe zu und verknĂŒpfen Sie das neue Element so, dass es oben auf dem Stack liegt (Sie mĂŒssen dazu dessen below pointer und top anpassen.)
  • Bei einem Operator prĂŒfen Sie zunĂ€chst, dass es mindestens 2 Elemente auf dem Stapel gibt. Addieren Sie dann den Wert des obersten (das, auf das top zeigt) zur darunter liegenden value. Löschen Sie dann das oben liegende Element mit delete und setzen Sie top richtig. (Hier mĂŒssen Sie aufpassen!)
  • Wenn alle Eingabewerte abgearbeitet sind, geben Sie das oberste Element des Stapels aus.

Dritte Version des Taschenrechners (mit Stapel aus der STL)

In der STL ist bereits ein Stapel (stack) implementiert. Diesen wollen wir nun nutzen.

  • Kopieren Sie sich die Zweite Version in ein File:
#include <iostream>
#include <cstdlib>                 // for atoi
using namespace std;

struct StackElement {
  StackElement * below;
  float          value;
};

int main (int argc, char* argv[])
{
 StackElement * top = NULL;       // points to top of stack
 StackElement * s;                // temporary variable
                          
 for (int i=1; i<argc; i++) {     // process all arguments
   bool add = argv[i][0] == '+';  // see if it is a command
   bool mul = argv[i][0] == 'x';
   if ( add || mul) {             // it is either command
     if ( top && top->below) {    // if (top)  <->  if (top != NULL)
                                  // NOTE: if top==NULL  -> the second
                                  // check is not applied! 
       if (add) top->below->value += top->value;
       if (mul) top->below->value *= top->value;
       s = top->below;            // remember the pointer
       delete top;                // get rid of top element
       top = s;                   // and point to element below
     }
   } else {                       // it is a number
     s = new StackElement;        // create a new entry
     s->value = atof(argv[i]);
     s->below = top;
     top = s;
   }
 }
 
 if (top) cout << "Ergebnis: " << top->value << endl;
}

Musterlösung

Übung 16: Zahlenabhaken unter Benutzung einer Menge

In Übung 12 wurde zum Abhaken der Zahlen im Einmaleins eine Klasse 'ScoreBoard' geschrieben.

  • Ersetzten Sie diese durch ein set aus der stl.
  • Lesen in der Dokumentation zu set nach, wie groß der (zeitliche) Aufwand zum EinfĂŒgen ist.
  • Diskutieren Sie, was die Vor- und Nachteile der drei Lösungen (ScoreBoard mit array von bool, ScoreBoard mit array von Bitmustern oder set) sind!

Musterlösung


Personal tools