Cpp_11

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.

Eine natürliche Zahl, die identisch ist mit ihrer Kehrzahl wie z.B. 131, wird Palindrom genannt. In dieser Fallstudie betrachten wir eine nicht deterministische Methode zur Berechnung beliebig großer Palindrome.

Die in C++ eingebauten elementaren Datentypen (wie int oder long) stellen keine echte Hilfe dar, wenn wir potentiell unendlich große Palindrome berechnen wollen. Zu diesem Zweck entwerfen wir im Folgenden zunächst eine Klasse Number, mit deren Hilfe sich sehr große Zahlen darstellen lassen. Im Anschluss daran gehen wir auf die Klasse PalindromCalculator ein, um Palindrome zu berechnen.

Die ganzzahligen Standarddatentypen in C++ wie short, int usw. besitzen allesamt die Eigenschaft, dass ihr Wertebereich limitiert ist. Für viele Anwendungen ist dies nicht nachteilig, da sich speziell mit den Datentypen int und long oder auch size_t ziemlich große Zahlen darstellen lassen. Für manche Anwendungen ist die Verarbeitung von ganzen Zahlen beliebiger Größe jedoch unabdingbar. Wir stellen im Folgenden eine Klasse BigInteger vor, die eine exakte Arithmetik vorzeichenbehafteter ganzer Zahlen beliebiger Größe zur Verfügung stellt.

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.

Gegenstand dieser Aufgabe sind Polynomfunktionen, kurz auch Polynome genannt. Formal ist ein Polynom als Summe von Vielfachen von Potenzen einer Variablen x definiert:

P_n(x) = a_nxⁿ + a_n-1x^n-1 + … + a₂x² + a₁x + a₀.

Entwickeln Sie eine Klasse Polynom, die – möglichst einfallsreich – die unterschiedlichen Konstrukte (Instanzvariablen, Konstruktoren, Methoden, inklusive getter- und setter-Methoden, Lambda-Funktionen, Operatoren usw.) zur Definition einer Klasse in “Modern C++” in Anspruch nimmt.

In der Zahlentheorie oder in der Kombinatorik ist eine Partition einer natürlichen Zahl n eine Möglichkeit, n als Summe natürlicher Zahlen zu schreiben. Zwei Summen, die sich nur in der Reihenfolge ihrer Summanden unterscheiden, werden als dieselbe Partition aufgefasst. Zum Beispiel kann die natürliche Zahl 4 auf fünf verschiedene Arten aufgeteilt werden:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1 

Wir beschäftigen uns in dieser Fallstudie mit der Fragestellung, auf wie viele Arten sich eine natürliche Zahl als Summe von natürlichen Zahlen – auch Partition oder Zerlegung genannt – schreiben lässt und wie sich diese mit den Hilfsmitteln von Modern C++ berechnen lassen.