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.
-
Geltungsbereich und Funktionen
Erstellen Sie C++ Programme für folgende Problemstellungen (für
Funktionen ist natürlich ein geeigneter Testrahmen im Hauptprogramm
vorzusehen):
-
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.
-
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.
-
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!
-
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
-
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.
-
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?
-
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.
-
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).
-
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).
- 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).
-
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
- *
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.
- *
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
- *
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
- *
Wie Beispiel 13, nur für Zeichenketten.
z.B. Eingabe: abc
Ausgabe: abc acb bac bca cab cba