Aufgaben zur UE
Einführung in die Programmierung

Legen Sie alle Programme so aus, dass der Benutzer die geforderten Berechnungen beliebig oft durchführen kann, ohne das Programm jedes mal neu zu starten.

Anspruchsvollere Aufgaben sind mit einem Stern gekennzeichnet.

  1. Geltungsbereich und Funktionen
  2. Erstellen Sie C++ Programme für folgende Problemstellungen (für Funktionen ist natürlich ein geeigneter Testrahmen im Hauptprogramm vorzusehen):

    1. Schreiben Sie eine Funktion int Binomial(int n, int k), die den Binomialkoeffizienten nach der Formel

      berechnet. Verwenden Sie zur Berechnung der Fakultät, die aus der Vorlesung bekannte Funktion.
    2. Die Folge Fn ist definiert durch die Rekursion
      Fn=2*Fn-1+Fn-2*Fn-3
      mit den Startwerten F0=1, F1=1 und F2=1
      Schreiben Sie eine Funktion, die den Wert Fn an einer beliebigen Position n berechnet.
    3. Schreiben Sie eine Funktion int ggt(int a, int b), die den größten gemeinsamen Teiler der beiden natürlichen Zahlen a und b berechnet. Verwenden Sie dazu keine Schleifen!
    4. Schreiben Sie die Funktionen int mult(int m, int n) und int power(int m, unsigned int n), die das Produkt m*n bzw. die Exponentialfunktion mn der Zahlen m und n berechnen. Verwenden Sie dazu weder Schleifen, noch den Operator * (Multiplikation). Auch das Verwenden irgendwelcher externer Routinen (z.B. Mathematikbibliotheken) ist nicht erlaubt! Beachten Sie, dass int-Werte auch negativ oder gleich 0 sein können. Hinweis: m*n = m+m*(n-1) für n>0 bzw. mn=m*mn-1
    5. Die Funktionen f(n), g(n) und h(n) sind für natürliche Zahlen n wie folgt definiert:
      f(0) = 0
      g(0) = 0
      h(0) = 1
      f(n) = h(n)+g(n-1)
      g(n) = 2*f(n)
      h(n) = n*h(n-1)
      Schreiben Sie ein Programm, das die Berechnung der Funktion f für ein beliebiges n erlaubt.
    6. Schreiben Sie eine Funktion void stack(), durch deren Aufruf der Stack zum Überlaufen gebracht wird. (Anmerkung: Dieser Überlauf, der normalerweise als „stack overflow“ bezeichnet wird, wird auf den Übungsrechnern durch den Abbruch des Programms und die Ausgabe der Fehlermeldung "Segmentation fault" angezeigt.) Wie oft muss die Funktion stack() aufgerufen werden, bis es zum stack overflow kommt? Wie können Sie das beschleunigen und wie können Sie aus Ihren Ergebnissen die Größe des Stack abschätzen?
    7. Schreiben Sie eine Funktion bool intTest(int n, char c), die prüft, ob die Ziffer c in der Zahl n vorkommt. Verwenden Sie in der Funktionsdefinition keine Schleifen.
    8. Schreiben Sie zwei Funktionen, die jeweils die Länge eines Strings, der als Parameter übergeben wird, bestimmen. Dabei soll die eine Funktion eine Schleife verwenden, die andere nicht. Verwenden Sie für diese Aufgabe keine Routinen aus externen Bibliotheken (z.B. strlen).
    9. Schreiben Sie eine Funktion, die einen String, der als globale Variable vereinbart und im Hauptprogramm eingelesen wird, in umgekehrter Reihenfolge wieder ausgibt. Verwenden Sie weder eine Schleife, noch Routinen aus externen Bibliotheken (z.B. strlen).
    10. Schreiben Sie eine Funktion, die aus einem integer-Feld, das als globale Variable vereinbart und im Hauptprogramm eingelesen wird, das Maximum ermittelt und retourniert. Die Funktion soll außerdem die Summe aller Werte am Bildschirm ausgeben. Verwenden Sie in der Funktion weder eine Schleife, noch Routinen aus externen Bibliotheken (z.B. strlen).
    11. Schreiben Sie eine Funktion, die einen String, der als globale Variable vereinbart und im Hauptprogramm eingelesen wird, vermixt wieder ausgibt. Dabei sollen zunächst alle Zeichen mit ungeradem Index in der ursprünglichen Reihenfolge ausgegeben werden und daran anschließend alle Zeichen mit geradem Index in umgekehrter Reihenfolge. Verwenden Sie weder eine Schleife, noch Routinen aus externen Bibliotheken (z.B. strlen). Beispiel:
      Eingabe: abcdefghi
      Ausgabe: bdfhigeca
    12. * Schreiben Sie ein Programm, das beliebig viele Zahlen (maximal 50) einliest und fallend sortiert wieder ausgibt. Verwenden Sie zum Sortieren folgenden rekursiven Algorithmus: Zunächst wird das Maximum gesucht und an die erste Stelle der Liste gesetzt. Dann wird dieser Vorgang mit der restlichen (um ein Element kürzeren) Liste wiederholt, so lange bis die Länge der Liste 1 ist.
      Bemerkung: Die Programmierung kann recht einfach erfolgen, wenn für die Liste ein globales Feld verwendet wird.
    13. * Schreiben Sie ein Programm, das eine Zahl einliest und alle möglichen Permutationen der in der Zahl vorkommenden Ziffern ausgibt. (Sie können davon ausgehen, dass jede Ziffer nur einmal eingegeben wird.)
      z.B. Eingabe: 123
      Ausgabe: 123 132 213 231 312 321
    14. * Schreiben Sie ein Programm, das eine natürliche Zahl n einliest und die expandierte Form des Ausdrucks (a+b)n ausgibt. Also z.B.:
      Eingabe: 3    Ausgabe: a^3+3a^2b+3ab^2+b^3
    15. * Wie Beispiel 13, nur für Zeichenketten.
      z.B. Eingabe: abc
      Ausgabe: abc acb bac bca cab cba