Ruprecht Karls Universität Heidelberg

UebungLoesungen

From Informatik-Vorkurs
Jump to: navigation, search

(Zur Hauptseite, zur Übungsseite)

Übung 1: Unix

kommt (vielleicht) noch...

Übung 2: Hallo Welt

Zur Aufgabe

#include <iostream>    // zur Ausgabe von Streams

int main (void)        // Hauptprogramm (ohne Argumente)
{
  float pi = 3.141;
  int    i = 3.9;      // i ist 3!
  std::cout << "Hallo Welt!" << std::endl;
  std::cout << "Ein float: " << pi;
  std::cout << " und ein int: " << i << '\n';
  return 0;
}

Übung 3: Kleines Einmaleins

Zur Aufgabe

#include <iostream>
using namespace std;   // 'std::' kann man damit weglassen...

int main (void)
{
  const int NN = 10;   // Zeige 1 ... (NN-1) an!
  
  for (int izeile=1; izeile<NN; izeile++)  // lokale Definition von 'zeile'!
  {
    for (int ispalte=1; ispalte<NN; ispalte++)
    {
      cout.width(3);   // AusgabelÀnge auf 3 Zeichen festlegen
      cout << ispalte * izeile; 
    }
    cout << endl;      // Zeilenumbruch am Ende einer Zeile erzeugen
  }
  return 0;            // Ende ohne Fehler melden
}

Übung 4: Wurzel aus Zwei

Zur Aufgabe

#include <iostream>

// Finde die Quadratwurzel von r als Nullstelle von f(x) = x * x - r.
// Newton's Iteration beginnt bei Startwert x und errechnet daraus einen
// besseren Wert x - f(x)/f'(x) = x - (x*x-r)/(2*x)

int main( void )
{
  std::cout.precision(10);          // Anzahl Stellen in der Ausgabe
  const float r = 2.0;              // Berechne Wurzel aus 2 (als Beispiel)
  float x = r/2;                    // Ein 'guter' Startwert (?)
  float delta;                      // Speichere hier die Änderung
  int   iter = 1;                   // ZĂ€hle Iterationen hier
  const float ERR = 0.00001;        // Iteriere bis Änderungen < ERR
  const int   MAXITER = 20;         // limitiere Zahl an Iterationen
  do {
    delta = (x * x - r) / (2 * x);  // Änderung berechnen
    x -= delta;                     // Neuer x-Wert
    if (delta < 0) delta = -delta;  // Betrag von delta (alternativ: fabs(..) aus <cmath>)
    std::cout << "Schritt " << iter << ": " << x << "\n";
  } while ( (delta > ERR) && (iter++ < MAXITER));  // Änderung klein oder max. Iteration
  
  return 0;
}

Übung 5: Teiler

Zur Aufgabe

#include <iostream>    // zur Ausgabe von Streams
#include <iomanip>     // fĂŒr setw()

int main (void)
{
  for (int row=2; row<=20; row++) {               // Zeilen durchlaufen
    std::cout <<"Zahl:" << std::setw(3) << row;   // Zahlen ausgeben
    std::cout << "  Teiler:";                     // Ausgabe Teiler vorbereiten 
    for (int i=2; i<row; i++)                     // Alle möglichen Teiler ausprobieren
//  for (int i=2; i<=row/2; i++)                  // effizienter!
//  for (int i=1; i<=row; i++)                    // zur Ausgabe von 1 und 'N'
      if (row%i == 0) std::cout << " " << i;      // Teiler ausgeben, wenn Division ohne Rest
    std::cout << '\n';                            // Zeilenende
  }
  return 0;
}

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

Zur Aufgabe

#include <iostream>
using namespace std;

int main(void)
{
  int          itest = 1;     // Zahl, mit der wir testen
  unsigned int nbit  = 0;     // ZĂ€hler fĂŒr Anzahl Bits
  
  do {
    itest <<= 1;              // nÀchste Zahl
    nbit++;                   // Bits zÀhlen
  } while (itest!=0);         // fertig?
  cout << "Ein 'int' hat " << nbit << " Bits\n";
  
  nbit = 0;                              // andere Variante
  for (short i=1; i!=0; i<<=1) nbit++;   //  fĂŒr short
  cout << "Ein 'short' hat " << nbit << " Bits\n";
  
  nbit = 0;                              // long long int
  for (long long int i=1; i!=0; i<<=1) nbit++;
  cout << "Ein 'long long int' hat " << nbit << " Bits\n";
  
  return 0;
}

