Aufgaben zur UE
Einführung in die Programmierung
Anspruchsvollere Aufgaben sind mit einem Stern gekennzeichnet.
-
Aufzähltyp, logischer Datentyp, spezielle Operatoren; Exkurs: Sortierverfahren
Erstellen Sie C++ Programme für folgende Problemstellungen:
-
Schreiben Sie eine Funktion, welche die Fakultät einer gegebenen Zahl n berechnet, ohne dass Sie eine
if-Anweisung, eine
switch-Anweisung oder eine Schleife verwenden.
-
Palindrome sind Worte (oder auch Sätze), die von links nach rechts gelesen das gleiche ergeben, wie von rechts nach links gelesen. Ein bekanntes Beispiel
ist der Name „Otto“. Das kann man auch auf Zahlen anwenden: So ist zum Beispiel 121 ein Palindrom, während 123 keines ist. Für Zahlen ist die Eigenschaft
„Palindrom“ natürlich abhängig von der gewählten Darstellung. So ist etwa die Zahl 15 in Binärdarstellung (1111) ein Palindrom, nicht aber in der
Dezimaldarstellung. Schreiben Sie zwei Funktionen bool pal10(unsigned) und
bool pal2(unsigned), die feststellen, ob der Eingangsparameter ein Palindrom im Dezimalsystem
(pal10) bzw. im Binärsystem (pal2) ist. Verwenden Sie in der Funktion pal2 weder Multiplikation (*,*=), noch Division (/,/=).
-
Schreiben Sie eine Funktion int count(int n), die die Anzahl der Einsen in der Binärdarstellung
der Zahl n retourniert. Verwenden Sie in der Funktion count weder Multiplikation (*,*=), noch Division (/,/=)
-
Schreiben Sie eine Funktion int add(unsigned i, unsigned j), die die Summe der beiden Parameter
i und j retourniert. Die Operatoren + - += und
-= dürfen in der Funktion nicht verwendet werden!
-
Verwenden Sie den Datentyp karten aus der Vorlesung und realisieren Sie folgende Funktionen:
karten read()
Liest eine ganze Zahl ein und liefert den entsprechenden Kartenwert zurück. Im Fehlerfall (der Benutzer gibt eine Zahl ein, die keinem
Kartenwert enspricht) wird einfach der Wert as retourniert.
void write(karten card)
Gibt die jeweilige Karte als Text aus. Also z.B. "Zehn" bzw. "Bube".
void sort(karten card1, karten card2, karten card3)
Gibt die Eingangsparameter card1, card2 und card3 aufsteigend nach ihrem Wert geordnet aus.
-
Schreiben Sie eine rekursive Funktion, die keine Schleife, keine if-Anweisung, keine
switch-Anweisung und auch keine bedingte Auswertung
(? :) enthält, die aber trotzdem terminiert.
-
Entwickeln Sie 2 Funktionen zum Sortieren eines Integer Feldes mit Hilfe eines „stabilen“ und eines „nicht-stabilen“ Bubblesort Verfahrens:
Das Feld wird wiederholt durchlaufen. Wenn dabei 2 benachbarte Elemente aus der Ordnung sind (größeres vor kleinerem), vertausche sie. Dadurch wird beim
ersten Durchlauf das größte Element an die letzte Stelle gesetzt, beim 2. Durchlauf das zweitgrößte an die vorletzte Stelle, usw. Die Elemente steigen wie
Blasen (bubbles) auf.
Ein Sortierverfahren heißt stabil, Wenn Datensätze, die denselben Schlüsselwert haben, ihre ursprüngliche Reihenfolge nach dem Sortieren beibehalten.
Beispiel: Sortieren der folgenden Daten nach Familiennamen
Franz Müller, Hermann Maier, Lieschen Müller
Ein stabiles Sortierverfahren muss folgende Reihenfolge liefern:
Hermann Maier, Franz Müller, Lieschen Müller
Ein nicht-stabiles Sortierverfahren könnte auch folgende Reihenfolge liefern:
Hermann Maier, Lieschen Müller, Franz Müller
Achtung: Ein nicht-stabiles Sortierverfahren muss die Reichenfolge nicht zwangsläufig verändern. Es muss nur die Möglichkeit bestehen, dass unter bestimmten
Voraussetzungen die ursprüngliche Reihenfolge nicht beibehalten wird.
-
Entwickeln Sie eine Funktion zum Sortieren eines Integer Feldes mit Hilfe des Mergesort Algorithmus:
Das zu sortierende Feld wird rekursiv in Teilfelder halber Länge geteilt, bis die (trivialen, skalaren) Felder aus einem einzigen Element bestehen.
Danach werden jeweils 2 Teilfelder zu einem doppelt so großen Feld gemergt (sortiert).
Beim Mergen werden sukzessive die ersten beiden Elemente der Felder verglichen und das kleinere in das neue Feld übertragen, bis alle Elemente im neuen
Feld sortiert gespeichert sind. Das Mergen wird solange wiederholt, bis in der letzten Phase 2 Felder der Länge n/2 zu einem sortierten Feld der Länge
n verschmelzen
-
Schreiben Sie eine Funktion double median(double feld[], int size), die den Median der in
feld übergebenen Werte bestimmt. Der Parameter
size gibt die Anzahl der Werte im Array an. Beachten Sie, dass zur Bestimmung des Medians
die Werte sortiert werden müssen.
-
Schreiben Sie ein Programm, das zur Ansteuerung von Lampen in einer Bühnenbeleuchtung dienen soll. Insgesamt können 32 Lampen angesteuert werden, indem
Bits in einer globalen Integer Variable status gesetzt werden. Eine eins bedeutet dabei, dass
die zugehörige Lampe eingeschaltet ist, eine 0 heißt, die Lampe ist ausgeschaltet. Schreiben Sie Funktionen um folgende Aktionen zu ermöglichen:
-
alle Lampen ausschalten
-
alle Lampen einschalten
-
mehrere Lampen ein/auszuschalten ohne den Zustand der anderen Lampen zu verändern
-
den Zustand aller Lampen umzukehren (alle Lampen, die vorher aus sind, werden eingeschaltet und umgekehrt)
-
den Zustand von mehreren vom Benutzer vorgegebenen Lampen umzukehren
-
die Lampen um eine vom Benutzer vorgegebene Anzahl 'weiterwandern' zu lassen. Das heißt, falls eine Lampe ein/ausgeschaltet ist, so wird die
nächste/übernächste/usw. (abhängig von der Anzahl) Lampe ein/ausgeschaltet. Die Lampen sind dabei zyklisch angeordnet zu denken, so dass die nächste
Lampe nach der letzten wieder die erste ist.
-
Schreiben Sie eine Funktion sort(char string[]), das die Zeichen in der als Parameter
übergebenen Zeichenkette sortiert.
- *
Wie Beispiel 4, allerdings soll die Funktion int add(int i, int j)auch negative Parameter
korrekt verarbeiten und die Verwendung von if-Anweisungen ist nicht erlaubt.
- *
Um die Inhalte zweier Variablen zu vertauschen verwendet man normalerweise eine Sequenz folgender Form:
temp=x;
y=x;
x=temp;
Schreiben Sie ein Programm, das die Inhalte zweier Variablen vertauscht, ohne eine Hilfsvariable zu verwenden (also verwenden Sie nur genau zwei Variablen
in Ihrem Programm). Es dürfen auch keine Subtraktionen (-, -=) verwendet werden.
- *
Implementieren Sie den Quicksortalgorithmus wie im Skriptum beschrieben. Fügen Sie vor der Zeile
if (i>=j) break;
folgende Ausgabeanweisung ein:
cout<<j<<endl;
Sortieren Sie dann eine Zahlenfolge, deren letzter Eintrag -2147483648 (-MAXINT) ist. In der Ausgabe können Sie erkennen, dass die Variable j offenbar
auch negative Werte annehmen kann.
-
Was bedeutet das für das Programm?
-
Wie kann man das beheben?
-
Warum ist die Sortierreihenfolge am Ende trotzdem korrekt?
- *
Schreiben Sie eine Funktion sort(char string[]), das die Zeichen in der als Parameter
übergebenen Zeichenkette sortiert. Dabei sollen im Ergebnis aber zuerst alle Vokale und dann erst die Konsonanten vorkommen. Sie sollen auf keinen Fall
mehrmals sortieren (also zum Beispiel zuerst alle Vokale heraussuchen, diese dann sortieren, dann die verbliebenen Konsonanten sortieren und die beiden
Ergebnise zusammenhängen). Beispiel:
Eingabe: keineahnung
Ausgabe: aeeiughknnn