Aufgaben

Aufgaben zur Vorlesung

Aufgabe 1:

Übersetzen Sie die Programme aus diesem Abschnitt und lassen Sie sie laufen.

Aufgabe 2:

Schreiben Sie die rekursive Funktion der Fakultät. Hierzu brauchen Sie den if-Befehl, wie Sie ihn aus Java kennen. Testen Sie die Funktion mit ein paar Werten.

Aufgabe 3:

Schreiben Sie jetzt eine Version der Fakultätsfunktion, in der ein Zeiger auf die Variable, in der das Ergebnis akkumuliert wird, als zweites Argument übergeben wird:

void fak(int x,int* result);

Schreiben Sie Testfälle für diese Funktion.

Aufgabe 4:

(2 Punkte) Schreiben Sie eine Funktion, die mit einer Intervallschachtellung für eine stetige Funktion eine Nullstelle approximiert.

float nullstelle(float (*f) (float),float mi,float ma);

Testen Sie Ihre Implementierung mit folgendem Programm:

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

float f1(float x){return 2*x*x*x+5;}
float f2(float x){return 2*x +1 + x*x*x/4 ;}
float f3(float x){return 10*x+5;}
float f4(float x){return 0;}
float f5(float x){return x*x;}

void teste(float (*f)(float)){
  const float fn = nullstelle(f,-10,11);
  std::cout << "n = "<<fn<< ", f(n) = " << f(fn) << std::endl;
}

int main(){
  teste(f1);
  teste(f2);
  teste(f3);
  teste(f4);
  teste(f5);
}

Aufgabe 5:

Implementieren sie die Funktion compose entsprechend folgender Header-Datei:

typedef int (* intfunction)(int);

int compose(intfunction fs [],int length,int x);

Sie soll eine Komposition aller Funktionen in der Reihung fs auf den Wert x anwenden. Es soll dabei gelten:

compose({f₁,... f_n},n,x) = f_n(f_n-1(...(f₁(x))...))

Testen Sie Ihre Lösung mit folgender Testdatei:

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

int f1(int x){return x*x;}
int f2(int x){return x;}
int f3(int x){return x+2;}
int f4(int x){return x*4;}
int f5(int x){return -x*x*x;}

int main(){
    intfunction fs [] = {f1,f2,f3,f4,f5};
    std::cout << compose(fs,5,2)<<std::endl;
}

Aufgabe 6:

Sie sollen in dieser Aufgabe die Sortiermethode des Bubble-Sort, wie sie im ersten Semester vorgestellt wurde, für Reihungen von ganzen Zahlen umsetzen:

a) Implementieren Sie eine Funktion
void bubbleSort(int xs [],int length ),
die Elemente mit dem Bubblesort-Algorithmus der Größe nach sortiert. Schreiben Sie ein paar Tests für Ihre Funktion.

b) Schreiben Sie jetzt eine verallgemeinerte Sortierfunktion, in der die Sortierrelation als Parameter mitgegeben wird. Die Sortierfunktion soll also eine Funktion höherer Ordnung mit folgender Signatur sein:
void bubbleSortBy(int xs [],int length, bool (*smaller) (int,int) )

Aufgabe 7:

(2 Punkte) Schreiben Sie eine Funktion fold mit folgender Signatur:
int fold(int xs [],int length,int (*foldOp)(int,int),int startV)

Die Spezifikation der Funktion sei durch folgende Gleichung gegeben:

fold(xs,l,op,st) = op(... op(op(op(st,xs[0]),xs[1]),xs[2])...,xs[l-1])

Oder bei Infixschreibweise der Funktion op gleichbedeutend über folgende Gleichung:

fold({x₀,x₁,,...,x_l-1},l,op,st) = st op x₀ op x₁ op x₂ op ... op x_l-1

Testen Sie Ihre Methode fold mit folgenden Programm:

#include <iostream>

int add(int x,int y){return x+y;}
int mult(int x,int y){return x*y;}

int fold(int xs [],int length,int (*foldOp)(int,int),int startV);

int main(){
  int xs [] = {1,2,3,4,5};
  std::cout << fold(xs,5,add,0)<< std::endl;
  std::cout << fold(xs,5,mult,1)<< std::endl;
}

Aufgabe 8:

Implementieren Sie für unsere in C++ implementierten Listenstruktur die folgenden Funktionen (nach der Spezifikation aus dem ersten Semester):

a) int last(struct IntList * dieses)

b) struct IntList * concat(struct IntList * xs,struct IntList * ys)

c) int elementAt(struct IntList * dieses,int i)

d) int fold(struct IntList * dieses,int start,int(*foldOp)(int,int))

Aufgabe 9:

Schreiben Sie eine Funktion zur Funktionakomposition mit folgender Signatur:

template <typename a, typename b, typename c>
c composition(c (* f2)(b),b (* f1)(a),a x);

