Fiete - Sa 14.10.17 17:34
Titel: Käfer auf Ikosaeder
Moin,
ein Käfer soll eine möglichst schnelle Reise über alle Seitenflächen des Ikosaeders machen.
Ein Ikosaeder ist ein regelmäßiges Polyeder mit 20 Seitenflächen, die die Nummern 1 bis 20 tragen.
Die Reise darf nur über jeweils benachbarte Seitenflächen des Ikosaeders erfolgen.
Zwei Seitenflächen sind benachbart, wenn sie eine gemeinsame Kante besitzen.
Der Käfer muss jede Seitenfläche genau einmal betreten.
Jede der 20 Flächen kann Startfläche sein.
Auf jeder Seitenfläche muss der Käfer eine Pause einlegen.
Die Länge der Pausen (in Sekunden) errechnet sich durch Multiplikation der Schrittnummer (von 1 bis 20)
mit der Nummer der betretenen Seitenfläche. Der Wechsel von einer Seitenfläche zur nächsten dauert eine Sekunde.
Für eine Reise mit der Route
[12,2,18,5,15,7,17,10,8,20,14,4,11,13,1,19,3,16,6,9]
benötigt der Käfer 2176 Sekunden.
(Aufgabe 1, BWInf 10, 1991)
Viel Spaß beim Studieren
Gruß Fiete
Horst_H - So 15.10.17 12:04
Hallo,
nur 3240 Wege.
Ich habe ein wenig geändert und eine Funktion durch ein Feld von Wahrheitswerten ersetzt.
Was die Laufzeit, wegen der Ausgabe, nur minimalst ändert (Linux 64-Bit Lazarus1.8 statt 75 ms nun 48 ms )
Ich habe mal zählen lassen, wann es nicht mehr weiterging.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29:
| procedure TIkosaeder.WegSuchen(von,Tiefe:Integer); var K:Integer; kamNichtWeiter : boolean; begin Weg[Tiefe]:=von; SchonBetreten[von] := true; if Tiefe=20 then WegGefunden else begin kamNichtWeiter:= true; for K:=1 to 3 do Begin if not SchonBetreten[Nachbar[von,K]] then Begin kamNichtWeiter:= false; WegSuchen(Nachbar[von,K],Tiefe+1); end; end; If kamNichtWeiter then inc(AnzahlInTiefe[tiefe]); end; SchonBetreten[von] := false; end; |
Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| Tiefe 8 Anzahl 120 Tiefe 9 Anzahl 120 Tiefe 10 Anzahl 240 Tiefe 11 Anzahl 840 Tiefe 12 Anzahl 1200 Tiefe 13 Anzahl 2160 Tiefe 14 Anzahl 4920 Tiefe 15 Anzahl 7200 Tiefe 16 Anzahl 9240 Tiefe 17 Anzahl 12720 Tiefe 18 Anzahl 12600 Tiefe 19 Anzahl 7800 |
Gruß Horst