Morse-Alphabet

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.

[Read More]

Das Haus des Nikolaus

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?

/img/houseofsantaclaus/HouseSantaClaus_01.png

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.

[Read More]

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]

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]