Algorithmen und Datenstrukturen
Gegeben ist ein Feld mit Buchstaben:
Ziel ist es, das in diesem Feld eingetragene Wort umzudrehen, so dass man erhält:
Aufgabe: 2
Mit wie vielen solcher Vertauschungsoperationen und mit welchen kann man ein gegebenes Wort umdrehen?
Je weniger Vertauschungsoperationen, desto besser.
Markieren Sie die beiden Buchstaben, die Sie vertauschen möchten und klicken Sie auf „VERTAUSCHEN“. Den zuletzt gewählten Buchstaben können Sie durch einen erneuten Klick darauf wieder abwählen.
Eine einfache und gute Lösung für diese Aufgabe ist es, den ersten mit dem letzten und den zweiten mit dem vorletzten Buchstaben zu tauschen. Dann hat man das gewünschte Ergebnis mit nur zwei Vertauschungsoperationen erreicht und weniger geht für das Beispiel auch nicht.
Allgemein kann man ein Wort der Länge n mit abgerundet n/2 Vertauschungsoperationen umdrehen.