Cpp_11

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.

Das Beispiel der dinierenden Philosophen ist eines der populärsten Standardprobleme aus dem Bereich der Parallelprogrammierung. Es erlaubt, die Kooperation der beteiligten Threads in einer lebendigen Simulation darzustellen.

Wir stellen eine Standard-Lösung für dieses Problem vor und gehen dabei vor allem auf die Klasse std::mutex und das RAII-Idiom näher ein. Basiswerkzeuge zur nebenläufigen Programmierung in C++ wie std::async, std::future oder auch std::scoped_lock werden eingesetzt.

Ist eine Menge von n Elementen gegeben, so bezeichnet man die möglichen Anordnungen aller dieser n Elemente als Permutationen (lat. permutare: vertauschen). Die Berechnung der Permutationen einer beliebigen Menge von Elementen steht im Mittelpunkt dieser Fallstudie. Als Elemente verwenden wir zunächst Zeichen, also char-Variablen. Dies soll aber verallgemeinerbar sein, also auch für Variablen eines beliebigen Datentyps funktionieren.

Für zwei Zeichen A und B gibt es nur die zwei Permutationen AB und BA. Drei Zeichen, angenommen A, B und C, können hingegen in sechs verschiedenen Permutationen dargestellt werden: ABC, ACB, BAC, BCA, CAB und CBA. Sind alle n Elemente voneinander verschieden, was wir in dieser Aufgabe zu Grunde legen, so gibt es dafür n! Anordnungen (n-Fakultät).

Die Fakultät ist in der Mathematik eine Funktion, die einer natürlichen Zahl n das Produkt aller natürlichen Zahlen kleiner und gleich dieser Zahl zuordnet: n! = 1 * 2 * 3 * … * n. In der Kombinatorik spielt die Fakultät ebenfalls eine große Rolle, weil n! die Anzahl der Möglichkeiten ist, unterschiedliche Gegenstände der Reihe nach anzuordnen. Bei diesen Überlegungen kommen auch Binomialkoeffizienten ins Spiel. Sie geben an, auf wie viele verschiedene Arten man k Objekte aus einer Menge von n verschiedenen Objekten auswählen kann.

Sowohl Fakultäten als auch Binomialkoeffizienten weisen eine unangenehme Eigenschaft auf: Ihre Werte können sehr schnell sehr groß werden – und sind damit in Variablen des Typs long oder size_t nicht mehr darstellbar. Ein Satz von Legendre verschafft hier Abhilfe: Er befasst sich mit der Frage, wie oft ein Primfaktor in der Primfaktorzerlegung von n! für ein n ∈ N vorkommt – um damit eine alternative Darstellung für Fakultäten und Binomialkoeffizienten zu ermöglichen, die das Problem des Überlaufs umgehen kann.

Wir betrachten in dieser Fallstudie die Berechnung von Fakultäten und Binomialkoeffizienten sowohl in ihrer klassischen Definition als auch mit Hilfe des Satzes von Legendre als Produkt von Primfaktorzerlegungen.

Die Notation eines mathematischen Ausdrucks, wie wir ihn aus der Mathematik kennen, zum Beispiel 2 * (7 + 5), bezeichnet man als Infix-Notation. Das Gegenstück dazu heißt Postfix-Notation oder UPN (umgekehrte polnische Notation, engl. reverse polish notation oder abgekürzt RPN). Die umgekehrte polnische Notation wurde 1920 von dem Polen Jan Lukasiewicz erfunden, um mathematische Ausdrücke ohne Vorrangregeln (Klammern) schreiben zu können.

In dieser Fallstudie behandeln wir einen Taschenrechner für arithmetische Ausdrücke in UPN-Darstellung. Reguläre Ausdrücke (std::sregex_iterator, smatch) und Type Traits (std::is_integral, std::is_floating_point) fließen neben anderen Modern C++–Sprachmitteln in der Implementierung mit ein.

Wir betrachten in dieser Fallstudie das Thema „Expression Templates” und damit in Zusammenhang stehend die Technik der genannten „Lazy Evaluation”. Auf einen einfachen Nenner gebracht: „Expression Templates” sind ein Anwendungsfall der Metaprogrammierung. Sie verschieben die Aus­wertung von Ausdrücken in eine separate Funktion, die zu einem späteren Zeitpunkt ausgeführt werden kann. An dieser Stelle wird der Begriff der „Lazy Evaluation” verständlich. Wir betrachten das Thema am Beispiel der Verknüpfung von Zeichenketten, also beispielsweise an einem Ausdruck in der Art

std::string result = "123"s + "ABC"s + "456"s + "XYZ"s + "789"s;

Mit „Expression Templates” lernen Sie einen alternativen Ansatz kennen, einen geschachtelten (arithmetischen) Ausdruck zu berechnen mit dem Vorteil, nahezu alle temporären Objekte zu vermeiden, die bei der klassischen Berechnung eines solchen Ausdrucks entstehen würden.

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.

Unter dem Gray-Code versteht man eine Folge binärer Zahlenketten, die nach dem Ingenieur Frank Gray, einem Forscher in den Bell Laboratories, benannt wurde. Er erhielt im Jahre 1953 für die Nutzung des nach ihm benannten Codes das U.S. Patent No. 2 632 058 „Pulse Code Communication”. Durch die Anzahl der Bits wird die Länge n eines Gray-Codes festgelegt. Man kann sich leicht überlegen, dass es zu einem bestimmten n 2ⁿ unterschiedliche Gray-Codes gibt.

Wir benutzen die Gray-Code-Darstellung, um an Hand einer Reihe von C++–Klassen das Zusammenspiel unterschiedlicher C++–Sprachkonstrukte zu üben und zu vertiefen. Das Endergebnis dieser Aufgabe, die Berechnung von Gray-Codes zu einem beliebigen n, ließe sich sicherlich auch kürzer und direkter erzielen, nur würden wir dabei keinen Lerneffekt erreichen.

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.