Übung 7: Zahlen in Einmaleins

Zur Aufgabe

#include <iostream>

int main(void)
{
  const int N  = 10;                 // GrĂ¶ĂŸe (1..N)
  const int NN = N * N;              // maximale Zahl ist N*N
  bool found[NN];                    // Markiere hier die gefundenen Zahlen
                                     // ACHTUNG: erlaubt ist found[0] .. found[NN-1]
  int charwidth = 2;                 // Zum Spass: ermittle die benötigte Buchstabenbreite
  int t = NN;                        //  fĂŒr beliebige NN
  while (t>=10) {t/=10; charwidth++;}
  
  for (int i=0; i<NN; i++) found[i] = false;  // alle Werte als 'nicht gefunden' markieren

  for (int iy=1; iy <= N; iy++) {    // Einmaleins ausgeben
    for (int ix=1; ix <= N; ix++) {  // s. Kommentar (1)
      std::cout.width(charwidth);
      std::cout << ix * iy;
      found[ix * iy - 1] = true;     // Produkt markieren. S. Kommentar (2)
    }                                // beachte die '-1', um nicht auf found[NN] zuzugreifen
    std::cout << std::endl;
  }
  
  int count = 0;
  for (int i=0; i<NN; i++) if (found[i]) count++;   // Anzahl 'true' zÀhlen
  
  std::cout << "There are " << count << " different numbers" << std::endl;
  return 0;
}

Das dynamische Anlegen des 'found' array geht mit

bool found = new bool[NN];
...
delete[] found;

Verbesserungsmöglichkeiten:

  • Da das Einmaleins symmetisch um die Diagonale ist (wegen ix * iy == iy * ix) muss man nicht alle N*N Elemente durchprobieren: Es reicht, wenn man mit ix jeweils nur bis zur Diagonale (inclusive) geht, also die Zeile (1) durch
