Allgemeine Informatik II SoSe 2001
Prof. Dr. H. Neumann $\bullet$ Dr. K. Murmann $\bullet$ S. Geschwentner $\bullet$ Dr. F. Schwenker

4. Aufgabenblatt (bis zum 14.06.2001)

8. Aufgabe:
In der 3. Aufgabe (Blatt 2) haben Sie Prozeduren zur Verwaltung von Studentennamen implementiert. Implementieren Sie nun rekursive Prozeduren:

1. PROCEDURE reverse(liste : listPtr);

   Die Prozedur reverse gibt die in der Liste liste gespeicherten Namen in der Reihenfolge ihrer Eingabe aus, d.h. die Liste soll vom Ende her ausgedruckt werden.

2. PROCEDURE anzahl(liste : listPtr) : CARDINAL;

   Die Funktionsprozedur anzahl liefert die Anzahl der eingetragenen Namen in der Liste liste zurück.

9. Aufgabe:
Für $n,k\in {\rm I\! N}$ ist der Binomialkoeffizient ${n \choose k}$ definiert durch

$${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$$

ferner gilt ${n \choose n}={n \choose 0}=1$ für alle $n$, sowie ${n \choose k}=0$ falls $n<k$.

Implementieren Sie eine rekursive Funktionsprozedur

PROCEDURE bino(n,k : CARDINAL) : CARDINAL;

zur Berechnung von Binomialkoeffizienten. Wie oft wird bino zur Berechnung von ${8 \choose 4}$ aufgerufen.

10. Aufgabe:
Auf einer Rolle mit $n$ Metern Schnur ( $n\in {\rm I\! N}$) wird fortlaufend entweder 1 oder 2 Meter abgeschnitten bis die Schnur verbraucht ist.

Schreiben Sie eine rekursive Prozedur

PROCEDURE schnittfolgen(n : CARDINAL) : CARDINAL;

die für die Länge $n$ die Anzahl aller möglichen Schnittfolgen bestimmt.

Beispiel: Für $n=4$ sind die folgenden fünf Schnittfolgen möglich

1. 1m, 1m, 1m, 1m
2. 1m, 1m, 2m
3. 1m, 2m, 1m
4. 2m, 1m, 1m
5. 2m, 2m

Schöne Pfingsten!