Stell dir einige Eichen vor, die kreisförmig angeordnet sind. Deine Aufgabe besteht darin, die Bäume unregelmäßig so auf der Kreislinie zu verteilen, dass keine zwei Bäume den selben Abstand voneinander haben. Der Abstand wird in ganzen Zahlen entlang des Kreisbogens gemessen.
Schaffst du es bei einem Kreis der Größe 21 mit 5 Eichen durch Probieren? Bedenke, dass es insgesamt 20 verschiedene Abstände gibt!
Wie viele Lösungen gibt es? Wir wollen als Lösungen nur Anordnungen gelten lassen, die nicht durch Drehung oder Spiegelung auseinander hervorgehen — ja, da wird das systematische Probieren schon ein wenig mühsam…
Für sechs Eichen (Kreisumfang = 31) wollen wir dann doch lieber den Rechner verwenden. Schreibe ein Programm in einer beliebigen Programmiersprache (python, Java, Javascript, php, C ), welches alle Lösungen findet und ausgibt.
Lass das Programm mit 7, 8 und 9 Eichen laufen. Wie unterscheiden sich die Laufzeiten? Die zugehörigen Kreisumfänge betragen jeweils N*(N-1) + 1. also 43, 57 und 73.
Du könntest ganz viele beliebige Anordnungen der Eichen per Zufall erzeugen und dann jeweils prüfen, ob alle ihre Abstände verschieden sind. Aber du wirst dabei nie wissen, ob du alle Lösungen gefunden hast. Außerdem werden viele Anordnungen mehrfach erzeugt, wenn du das Programm sehr lange laufen lässt.
Vermutlich probiert dein Programm daher einfach alle denkbaren Anordnungen durch. Kannst du es so verbessern, dass nur deutlich weniger Anordnungen untersucht werden müssen?
Hast du Python verwendet? Dann ist dein Programm vermutlich kurz und elegant, aber es läuft ungefähr 7 mal langsamer als mit Javascript. Gegenüber Java und C ist der Unterschied noch größer.
Dein Rechner hat vier oder acht Rechenkerne, aber dein Programm nutzt vermutlich nur einen davon. Kannst du ihm beibringen, alle Kerne zu nutzen?
Hast du eine moderne Grafikkarte (Geforce ..) ? Dann besitzt die Grafikkarte vermutlich 100 mal mehr Rechenleistung als dein „Haupt“-CPU. Du kannst eine gewaltige Beschleunigung erzielen, wenn du das Programm auf der Grafikkarte ausführst. Wie das geht? Schau dir mal CUDA an! CUDA unterstützt nicht nur C/C++, sondern auch Perl, Python , Ruby, Java und .NET!