Abt. Rekursion mit XProfan
===================
Rekursion ist an sich keine Stärke von XProfan. Der bekannte "Fluch der Dimensionen" schlägt daher relativ früh zu: Bei Wortkettenbildung z.B. (Letzter Buchstabe = erster Buchstabe des Folgewortes) aus einem "Wortschatz" von max. 70 Wörtern wird das Endziel (23 Wörter in der Kette) erst nach etwa 2 Stunden Rechenzeit erreicht - ein Geduldspiel, aber immerhin: Es geht!
Für praktische Zwecke - eine ähnliche Aufgabe wäre z.B. Maschinenpark-Durchlaufzeitoptimierung ("Job-Shop-Problem") - wäre eine deutliche Beschleunigung z.B. per Assembler wünschenswert. Anbei ein paar Benchmarks.
Gruss
Tabelle "Komplexität vs. Rechenzeit"
-----------------------------------------------
Zu prüfender Wortschatz | Rechenzeit:
47 Worte von max. 70: <0.5 Sekunden
48: ~1 Sek.
49: 6 Sek.
50: 12 s (Interpreter ca. 1 min)
51: 13 s
52: 43 s (... eigenartiger Sprung! Auslagerungsdatei?)
53: 47 s
54: 60 Sekunden = 1 min
55: 154 Sekunden = 1.5 min
56: 163 sek = 2.7 min
57: 172 sek = 2.8 min
58: 372 sek = 6.2 min
59: 338 s = 5.7 min (Eigenartig: Memoryverwaltung scheint zu optimieren.
Von Datenanordnung abhängigies Teilergebnis: Max. Kettenlänge 20, kommt hier 80 mal vor)
60: 366 s = 6.1 min
61: 1747 s 22 lang (460 mal) 29.5 min (nächster eigenartiger Sprung!)
62: 1773 s exe 22 (461) = 29.55 min
63: 2017 s exe 22 (416) = 33.62 min
64: 2300 s exe 22 (416) ? 38.33 min (bis hier am Laptop getestet)
...
70: ~7200 sek = 120 min = Vermutlich ~ 2 Std ??
WindowTitle upper$(" Last_Letter = First_Letter-Spiel: Längste Wortkette bilden")
'(CL) 2018-08 von BBC-Basic nach XProfan11.2a by P.Specht, Vienna/EU
' OHNE JEDWEDE GEWÄHR! Without any warranty whatsoever! Rechte Dritter nicht geprüft!
'REKURSIVER CODE! Q: http://rosettacode.org/wiki/Last_letter-first_letter
WindowStyle 24:CLS:font 1:var Pokemon$=\
"audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon "+\
"cresselia croagunk darmanitan deino emboar emolga exeggcute gabite "+\
"girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan "+\
"kricketune landorus ledyba loudred lumineon lunatone machamp magnezone mamoswine "+\
"nosepass petilil pidgeotto pikachu pinsir poliwrath poochyena porygon2 "+\
"porygonz registeel relicanth remoraid rufflet sableye scolipede scrafty seaking "+\
"sealeo silcoon simisear snivy snorlax spoink starly tirtouga trapinch treecko "+\
"tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask"
declare i%,w$,n&,Names$[]:Names$[]=explode(Pokemon$," ")
print "\nZUR AUSWAHL STEHEN HIER DIE POKEMONS: ";Pokemon$
print "\n Auswahlgroesse N [n=35..70 > ~ 2h prc-Zeit] = ";:input n&:print
case n&=0:n&=sizeof(Names$[])
print " ";n&;"/70: "; 'Rechenzeit für Test verkürzen durch Kürzung der Auswahl
var TM&=&GetTickCount
var maxPathLength% = 0
var maxPathLengthCount% = 0
var maxPathExample$ = ""
whileloop 0,n&-1:i%=&Loop
w$=names$[0]:names$[0]=names$[i%]:names$[i%]=w$
PROClastfirst(names$[],1)
w$=names$[0]:names$[0]=names$[i%]:names$[i%]=w$
endwhile
PRINT " ERGEBNIS:\n Kettenlaenge [Worte] = ";maxPathLength%
Print " Ermittelt in ";int((&gettickcount-tm&)/1000);" Sekunden"
PRINT " Anzahl Loesungen mit dieser Laenge = ";maxPathLengthCount%
PRINT " Loesungsbeispiel (auch in Zwischenablage): \n\n ";maxPathExample$
clearclip:putclip maxPathExample$
beep:Waitinput
END
Proc PROClastfirst :parameters names$[],offset%
declare L%,i%
IF offset% > maxPathLength%
maxPathLength% = offset%
maxPathLengthCount% = 1
ELSEIF offset% = maxPathLength%
inc maxPathLengthCount%
maxPathExample$ = ""
whileloop 0,offset%-1
maxPathExample$ = maxPathExample$ +names$[&Loop]+"\n "
endwhile
ENDIF
L%=ord(RIGHT$(names$[offset%-1],1))
Whileloop offset%,n&-1:i%=&Loop
IF ord(names$[i%]) = L%
w$=names$[i%]:names$[i%]=names$[offset%]:names$[offset%]=w$
PROClastfirst(names$[], offset%+1)
w$=names$[i%]:names$[i%]=names$[offset%]:names$[offset%]=w$
ENDIF
Endwhile
ENDPROC
'Originalergebnis:
'-----------------
'Maximum length = 23; Number of solutions with that length = 1248
'One such solution:
' machamp pinsir rufflet trapinch heatmor remoraid darmanitan nosepass
' starly yamask kricketune exeggcute emboar relicanth haxorus simisear
' registeel landorus seaking girafarig gabite emolga audino
Alles anzeigen
P.S.: Lt. Musterergebnis sollte bei N&=70 Länge 23 herauskommen, Details siehe Programmtext