Cpp_20

Unter der sehr ironischen Überschrift ist zunächst die Suche nach so genannten „Happy Numbers”, also glücklichen Zahlen, zu verstehen. Damit sind, ausgehend von einer natürlichen Zahl als Startwert, solche Zahlen gemeint, für die eine bestimmte Iterationsvorschrift nach endlich vielen Iterationsschritten zum Wert 1 führt. Wenn wir dieses Thema näher betrachten, stellen wir fest, dass wir auch manchmal mit Zahlenfolgen konfrontiert sind, die Zyklen enthalten und damit endlos sind. Beim Umschiffen dieser Stolperfalle kommen Schildkröten und Hasen ins Spiel, aber dazu später noch mehr.

Schlussendlich überlegen wir uns, ob constepr auch ein gangbarer Weg sein könnte, um derartige Zahlen zu suchen, eben dann mit dem Übersetzer und nicht mit in Maschinencode gegossenen CPU-Anweisungen.

In dieser Fallstudie stellen wir mehrere Lösungsvarianten zur Berechnung glücklicher Zahlen vor. In einem Nebenschauplatz gehen wir auf Zyklen in verketteten Listen ein. Hashtabellen und die schon zitierten Hasen und Schildkröten helfen uns dabei, die Zyklen zu entdecken und damit das Traversieren von unendlichen Zahlenfolgen zu vermeiden.

Viele Objekte im täglichen „C++”–Alltag zeichnen sich dadurch aus, dass ihre Daten über die beiden Speicherbereiche Stack und Heap verteilt sind. Für das Kopieren derartiger Objekte bedeutet dies, dass es nicht genügt, die auf dem Stack liegenden Verwaltungsdaten „flach” zu kopieren. Auch die Daten auf dem Heap wollen kopiert werden, zumindest wenn man von einer echten („tiefen”) Kopie sprechen möchte.

Interessanter Weise kann man sich eine dritte Art des Kopierens vorstellen, einen Mittelweg zwischen flacher und tiefer Kopie: Wie wäre es, bei einer Kopieranforderung dem Benutzer von Objekt und Objektkopie (hinter den Kulissen) zunächst einmal datentechnisch dasselbe Objekt in die Finger zu geben. Solange keines dieser beiden Objekte verändert wird, besteht ja kein zwingender Handlungsbedarf, eine neue, unabhängige Kopie zu erstellen. Problematisch wird der „faule” Ansatz erst dann, wenn es an einem der beteiligten Objekte zu Änderungen kommt. Jetzt laufen Objekt und Objektkopie inhaltlich auseinander. Es wäre aber immer noch Zeit vorhanden, verspätet – aber eben nicht zu spät – eine echte Kopie des Objekts zu erzeugen, das soeben Änderungen erfährt.

Diesen Ansatz des Kopierens könnte man als „Lazy Copy” bezeichnen, nur hat sich dieser Begriff nicht so wirklich durchgesetzt. Wir sprechen hier meistens von der so genannten „Copy-On-Write”-Strategie. Sprich das Erstellen einer Kopie wird erst dann angegangen, wenn es zu schreibenden Zugriffen auf das Objekt kommt.

Wir betrachten eine „Copy-On-Write”-Realisierung für Zeichenketten in dieser Fallstudie. Neben einem Vergleich der Performanz zwischen der std::string-Klasse aus der STL und unserer selbstgeschriebenen CowString-Klasse kommt auch ein Anwendungsbeispiel zum Zuge.

Und wieder steht etwas Schulmathematik auf dem Programm, dieses Mal geht es um rechtwinklige Dreiecke. Für derartige Dreiecke gibt es den Satz des Pythagoras, er fällt eine Aussage zu den Seitenlängen solcher Dreiecke. Wir wollen im Folgenden nur Dreiecke betrachten, deren Seitenlängen ganzzahlig sind.

Schreiben Sie ein C++–Programm, das für folgende Fragestellung eine Antwort findet: Für welchen Umfang p mit p <= 2000 ist die Anzahl der verschiedenen rechwinkligen Dreiecke mit ganzzahligen Seitenlängen a, b und c am größten?

Hinweis: Die Aufgabenstellung stammt aus dem Repository „Project Euler”: Project Euler ist eine englischsprachige Website, sie enthält eine Reihe von Problemstellungen, die mit Hilfe von Mathematik und Programmierung gelöst werden können. Die Aufgabenstellung dieser Fallstudie finden Sie unter „Problem 39” vor.

Welche Parallelisierungsansätze sind für diese Aufgabenstellung denkbar? Implementieren Sie einen parallelen Algorithmus und vergleichen Sie die Laufzeiten der beiden Varianten. Mit Hilfe der Klassen std::thread, std::function, std::mutex und std::lock_guard gehen wir auf die Realisierung einer Funktion parallel_for ein.

Mit dem Kettenrechnen kehren wir zu den Ursprüngen unserer Grundschulzeit zurück. Für diejenigen unter Ihnen, die dieses Thema aus Ihrem Gedächtnis verdrängt haben: Jede Kettenrechnung beginnt mit einer normalen Rechenaufgabe (z.B. „1 + 3”). Das Resultat muss im Gedächtnis behalten werden, denn es folgt eine weitere Operation (z.B. „* 5”), welche jeweils zum vorhergehenden Resultat gerechnet wird. Das neue Zwischenresultat merkt man sich ebenfalls wieder für die nächste Operation usw. usw. So verlängert sich die „Rechenkette” immer weiter. Im Beispiel der Kettenrechnung 1 + 3 * 5 - 2 * 2 - 8 / 2 sollte man 14 als Endergebnis erhalten.