Sie sei spezifiziert durch die Gelichung: composition(f₂,f₁,x)=f₂(f₁(x)). Testen Sie Ihre Implementierung für verschiedene Typen.

Aufgabe 10:

Schreiben Sie jetzt eine generische Fuktion fold auf Reihungen und testen Sie diese auf verschiedenen Typen aus.

Aufgabe 11:

Verallgemeinern Sie jetzt Ihre Funktion bubbleSortBy zu einer generischen Funktion, mit der sie Reihungen beliebiger Typen sortieren können.

Aufgabe 12:

(3 Punkte) Ergänzen Sie die obige Listenklasse um weitere Listenoperatoren.

const std::string operator[](const int i) const; soll das i-te Element zurückgeben.
const StringLi* operator-(const int i) const; soll eine neue Liste erzeugen, indem von der Liste die ersten i Elemente weggelassen werden.
const bool operator<(const StringLi* other) const; soll die beiden Listen bezüglich ihrer Länge vergleichen.
const bool operator==(const StringLi* other) const; soll die Gleichheit auf Listen implementieren.

Testen Sie ihre Implementierung an einigen Beispielen.

Aufgabe 13:

(Alternative zur letzten Punkteaufgabe 3 Punkte) In dieser Aufgabe ist eine Klassen für HashMengen zu schreiben:

a) Schreiben Sie eine Klasse, die eine Hashmenge realisiert. Ihre Klasse soll der folgenden Kopfdatei entsprechend Funktionalität bereitstellen

#include "Li.h"

template <class elementType>
class HashSet {
  protected:
    int capacity;
    int (*hashFunction)(elementType);
    Li<elementType>* hashArray [];
  
  public:
    HashSet(int c, int (*hashF)(elementType));
    virtual ~HashSet();
    void add(elementType el);

    bool contains(elementType el);    
    std::string toString();
};

b) Schreiben Sie Testfälle und betrachten Sie, wie gut in diesen Tests die Elemente gestreut liegen.

Aufgabe 14:

Schreiben Sie jetzt analog zu Ihrer Lösung aus der letzten Aufgabe, eine generische Klasse HashMap, die eine endliche Abbildung von Schlüsseln auf Werte realisiert. Benutzen Sie hierzu auch die bereits geschrieben Klasse Pair, um die Schlüssel-Wert-Paare in Listen zu speichern.

Aufgabe 15:

Schreiben Sie weitere Funktionen, die Objekte der Klasse LazyList erzeugen und testen Sie diese:

a) Schreiben Sie eine generische Funktion:

template <typename A>
LazyList<A>* repeat(A x)

die eine Liste erzeugt, in der unendlich oft Wert x wiederholt wird.

b) Schreiben Sie eine Funktion, die eine unendliche Liste von Pseudozufallszahlen erzeugt. Benutzen sie hierzu folgende Formel:
z_n+1 = (91 * z_n + 1) mod 347

Aufgabe 16:

(2 Punkte) Sie haben bereits zweimal eine Funktion fold implementiert. Einmal auf Reihungen und einmal auf unseren selbstgeschriebenen einfach verketteten Listen. Jetzt sollen Sie die Funktion noch einmal allgemeiner schreiben.

a) Implementieren Sie jetzt die Funktion fold zur Benutzung für allgemeine Behälterklassen im STL Stil entsprechend der Signatur:

template <typename Iterator,typename BinFun,typename EType>
EType fold(Iterator begin,Iterator end,BinFun f,EType start);

b) Testen Sie Ihre Implementierung mit folgendem Programm:

#include <vector>
#include <string>
#include <functional>
#include <iostream>
#include "STLFold.h"

int addLength(int x,std::string s){return x+s.length();}

std::string addWithSpace(std::string x,std::string y){
    return x+" "+y;
}

int main(){
  int xs []={1,2,3,4,5};
  int result;
  result = fold(xs,xs+5,std::plus<int>(),0);
  std::cout << result << std::endl;
  result = fold(xs,xs+5,std::multiplies<int>(),1);
  std::cout << result << std::endl;

  std::vector<std::string> ys;
  ys.insert(ys.end(),std::string("friends"));
  ys.insert(ys.end(),std::string("romans"));
  ys.insert(ys.end(),"contrymen");
  result = fold(ys.begin(),ys.end(),addLength,0);
  std::cout << result << std::endl;

  std::string erg
    = fold(ys.begin(),ys.end()
          ,std::plus<std::string>(),std::string(""));
  std::cout << erg << std::endl;

  erg=fold(ys.begin(),ys.end(),addWithSpace,std::string(""));
  std::cout << erg << std::endl;
}

c) Schreiben Sie weitere eigene Tests.

Aufgabe 17:

(1 Punkt) Schreiben Sie eine OpenGL-Funktion
void circle(int radius),
mit der Sie einen Kreis zeichnen können. Benutzen Sie hierzu die Figur GL_POLYGON.