# Aufgaben zur UE
Einführung in die Programmierung

Anspruchsvollere Aufgaben sind mit einem Stern gekennzeichnet.

##
6. Aufzähltyp, logischer Datentyp, spezielle Operatoren; Exkurs: Sortierverfahren

Erstellen Sie C++ Programme für folgende Problemstellungen:

1. 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.

2. 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 (/,/=).

3. 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 (/,/=)

4. 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!

5. 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.

6. 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.

7. 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.

8. 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

9. 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.

10. 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:
    1. alle Lampen ausschalten
    2. alle Lampen einschalten
    3. mehrere Lampen ein/auszuschalten ohne den Zustand der anderen Lampen zu verändern
    4. den Zustand aller Lampen umzukehren (alle Lampen, die vorher aus sind, werden eingeschaltet und umgekehrt)
    5. den Zustand von mehreren vom Benutzer vorgegebenen Lampen umzukehren
    6. 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.

11. Schreiben Sie eine Funktion sort(char string[]), das die Zeichen in der als Parameter übergebenen Zeichenkette sortiert.

12. * 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.

13. * 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.

14. * 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.
    1. Was bedeutet das für das Programm?
    2. Wie kann man das beheben?
    3. Warum ist die Sortierreihenfolge am Ende trotzdem korrekt?

15. * 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