Wie schreibt man ein Programm, das alle Konstellationen pr\u00fcft?
Man formuliert die Vorgehensweise in nat\u00fcrlicher Sprache und macht dann ein Programm daraus.<\/p>\n\n\n\n
N<\/code>. Wir nummerieren die Eichen von [ 0 .. (N-1) ]<\/code> durch.<\/li>- Wir stellen uns einen Kreis vor, indem es (
N*(N-1)+1<\/code>) Positionen gibt. Die Positionen werden im Uhrzeigersinn durchnummeriert, von [ 0 .. N*(N-1) ]<\/code>.<\/li>- Der Abstand zweier B\u00e4ume entspricht der Differenz ihrer Positionen. Wir nennen ihn
distR<\/code> und distL<\/code>, also Distanz nach rechts und nach links. Die Summe dieser Distanzen betr\u00e4gt immer (N*(N-1)+1).<\/code> Die kleinst m\u00f6gliche Distanz ist 1, d.h. zwei B\u00e4ume stehen direkt nebeneinander, die gr\u00f6\u00dftm\u00f6gliche Distanz ist (N*N-1)<\/code>.<\/li>- Wir legen eine Liste (
positions<\/code>) an, die f\u00fcr jeden Baum dessen Position im Kreis enth\u00e4lt. Ist die Position eines Baums noch nicht festgelegt, tragen wir bei ihm einen speziellen Wert ein, der als Positionsangabe unzul\u00e4ssig w\u00e4re, zum Beispiel „-1“.<\/li>- Wir f\u00fcllen
positions<\/code> zun\u00e4chst f\u00fcr jeden Baum mit diesem Wert, denn noch haben wir keinerlei Festlegungen \u00fcber die Anordnung der B\u00e4ume getroffen.<\/li>- Die Grundidee ist nun, dass wir die B\u00e4ume der Reihe nach m\u00f6glichst eng platzieren, wobei wir aber st\u00e4ndig darauf achten, dass alle ihre Abst\u00e4nde unterschiedlich sind.<\/li>
- Naheliegenderweise beginnen wir damit, dass wir den Baum 0 der Position 0 zuordnen. Der n\u00e4chste verf\u00fcgbare Baum ist danach Baum 1.<\/li>
- Wir stellen ihn m\u00f6glichst eng rechts (also im Uhrzeigersinn) daneben. Nun sieht
positions<\/code> so aus <\/code>
[ 0 , 1 , -1 , -1 , -1 , -1 ]<\/code>.<\/li>- Jedesmal wenn wir einen weiteren Baum platziert haben, \u00fcberpr\u00fcfen wir alle Abst\u00e4nde.<\/li>
- Dazu benutzen wir eine Liste aller denkbaren Abst\u00e4nde, die wird
dists<\/code> (distances) nennen. Diese Liste enth\u00e4lt f\u00fcr jeden Abstand 1 oder 0, je nachdem, ob er bei der bisherigen Anordnung der B\u00e4ume vorkommt oder nicht. Nachdem wir die ersten zwei B\u00e4ume platziert haben, enth\u00e4lt dists<\/code> \u00fcberall 1<\/code>, nur die Eintr\u00e4ge an den Positionen 1 und 30 sind 0<\/code>. Aus technischen Gr\u00fcnden enth\u00e4lt dists<\/code> auch ein Element an Position 0, das allerdings immer 0<\/code> ist, da der Mindestabstand zweier B\u00e4ume 1 betr\u00e4gt.<\/li>- Wir fahren damit fort, weitere B\u00e4ume hinzuzuf\u00fcgen<\/span>, und zwar immer m\u00f6glichst eng rechts neben ihrem Vorg\u00e4nger.<\/li>
- Wenn wir jetzt Baum 2 auf die n\u00e4chste Position rechts von Baum 1 stellen wollen, erhalten wir den ersten Konflikt, denn der Abstand 1 kommt bereits vor.<\/li>
- Jedesmal wenn es zu einem Konflikt kommen w\u00fcrde, probieren wir es mit der n\u00e4chsten Position weiter rechts.<\/li>
- Nun sieht
positions<\/code> so aus: [ 0, 1, 3, -1, -1, -1 ]<\/code>.<\/li>- In der Liste der Abst\u00e4nde sind jetzt schon 6 Werte besetzt, n\u00e4mlich 1,2,3,28,29,30. <\/li>
- Manchmal werden wir feststellen, dass kein Platz mehr f\u00fcr den Baum ist, den wir neu hinzuf\u00fcgen wollen, denn direkt links neben Baum 0 ist Schluss). In so einem Fall f\u00fcgen wir den Baum nicht hinzu, sondern schieben den vorherigen<\/em> Baum weiter nach rechts, nat\u00fcrlich immer unter \u00dcberpr\u00fcfung der Abst\u00e4nde.
Haben wir f\u00fcr ihn einen passenden anderen Platz gefunden, versuchen wir wieder, den n\u00e4chsten Baum m\u00f6glichst nah zu platzieren.<\/li>- Achtung: Beim Verschieben eines Baums, der bereits platziert worden war, m\u00fcssen wir die ihm zuvor zugeordneten Abst\u00e4nde wieder als verf\u00fcgbar markieren (auf
0<\/code> setzen) und nach dem Verschieben die neuen Abst\u00e4nde als benutzt markieren (=auf 1<\/code> setzen).<\/li>- Es kann sein, dass es nicht gen\u00fcgt, den vorletzten Baum auf diese Weise zu verschieben; finden wir f\u00fcr ihn keinen passenden Platz mehr, dann entfernen wir auch ihn und schieben analog seinen Vorg\u00e4nger weiter nach rechts.<\/li>
- Wenn es uns gelingt, alle B\u00e4ume zu platzieren, dann haben wir eine L\u00f6sung gefunden. Wir machen dann dennoch weiter, um auch die \u00fcbrigen L\u00f6sungen zu finden. D.h. wir entfernen den letzten Baum und versuchen, seinen Vorg\u00e4nger weiter nach rechts zu schieben. Ist auch f\u00fcr den kein Platz mehr, so entfernen wir ihn und verschieben den Vor-Vorg\u00e4nger usw.; alles wie gehabt!<\/li>
- Irgendwann werden wir an einem Punkt ankommen, an dem es n\u00f6tig werden w\u00fcrde, den zweiten Baum (Baum 1) zu verschieben. In diesem Moment sind wir fertig, denn jede weitere L\u00f6sung w\u00e4re nur noch eine Drehung der bisher gefundenen Anordnungen. Schlie\u00dflich muss immer irgendwo der Abstand 1 vorkommen, den wir gleich zu Beginn verwendet haben. Da bei jeder gefundenen L\u00f6sung immer auch deren Spiegelbild vorkommt, ist die Anzahl der „echt“ verschiedenen L\u00f6sungen halb so gro\u00df wie von uns gefundene Anzahl.<\/li><\/ol>\n\n\n\n
\n\n\n\nMit etwas Nachdenken erkennt man Ansatzpunkte, um Rechenzeit einzusparen. Beispielsweise bilden die Abst\u00e4nde wie oben erl\u00e4utert grunds\u00e4tzlich Paare. Es gen\u00fcgt daher, nur den jeweils kleineren Abstand als benutzt zu markieren. Die Liste der Abst\u00e4nde ist dann nur noch halb so lang.<\/p>\n\n\n\n
Man kann beim Hinzuf\u00fcgen der B\u00e4ume immer sofort mit dem kleinsten noch nicht benutzten Abstand beginnen. Dessen Wert kann man sich merken, anstatt ihn jedesmal neu zu ermitteln. Ebenso kann man sich den gr\u00f6\u00dften benutzten Abstand merken und mit dem Verschieben eines Baums nach rechts aufh\u00f6ren, wenn dieser Wert erreicht werden w\u00fcrde.<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Wie schreibt man ein Programm, das alle Konstellationen pr\u00fcft?Man formuliert die Vorgehensweise in nat\u00fcrlicher Sprache und macht dann ein Programm daraus. Wir nennen die Anzahl der zu verteilenden Eichen N. Wir nummerieren die Eichen von [ 0 .. (N-1) ] durch. Wir stellen uns einen Kreis vor, indem es (N*(N-1)+1) Positionen gibt. Die Positionen werden… Eichen im Kreis – systematische Suche<\/span> weiterlesen<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/posts\/751"}],"collection":[{"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/comments?post=751"}],"version-history":[{"count":7,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/posts\/751\/revisions"}],"predecessor-version":[{"id":761,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/posts\/751\/revisions\/761"}],"wp:attachment":[{"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/media?parent=751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/categories?post=751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/followthescore.org\/schueler-labor\/wp-json\/wp\/v2\/tags?post=751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}