for (int ix=1 ; ix <= iy; ix++) {

ersetzt.

  • Man kann die verschiedenen Zahlen auch gleich zĂ€hlen, wenn man sie im found[] array markiert: Man erhöht also count, sobald ein found-Element gesetzt werden soll, das vorher noch nicht gesetzt war. Man ersetzt also (2) durch:
int k = ix * iy - 1;
if (!found[k]) {found[k]=true; count++;}

und spart sich das Aufsummieren. Überlegen Sie, welche Methode effizienter ist....

Übung 8: Sortieren

Zur Aufgabe

#include <iostream>
using namespace std;

int main (void)
{
  const int SIZE = 10;
  int number []  = {1,5,3,8,5,7,3,9,3,10};
  
  for (int startpos = 0; startpos < SIZE; startpos++) {
    int smallest = number[startpos];            // Annahme: kleinste Zahl ist bei startpos
    int ipos     = startpos;                    // Position der 'kleinsten' Zahl merken      
    for (int i=startpos+1; i<SIZE; i++) {       // nach kleineren Zahlen suchen
      if (number[i] < smallest) {               
        ipos = i;                               // Kleienere Zahl gefunden:
        smallest = number[i];                   // Neue Position und den Wert merken
      }
    }
    number[ipos]     = number[startpos];        // Vordere Zahl nach hinten kopieren
    number[startpos] = smallest;                // Kleinste Zahl nach vorne holen
  }
  
  for (int i=0; i<SIZE; i++) cout << number[i] << ' ';
  cout << endl;
  
  return 0;
}

Dieser Algorithmus ist nicht effizient: die Laufzeit steigt quadratisch mit der FeldgrĂ¶ĂŸe N. Es gibt schnelle Algorithmen, die mit N*log(N) skalieren: Wenn der Aufwand fĂŒr ein Feld der LĂ€nge N i.W. N^2 ist, dann kostet das Sortieren von zwei halben Feldern (mit je N/2) nur 2*(N/2)^2 = N^2/2, ist also schneller. (Die zwei sortierten Felder mĂŒssen dann noch gemischt werden, was aber schnell geht). Wenn man das weiter treibt (also die N/2 langen Felder in N/4 lange Felder teilt u.s.w.), so kommt man auf einen sehr effizienten (aber komplizierten) Algorithmus.

Übung 9: Spirale zeichnen

Zur Aufgabe

Einfacher Fall:

#include <fstream>
#include <cmath>
using namespace std;

void linie (fstream & f, float x1, float y1, float x2, float y2)
{
  f << x1 << " " << y1 << " moveto " << x2 << " " << y2 << " lineto stroke\n"; 
}

int main(void)
{
  fstream f;                                // Zeiger zum Outputstream (alternativ: ofstream)
  f.open("spirale.ps", fstream::out);       // File öffnen (hier sollte man prĂŒfen, dass ok!)
  
  f << "%!PS-Adobe-3.0 EPSF-3.0\n";         // 'geheimnisvollen' Postscript Teil ausgeben
  f << "%%BoundingBox: 0 0 595 842\n";
  f << "2.835 dup scale 5 dup translate 0.1 setlinewidth\n";
  f << "newpath 0 0 moveto 0 287 lineto 200 287 lineto 200 0 lineto closepath stroke\n";
  f << "100 143.5 translate\n";
  
  float xalt = 0;                           // x/y Koordinaten des alten Punktes
  float yalt = 0;                           // wir fangen im Ursprung an
  for (float phi=0; phi < 6*M_PI; phi+=0.1){// 3 Umdrehungen (a 2 pi)
    float r = 3 * phi;                      // Spirale: Radius steigt linear mit phi
    float xneu = r * cos(phi);              // Neuen Punkt berechnen
    float yneu = r * sin(phi);
    linie (f, xalt, yalt, xneu, yneu);      // Linie ins Postscript File schreiben
    xalt = xneu;                            // aus alt mach' neu
    yalt = yneu;
  }
  
  f << "showpage\n";                        // Kommando zum Zeichen der Seite
  f.close();
}

Mit Klasse 'Punkt' und ausgelagerter Funktion 'ZeichneSpirale':

#include <fstream>
#include <cmath>
using namespace std;

struct Punkt    {float x,y;};
enum   Richtung {RECHTSRUM, LINKSRUM};

void linie (fstream & f, Punkt p1, Punkt p2)
{
  f << p1.x << " " << p1.y << " moveto " << p2.x << " " << p2.y << " lineto stroke\n"; 
}

void ZeichneSpirale (fstream & f, float x, float y, float rad, int nturn, Richtung dir) {
  Punkt alt = {x,y};
  for (float p=0; p<nturn*2*M_PI; p+=0.1){
    float phi = (dir==LINKSRUM) ? p : -p;
    float r = rad * phi;
    Punkt neu; 
    neu.x = x + r * cos(phi);
    neu.y = y + r * sin(phi);
    linie (f, alt, neu);
    alt = neu;
  }
}

int main(void)
{
  fstream f;
  f.open("spirale.ps", fstream::out);
  f << "%!PS\n";
  f << "2.835 dup scale 5 dup translate 0.1 setlinewidth\n";
  f << "newpath 0 0 moveto 0 287 lineto 200 287 lineto 200 0 lineto closepath stroke\n";
  f << "100 143.5 translate\n";
  ZeichneSpirale (f, 0,  50, 2, 3, RECHTSRUM);
  ZeichneSpirale (f, 0, -50, 1, 4, LINKSRUM);
  f << "showpage\n";
  f.close();
}

Übung 10: Vector Routinen

Zur Aufgabe

xyvect.h:

#include <iostream>                                 // fĂŒr operator<<
struct xyvect {float x,y;};                         // Struktur definieren

// Beachte: Die Parameter vom Typ xyvect sollte man besser
// durchgÀngig als const xyvect & definieren:
// - Kein Kopieraufwand beim Aufruf
// - Sicherheit vor Änderung durch 'const'
// Dies ist exemplarisch in operator+( gezeigt, sonst vereinfachend weggelassen.

xyvect operator+(const xyvect &, const xyvect &);   // vect + vect   -> vect
xyvect operator*(float,  xyvect);                   // skalar * vect -> vect
float  operator*(xyvect, xyvect);                   // vect * vect   -> skalar
float betrag (xyvect);                              // Betrag        -> skalar
std::ostream & operator<< (std::ostream &, xyvect);

xyvect.cc:

#include <iostream>
#include <cmath>
#include "xyvect.h"

xyvect operator+(const xyvect & a, const xyvect & b) {
  xyvect c;
  c.x = a.x + b.x;
  c.y = a.y + b.y;
  return c;
}

float betrag (xyvect v) {
  return std::sqrt(v * v);
}

float  operator*(xyvect v1, xyvect v2){
  return v1.x * v2.x + v1.y * v2.y;
}

xyvect operator*(float x, xyvect v) {
  xyvect c;
  c.x = x * v.x;
  c.y = x * v.y;
  return c;
}

std::ostream & operator<< (std::ostream & os, xyvect v) {
  os << v.x << "/" << v.y;
  return os;
}

test_xyvect.cc:

#include <iostream>
#include "xyvect.h"

int main (void) {
  xyvect v1 = {1,1};
  xyvect v2 = {2,3};
  std::cout << "v1        = " << v1 << std::endl;
  std::cout << "v2        = " << v2 << std::endl;
  std::cout << "v1+v2     = " << v1 + v2 << std::endl;
  std::cout << "v1*v2     = " << v1 * v2 << std::endl;
  std::cout << "Betrag v1 = " << betrag(v1) << std::endl;
  std::cout << "4.0 * v1  = " << 4 * v1 << std::endl;
  return 0;
}

Beide files mĂŒssen getrennt compiliert werden und dann dann mit g++ -o test test_xyvect.o xyvect.o gebunden werden.

Übung 11: Wurf

Zur Aufgabe

#include <iostream>
#include <cmath>
#include "xyvect.h"
using namespace std;

// Einheiten sind Meter und Sekunden
// y zeigt nach oben, also hat der g-Vektor eine negative y Komponente

const float  v0 = 10.0;             // Startgeschwindigkeit in m/s
const float  dt = 0.1;              // Zeitschritt in Sekunden (evtl. kleiner wÀhlen!)
const xyvect g  = {0, -9.81};       // Erdbeschleunigung

void PrintDistance (float angle)    // Winkel (in Grad)
{
  float anglerad = M_PI * angle / 180.0;     // Grad -> Radian
  xyvect v   = {v0 * cos(anglerad), v0 * sin(anglerad)};  // Geschwindigkeitsvektor initialisieren
  xyvect pos = {0, 0};                       // Startposition
  do {                                       // iteriere
    pos = pos + v * dt;
    v   = v   + g * dt;
  } while (pos.y > 0);                       // solange y positv ist
  cout << "Winkel = " << angle << " Grad, Wurfweite = " << pos.x << " Meter \n";
}

int main (void) {
  for (float phi = 5.0; phi < 90.0; phi += 5.0)
    PrintDistance (phi);
  return 0;
}

Übung 12: Zahlen abhaken

Zur Aufgabe

Hauptprogramm:

#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
  
  int charwidth = 2;                  // Ausgabebreite allgemein ermitteln
  int t = NN;
  while (t >= 10) {t/=10; charwidth++;}
  
  for (int iy = 1; iy <= N; iy++) {
    for (int ix = 1; ix <= N; ix++) {
      std::cout.width(charwidth);
      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;
}

Scoreboard.h:

class ScoreBoard {
  public:
                  ScoreBoard (void);          // Konstruktor (setzt alle Werte zurĂŒck)
    void          set        (unsigned int);  // markiere einen Wert
    unsigned int  count      (void);          // gibt Anzahl markierter Werte zurĂŒck
  private:
    bool          arr[100];                   // Array mit FESTER GrĂ¶ĂŸe. HÄSSLICH!
};

Scoreboard.cc:

#include "ScoreBoard.h"

ScoreBoard::ScoreBoard () {
  for (unsigned int i=0; i<100; i++) arr[i] = false;
}
 
void ScoreBoard::set (unsigned int i) {
  if (i>=0 && i<100) arr[i] = true;    // verhindere Zugriffe zu unerlaubten Indizes
}

unsigned int ScoreBoard::count (void) {
  unsigned int sum = 0;
  for (unsigned int i = 0; i < 100; i++) if (arr[i]) sum++;
  return sum;
}

Hauptprogramm mit dynamischer Erzeugung des ScoreBoards:

  ...
  ScoreBoard * SB;                    // Einen Pointer auf ein Scoreboard deklarieren
  ...
  SB = new ScoreBoard(NN);            // das Scoreboard dynamisch erzeugen & initialisieren
  ...
    ...SB->set(...);                  // Zugriff jetzt mit ->, da SB nun ein Pointer ist
  ...
    ...SB->count()...
  ...
  delete SB;                          // weg damit! (Destruktor wird aufgerufen)

Header File fĂŒr dynamische Version - Scoreboard.h:

class ScoreBoard {
  ...
           ScoreBoard (unsigned int); // Konstruktor bekommt gewĂŒnschte GrĂ¶ĂŸe ĂŒbergeben
          ~ScoreBoard (void);         // Neu: Destruktor
  ...
  bool *   arr;                       // Pointer auf Array. Das Array muss erschaffen werden!
};

Implementierung der dynamischen Version - Scoreboard.cc:

... 
ScoreBoard::ScoreBoard (unsigned int n) {
  size = n;                           // GrĂ¶ĂŸe merken
  arr  = new bool[size];              // Array erschaffen
  for (unsigned int i=0; i<size; i++) // Array löschen (wie vorher)
    arr[i] = false;
}
... 
ScoreBoard::~ScoreBoard (void) {
  delete[] arr;
}
...
die anderen Funktionen nutzen size anstelle der Konstanten 100! 
...

Speicher sparende Version Scoreboard2.h:

class ScoreBoard {
  public:
    ScoreBoard (unsigned int);   // Diese Methoden sind nach außen sichtbar
    void set (unsigned int);     // und UNVERÄNDERT. Daher kann man
    unsigned int  count (void);  // #include "ScoreBoard.h" problemlos durch 
    ~ScoreBoard (void);          // #include "ScoreBoard2.h" ersetzen!
  private:
    unsigned int * arr;   //  Das Array
    unsigned int narr;    //  ArraygrĂ¶ĂŸe (in unsigned ints)
    unsigned int max ;    //  höchster erlaubter Eintrag+1
};

Scoreboard2.cc:

#include <iostream>
#include "ScoreBoard2.h"

// Idee zum Sparen von Speicherplatz:
// Nutze die 32 Bit eines unsigned int, um 32 bool werte zu speichern.
// FĂŒr ein ScoreBoard der GrĂ¶ĂŸe 100 benötigen wir nur 4 (=narr) Speicherstellen.
// In der Variable max merken wir uns den grĂ¶ĂŸten erlaubten Eintrag (hier 100).
// (NB: Die Bitbreite eine unsigned int ist hier auf 32 festgelegt, man sollte
// aber besser die tatsÀchliche Maschinenauflösung nutzen.

ScoreBoard::ScoreBoard (unsigned int n) {
  max  = n;
  narr = (n-1) / 32 + 1; // n-1 is the largest entry we have !! should check for n==0!
  arr  = new unsigned int [narr];
  for (unsigned int i=0; i<narr; i++) arr[i] = 0;
}

void ScoreBoard::set (unsigned int i) {
  if (i>=0 && i<max) {       // i   : 0 1 ... 31 32 ..
    int iarr = i / 32;       // iarr: 0 0 ...  0  1 ..
    int ibit = i % 32;       // ibit: 0 1 ... 31  0 ..
    arr[iarr] |= (1<<ibit);
  }
}

unsigned int ScoreBoard::count (void) {   // das geht geschickter (hier nicht verraten!)
  unsigned int sum = 0;
  for (unsigned int iarr = 0; iarr < narr; iarr++) {
    unsigned int value = arr[iarr];
    //    std::cout << std::hex << value << std::endl;
    for (unsigned int ibit = 0; ibit < 32; ibit++) {
      if ((value & 0x1) != 0) sum++;
      value >>= 1;
    }
  }
  return sum;
}

ScoreBoard::~ScoreBoard (void) {
 delete[] arr;
}

NB: Die Implementierung von count() ist nicht effizient. Bessere Methoden sind unter TippsAndTricks erlÀutert.

Übung 13: Das Spiel des Lebens

Zur Aufgabe.

Hier ist zunÀchst eine ganz einfache Lösung gezeigt. Ein paar optimierte Versionen sind auf der Seite Tipps & Tricks zusammengestellt.

#include <iostream>

const int NX = 10;           // FeldgrĂ¶ĂŸe
const int NY = 8;

class T_life {
public:
       T_life (void);
  void print  (void);
  void set    (int ix, int iy);
  void iterate(void);        // einmal iterieren
  void iterate(int n);       // n mal iterieren
private:
  bool world[NX][NY];
};

T_life::T_life (void)        // Konstruktor
{
  for (int ix = 0; ix < NX; ix++)
    for (int iy = 0; iy < NY; iy++)
      world[ix][iy] = false;
}

void T_life::print(void)     // Ausgabe
{
  for (int iy = 0; iy < NY; iy++) {
    for (int ix = 0; ix < NX; ix++)
      std::cout << (world[ix][iy] ? '*' : '.');
    std::cout << std::endl;
  }
  std::cout << std::endl;
}

void T_life::set(int ix, int iy)   // Ein Feld setzten
{
  world[ix][iy] = true;
  // world[(ix+NX)%NX][(iy+NY)%NY] = true;// Mit Test der Grenzen. Details s.u.
}

void T_life::iterate(void)
{
  int neigbors[NX][NY];                   // Speichere die Nachbarsumme hier
  for (int iy = 0; iy < NY; iy++)
    for (int ix = 0; ix < NX; ix++) {
      unsigned int sum = 0;
      for (int iiy = -1; iiy <= +1; iiy++)   
        for (int iix = -1; iix <= +1; iix++) {  // 3x3 Felder abarbeiten
        if ((iix == 0) && (iiy == 0)) continue; // das mittlere Feld auslassen
        if (world[(ix+iix+NX)%NX][(iy+iiy+NY)%NY]) sum++;  // zÀhlen
        // NB: '+NX' is nötig, da -1%NX leider -1 ergibt!
      }
      neigbors[ix][iy] = sum;
  }    

  for (int iy = 0; iy < NY; iy++)       // jetzt 'die Welt verÀndern'
    for (int ix = 0; ix < NX; ix++) {
    unsigned int n = neigbors[ix][iy]; 
    if (n == 3)                         // Hier könnte man auch 'switch' verwenden
      world[ix][iy] = true;
    else if (n<2 || n>3)
      world[ix][iy] = false;
  }
}

void T_life::iterate(int n)
{
  for (int i=0; i<n; i++) {
    std::cout << "Iteration " << i << ":\n";
    iterate();
    print();
  }
}

int main ()
{
  T_life game;
  game.set(1,1); game.set(2,1); game.set(3,1);  // Linie
  game.set(4,4); game.set(5,4); game.set(6,4); game.set(6,5); game.set(5,6); // 'Glider'
  game.print();
  game.iterate(5);
  return 0;
}

Übung 14: Labyrinth

Zur Aufgabe

Hier ist eine mögliche Lösung mit einer beliebigen Zahl von TĂŒren gezeigt. Dazu wurde eine neue Klasse 'door' eingefĂŒhrt. Zur Verwaltung der TĂŒren wird eine Liste aus der Standardbibliothek verwendet.

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

class room;                                   // 'VorwÀrts-Deklaration': Es wird nur bekannt gegeben, 
                                              // dass es ein room gibt, Details folgen spÀter.
                                              // (In door mĂŒssen wir room kennen, in room door...)
class door {
public:
  door (string n, room * p) {name = n; behind = p;};  // Konstruktor
                                              // Datenelemente:
  string name;                                // Name der TĂŒr
  room * behind;                              // Das Zimmer hinter der TĂŒr
};

class room {
public:
  room (string n, int i) {name = n; ErlaubteBesuche = i;};  // Konstruktor
  void PrintInfo(void);
  void AddDoor(string n, room * r);
  
  int ErlaubteBesuche;                        // ZĂ€hle Besuche in diesem Zimmer
  string name;                                // Name des Zimmers
  list<door> doors;                           // Eine Liste von TĂŒren
};

void room::PrintInfo(void) {                  // Gib Zimmername und TĂŒren aus
  cout << "Du bist im " << name << ". Es gibt folgende TĂŒren:";
  for (list<door>::iterator d=doors.begin(); d!=doors.end(); d++)
    cout << " " << d->name;
  cout << "." << endl;
}

void room::AddDoor(string n, room * r) {      // FĂŒge eine TĂŒr hinzu:
  door * newdoor = new door(n,r);             // Erschaffe die TĂŒr
  doors.push_back(*newdoor);                  // HĂ€nge sie an die Liste an
}

int main() 
{
  room * r1      = new room ("Foyer", 2);     // Erschaffe ein paar Zimmer...
  room * r2      = new room ("Treppenhaus", 5);
  room * r3      = new room ("Kuppelsaal", 5);
  room * ausgang = new room ("Ausgang", 5);
  
  r1->AddDoor("NordtĂŒr", r2);                 // ...und ein paar TĂŒren
  r2->AddDoor("OsttĂŒr" , r3);                 // Parameter sind je:
  r3->AddDoor("T1"     , r1);                 // - der Name der TĂŒr
  r3->AddDoor("T2"     , r2);                 // - das Zimmer dahinter
  r3->AddDoor("T3"     , r3);
  r3->AddDoor("T4"     , ausgang);
  r3->AddDoor("T5"     , r1);
  
  room * here = r1;                           // 'here' is das momentane  Zimmer
  do {
    here->PrintInfo();
    if (--(here->ErlaubteBesuche) == 0) {cout << "Zu viele Besuche! Du bist tot.\n"; break;};
    cout << "Noch " << here->ErlaubteBesuche << " Besuche in diesem Zimmer.";
    cout << " Wohin? (X:exit)" << endl;
    string in; cin >> in;
    if (in=="X") {cout << "TschĂŒss\n"; break;};
    for (list<door>::iterator adoor=here->doors.begin(); adoor != here->doors.end(); adoor++)
      if (in == adoor->name) {                // Eingabe == Name einer TĂŒr?
        here = adoor->behind;                 // Dann sind wir in einem neuen Zimmer...
        break;                                // Verlasse die for Schleife
      };
    if (here == ausgang) {cout << "GlĂŒckwunsch: Ausgang gefunden!\n"; break;};
  } while ( true );
}

Übung 15: Taschenrechner in der Kommandozeile

Zur Aufgabe.

Erste Version (festgelegte maximale Tiefe des Stapels):

#include <iostream>
#include <cstdlib>                // FĂŒr atof
using namespace std;

int main (int argc, char* argv[])
{
  const int MAX = 10;             // Maximale Tiefe des Stacks (unschön, sollte variabel sein!)
  float     stack[MAX];           // Lege Zahlen hier ab.
  int       n = 0;                // Anzahl Zahlen auf Stack. n zeigt auf nÀchstes LEERES Feld.
  
  for (int i=1; i<argc; i++) {    // Arbeite alle Argumente der Kommandozeile ab (außer argv[0])
    if (argv[i][0]=='+') {        // Ist der erste Buchstabe ein '+' ?
      if (n >= 2) {               // Wenn mindestens 2 Elemente auf dem Stack sind:
        n--;                      // - addiere die oberen beiden Elemente und
        stack[n-1] += stack[n];   // - reduziere Stackhöhe um eins.
      }
    } else if (argv[i][0]=='x') { // Dto. fĂŒr Multiplikation
      if (n >= 2) {
        n--;
        stack[n-1] *= stack[n];
      }
    } else {                      // Kein '+', kein 'x', also Zahl -> auf Stack damit
      if (n < MAX) stack[n++] = atof(argv[i]);   // beachte, dass nur MAX Elemente auf Stack passen!
    }
  }
  
  if (n>0)                        // Alle Eingaben abgearbeitet: gib oberste Zahl (=Ergebnis) aus
    cout << "Ergebnis: " << stack[n-1] << endl;
}

Zweite Version (mit dynamischem Stapel):

#include <iostream>
#include <cstdlib>                 // for atof
using namespace std;

struct StackElement {              // Jedes Element auf dem Stapel hat
  float          value;            // - einen Wert und
  StackElement * below;            // - einen Zeiger auf das DARUNTER liegende Element.
};

int main (int argc, char* argv[])  // Ein Taschenrechner mit UPN mit dynamischem Stapel
{
  StackElement * top = NULL;       // top zeigt auf das OBERSTE Element im Stapel
  StackElement * s;                // Ein Zeiger fĂŒr spĂ€ter...
                                   // Wir sorgen dafĂŒr, das alle ungĂŒltigen Zeiger NULL sind!
  for (int i=1; i<argc; i++) {
    bool add = argv[i][0] == '+';  // FĂŒhre AbkĂŒrzungen fĂŒr zwei Kommandos ein
    bool mul = argv[i][0] == 'x';
    if ( add || mul) {             // Wenn es ein Kommando ist:
      if ( top && top->below) {    // Haben wir schon zwei gĂŒltige Elemente ?
                                   // Achtung: wenn (top==NULL) wird die zweite Abfrage NICHT
                                   // mehr ausgefĂŒhrt (das dĂŒrften wir dann auch nicht!) 
        if (add) top->below->value += top->value;  // FĂŒhre den Befehl aus 
        if (mul) top->below->value *= top->value;
        s = top->below;            // Jetzt mĂŒssen wir top löschen. Wenn wir das sofort machen,
        delete top;                // geht unser Zeiger 'below' verloren.
        top = s;                   // Daher merken wir ihn uns kurz.
      }
    } else {                       // Kein Kommando, also (hoffentlich) eine Zahl:
      s = new StackElement;        // Wir brauchen ein neues StackElement
      s->value = atof(argv[i]);    // Weise den neuen Wert zu
      s->below = top;              // Verlinke das neuen Element
      top = s;                     // Top zeigt jetzt auf das neue Element
    }
  }
  if (top) cout << "Ergebnis: " << top->value << endl;
}

Dritte Version (mit Stapel aus der stl), hier auch mit 'wurzel' und 'sinus':

#include <iostream>
#include <cstdlib>      
#include <cstring>                    // fĂŒr strcmp()
#include <cmath>                      // FĂŒr sqrt() und sin()
#include <stack>                      // Hier haben wir einen Stapel in der stl
using namespace std;

int main (int argc, char* argv[])
{
  stack <float> s;                    // Wir brauchen einen Stapel von floats
                           
  for (int i=1; i<argc; i++) {
    bool add  = argv[i][0] == '+';    // Hier dekodieren wir die Kommandos
    bool mul  = argv[i][0] == 'x';
    bool wurz = !strcmp(argv[i],"wurzel");
    bool ssin = !strcmp(argv[i],"sinus");
                                      // Hier sollte man prĂŒfen, dass das eingegebene
                                      // Kommando erlaubt ist!
    if (wurz || ssin) {               // Ist es ein Kommando mit 1 Argument?
      if (wurz) s.top() = sqrt(s.top()); // Kommando ausfĂŒhren
      if (ssin) s.top() =  sin(s.top());
    } else if (add || mul) {          // Ist es ein Kommando mit 2 Argumenten?
      if ( s.size() >= 2    ) {
        float topvalue = s.top();     // Wir merken uns die obere Zahl,
        s.pop();                      // löschen den obersten Eintrag
        if (add) s.top() += topvalue; // und verÀndern das oberste Element
        if (mul) s.top() *= topvalue;
      }
    } else {                          // Eine Zahl legen wir auf den Stack
      s.push(atof(argv[i]));
    }
  }
  if (!s.empty()) cout << "Ergebnis: " << s.top() << endl;
}

Übung 16: Zahlenabhaken unter Benutzung einer Menge

Zur Aufgabe

#include <iostream>
#include <set>                        // Wir benutzen jetzt eine Menge

int main()
{
  const int N = 10;                   // GrĂ¶ĂŸe
  std::set<int> S;                    // Wir speichern int Werte ab
  
  for (int iy = 1; iy <= N; iy++) {
    for (int ix = 1; ix <= N; ix++) {
      std::cout.width(3);
      std::cout << ix * iy;           // Den Wert ausgeben
      S.insert(ix * iy);              // Das Produkt zur Menge hinzufĂŒgen
    }
    std::cout << std::endl;
  }
  std::cout << "Es gibt " << S.size() << " verschiedene Produkte." << std::endl;
  
  return 0;
}

Diskussion:

  • Die erste Lösung (mit einem array von bool) verschwendet viel Speicher, ist aber einfach und schnell.
  • Die zweite Lösung (32 Bits pro int) kommt mit minimalem Speicher aus, und ist nur wenig langsamer (beim Markieren der Werte sind ein paar Rechenschritte nötig). Sie benötigt aber den meisten Programmieraufwand.
  • Die Lösung mit der Menge ist extrem schnell und einfach implementiert. Leider ist das EinfĂŒgen der Elemente im set aufwĂ€ndig, da jedes Mal explizit geprĂŒft werden muss, ob das Element schon vorhanden ist. FĂŒr sehr große Probleme ist das also keine gute Lösung.
Personal tools