Autor Beitrag
Fiete
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 601
Erhaltene Danke: 339

W7
Delphi 6 pro
BeitragVerfasst: Sa 14.10.17 17:34 
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.
IkoScreen
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
Einloggen, um Attachments anzusehen!
_________________
Fietes Gesetz: use your brain (THINK)

Für diesen Beitrag haben gedankt: Horst_H, Mathematiker, Narses, Tastaro
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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.
ausblenden 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:
//     { Private-Deklarationen }
//    AnzahlInTiefe : array[0..20] of integer;
//    SchonBetreten : array [1..20] of boolean;
 // rekursive Suche 
 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;


ausblenden 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


Zuletzt bearbeitet von Horst_H am Mi 25.10.17 22:30, insgesamt 1-mal bearbeitet

Für diesen Beitrag haben gedankt: Fiete
Fiete Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 601
Erhaltene Danke: 339

W7
Delphi 6 pro
BeitragVerfasst: Di 24.10.17 16:43 
Moin Horst_H,
mein Rechner war defekt, konnte Deine Lösung erst gestern studieren.
Mit dem Array SchonBetreten sieht das Programm eleganter aus, gute Idee!
Gruß an den Tüftler

_________________
Fietes Gesetz: use your brain (THINK)