Entwickeln Sie eine Funktion calc, die eine Kettenrechnung als Parameter übergeben bekommt und ihr Resultat zurückliefert:

int calc (const std::string& chain);

Offensichtlich führen viele Wege zum Ziel einer ansprechenden Realisierung. Im Lösungsteil finden Sie Lösungsansätze vor, die generische Funktionen, heterogene STL-Container, reguläre Ausdrücke und vieles mehr anwenden.

Beginnend mit C++ 11 haben eine Reihe von neuen Sprachfeatures Einzug in die Programmiersprache C++ gefunden, die wir in ihrer Gesamtheit unter dem Begriff C++ 20 subsumieren können:

• Lambda-Funktionen
• Generische Funktionen
• Folding
• Variadische Templates
• Parameter Packs
• Rekursive Parameter Pack Expansion
• IIFE

Sicherlich muss man all diese Konzepte erst einmal alleinstehend für sich betrachten und studieren, um sie zu erfassen und zu verstehen. Dies setze ich für das Studium dieser Fallstudie voraus. Mir kommt es darauf an, all diese Techniken miteinander zu verknüpfen! Genau dies wollen wir an Hand einer Reihe von Beispielen in dieser Fallstudie näher betrachten.

Im Jahr 1857 hat der Amerikaner Samuel Morse das Morsealphabet erfunden. Damals war es noch nicht möglich, gesprochenen Text über Telegrafenleitungen zu übermitteln. Also verwendete Samuel Morse für jeden Buchstaben kurze und lange Piepstöne (Punkte und Striche). Diese Punkte und Striche kann man aber auch als Lichtblitze, Pfeiftöne etc. weitergeben. So ist es möglich, ganze Worte mit anderen über große Distanzen zu „sprechen”.

Schreiben Sie zwei Funktionen encode und decode, die eine lesbare Nachricht in Morseschrift verschlüsseln bzw. entschlüsseln.

Das Haus des Nikolaus ist ein altes Zeichenspiel und vermutlich jedem Leser unter Ihnen bekannt, der Kinder sein eigen nennen darf. Ziel des Spiels ist es, ein Haus (wie in Abbildung 1 dargestellt) „ohne Absetzen des Stiftes„ zu zeichnen, also in einem Zug mit acht Strecken. Sie werden die Beobachtung machen, dass dies nicht immer zum Ziel führt, da man öfters in die Situation gelangt, eine Strecke mehrmals zeichnen zu müssen, was nicht erlaubt ist. Kinder erfreuen sich an diesem Spiel zusätzlich daran, ihre Eltern lautstark am Spielen zu beteiligen, indem sie an jeder Ecke, die sie erreichen, ein Wort des Satzes „Das ist das Haus vom Ni–ko–laus” aussprechen – zu jeder Strecke gehört ein Wort bzw. eine Silbe. Wie viele verschiedene Möglichkeiten gibt es, das Haus zu zeichnen?

Abbildung 1: Das Haus des Nikolaus – als Spiel betrachtet.

Entwerfen Sie geeignet ein oder mehrere C++–Klassen, um alle Lösungen des „Haus des Nikolaus”-Problems zu ermitteln. Im Lösungsvorschlag finden Sie zwei Realisierungsansätze vor:

• eine klassische Realisierung (keine „Modern C++” Kenntnisse erforderlich)
• eine C++20 Realisierung mit „Ranges”

Schreiben Sie ein Programm, das alle Lösungen in ansprechender Form auf der Konsole ausgibt.

Die Suche nach Primzahlen – also Zahlen, die nur durch sich selbst und durch 1 teilbar sind – war lange Zeit eine der zentralsten Bestandteile der Zahlentheorie. Primzahlenjäger können neben den zahlreichen Erkenntnissen der Zahlentheoretiker heutzutage auf eine zusätzliche Hilfestellung zurückgreifen, den Computer. Wir wollen im Folgenden ein Programm entwickeln, das mit Hilfe mehrerer Threads zu zwei fest gegebenen natürlichen Zahlen n und m die Anzahl aller Primzahlen p mit n ≤ p ≤ m bestimmt.

Für die Koordination der Threads setzen wir „Hindernisse” ein, also C++–20 std::latch-Objekte. Studieren Sie in dieser Anwendung, wie die Primzahlensuche mit mehreren Threads auf diese Weise koordinierbar ist.

In dieser Fallstudie betrachten wir ein sehr „martialisches” Problem, das durch den jüdischen Historiker Flavius Josephus überliefert worden ist. Dieser soll im römisch–jüdischen Krieg mit 41 Kameraden den Selbstmord der Gefangenschaft vorgezogen haben. Details finden Sie gleich weiter unten vor – umso interessanter die Fragestellung, wie Informatiker bei dieser Fallstudie ins Spiel kommen: Josephus fand nämlich heraus, an welche Position im Kreis er sich stellen musste, um als letzter übrig zu bleiben, also um überleben zu können.

Damit sind schlagartig vielen Türen der Informatik geöffnet, zum Beispiel einfach-verkettete Listen, Arrays und sogar das Prinzip der Vererbung, um nur einige wenige anzusprechen. Lassen Sie sich überraschen, wie wir mit den Hilfsmitteln des Modern C++ die Lösung des Josephus-Problems bestimmen.

Das Collatz-Problem, auch als „3n + 1”-Vermutung bezeichnet, ist ein ungelöstes mathematisches Problem und wird dem Mathematiker Lothar Collatz zugeschrieben.

Diese Fallstudie zeigt, wie sich die Berechnung der Elemente einer Zahlenfolge in einen C++–Iterator einbetten lässt, um auf diese Weise mit Hilfe der STL performante und elegant in das C++–Programmiermodell integrierte Algorithmen formulieren zu können.