Modern C++

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.

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.

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.

Unter der Potenzmenge P(S) versteht man die Menge aller möglichen Teilmengen von S. Mit Hilfe zweier Klassen PowerSet und PartialSet sowie einem recht einfachen Algorithmus zur Bestimmung der Potenzmenge betrachten wir diese in Modern C++.