„Selected Programming Assignments – Ausgewählte Programmieraufgaben”

Benutzerdefinierte Literale: Übersetzungszeit oder Laufzeit?

Durch Überladen des so genannten Literaloperators operator"" lassen sich neue Formate für benutzerdefinierte Literale definieren. Diese setzen sich aus einem Standard-Literal und einem benutzerdefinierten Suffix zusammen. Damit kann man in einem C++–Programm beispielsweise schreiben:

100.5_kg
0xFF00FF_rgb
10010101_b

Wie sich benutzerdefinierte Literale in Ihrem Programm definieren lassen und welche Stolperfallen Sie dabei beachten sollten, können Sie in dieser Fallstudie nachlesen.

[Read More]
Cpp_17 

Being constexpr or not being constexpr: Konstante Ausdrücke in C++

Die Berechnung von Ausdrücken zur Übersetzungszeit wurde in C++–17 auf ein neues Niveau angehoben. Längst haben wir es nicht mehr mit nur konstanten Literalen oder einfachen Ausdrücken, bestehend aus einer Summation oder Multiplikation, zu tun. In C++–17 können zur Übersetzungszeit Variablen, Funktionen und auch ganze Klassen bzw. deren Objekte mit entsprechenden Konstruktoren zur Übersetzungszeit ausgeführt bzw. erzeugt werden.

Von Interesse ist dieser Aspekt in der Anwendung zum Beispiel für die Embedded Programmierung, wenn es darum geht, möglichst viele Daten vom Übersetzer berechnen zu lassen, um diese mit Hilfe des Kompilats in das ROM (Read-Only-Memory) einer speziellen Hardware zu packen.

Welche Möglichkeiten sich mit constexpr in C++ 17 eröffnen, zeigen wir an einer Reihe von Fallbeispielen in dieser Studie auf.

[Read More]
Cpp_17 

Gray-Codes

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

[Read More]
Cpp_11  Core 

Parallele Suche nach Primzahlen mit “Hindernissen”

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

[Read More]

Spiegelzahlen – auch Palindrome genannt

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.

[Read More]

Exakte Arithmetik ganzer Zahlen

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.

[Read More]

Das Josephus Problem

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.

[Read More]

Collatz-Zahlenfolgen und C++-Iteratoren

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.

[Read More]

Polynome

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

Pn(x) = anxn + an-1xn-1 + … + a2x2 + a1x + a0.

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.

[Read More]

Das Springerproblem

Das Springerproblem ist auf den Schweizer Mathematiker Leonhard Euler (1707 – 1783) zurückzuführen. Dieser stellte sich vor über 200 Jahren, genauer gesagt im Jahre 1758, die folgende Frage: „Gegeben sei ein leeres Schachbrett. Gibt es eine Zugfolge, mit der der Springer alle (schwarzen und weißen) Felder des Bretts genau einmal besucht?”.

Hmmm, eine gute Frage, wird sich der geneigte Leser jetzt sagen. Möglicherweise kann man sie innerhalb von wenigen Minuten selbst beantworten, schließlich ist ein Schachbrett mit seinen 8×8 Feldern nicht so wirklich groß. Stellt man nach einer ersten Phase euphorischen Suchens ernüchternd fest, dass das Problem doch nicht ganz so einfach zu lösen ist, kommt man vielleicht auf den revolutionären Gedanken, dem Problem mit Hilfe eines Softwareprogramms auf den Leib zu rücken. Dies ist natürlich möglich, wie wir in dieser Fallstudie am Beispiel von Modern C++ zeigen werden.

Neben der Implementierung einer Backtracking-Strategie betrachten wir auch Überlegungen, wie sich das Suchen von Zugfolgen parallelisieren lässt. Die Methode std::async und Objekte, die es „erst in der Zukunft” gibt (std::future<T>), kommen zum Einsatz.

[Read More]