ALGORITHMEN - Teil XVIII: Neueste Fortschritte in Künstlicher Dummheit

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    Unsere Datenschutzerklärung wurde aktualisiert. Mit der Nutzung unseres Forums akzeptierst Du unsere Datenschutzerklärung. Du bestätigst zudem, dass Du mindestens 16 Jahre alt bist.

    • Abt. Ungestelltes Rätsel da oben
      =====================
      In ersten Simulationen ergaben sich je nach Reihenfolge der beiden ungeraden Tauschvorgänge ständig andere Ergebnisse. Das war aber falsch, wie sich bei näherem Durchdenken herausstellte!: Plätze können nur Läufer tauschen, die "Nachbarn" sind - es gibt keine "Doppel-Bocksprünge" über den mittleren Läufer. Das Ergebnis war dann stabil - aber noch immer falsch, weil die Ausgabe in Trikot-Nummern- statt Namensposiitionen erfolgen muss.

      So hat sich letztlich das "intuitive" Ergebnis von AHT voll bestätigt: Selbst ein 2-stündiger Programmlauf mit zufälliger Platztauschreihenfolge lieferte keine anderen Ergebnisse - jetzt weiss ich wenigstens, warum!
      War also ein ziemlich lehrreiches Beispiel, das ungestellte Rätsel!
      Gruss

      Quellcode

      1. WindowTitle "Ungestelltes Rätsel: Laufsimulation"
      2. Window %maxx/4,0 - %maxx/2,%maxy-40
      3. font 1
      4. randomize
      5. declare p&,s&,t& ,tmp&,rn!,m&
      6. declare ps&,st&,pt&, n&,verbose&
      7. 'Startreihenfolge = P:1 - S:2 - T:3
      8. 'P und S tauschen die Plätze. Das fand 9 mal statt.
      9. 'S und T tauschen die Plätze. Das fand 10 mal statt.
      10. 'P und T tauschen die Plätze. Das fand 11 mal statt.
      11. 'Das Geheimnis: Die Platz-Tauschvorgänge (9,10 und 11 mal) können nur vorkommen,
      12. 'wenn die jeweiligen Läufer gerade Nachbarn sind.
      13. 'Hier werden Wettläufe mit zufallsgesteuerten Überholvorgängen simuliert.
      14. 'Läufe, bei denen noch Überholvorgänge offen sind, die Läufer aber keine Nachbarn,
      15. 'müssen verworfen werden - der einzige Grund für die Stabilität des Ergebnisses!
      16. verbose&=0 '1 = on, 0 = off
      17. Print ansitooem$("\n Ausführlich? [0/1]: ";):input verbose&
      18. while 1
      19. inc m&
      20. p&=1.:s&=2.:t&=3.
      21. ps&=0:st&=0:pt&=0
      22. case verbose&:print
      23. n&=0
      24. repeat
      25. inc n&
      26. rn!=rnd()
      27. if rn!<1/3
      28. if (ps&<9) and (abs(p&-s&)=1):tmp&=p&:p&=s&:s&=tmp&:inc ps&:endif
      29. elseif (rn!>=1/3) and (rn!<2/3)
      30. if (st&<10) and (abs(t&-s&)=1):tmp&=s&:s&=t&:t&=tmp&:inc st&:endif
      31. elseif (rn!>=2/3)
      32. if (pt&<11) and (abs(p&-t&)=1):tmp&=p&:p&=t&:t&=tmp&:inc pt&:endif
      33. endif
      34. if verbose&
      35. print " P:",p&;"., S:",s&;"., T:",t&;". ";
      36. print "Getauscht haben P<>S:";ps&;" S<>T:";st&;" P<>T:";pt&
      37. endif
      38. case n&>=200:BREAK
      39. until (ps&=9) and (st&=10) and (pt&=11)
      40. ' Weitere Komplikation bei der Art der Ausgabe: Reihenfolge der numerierten Läufertrikots!
      41. if n&<200
      42. case verbose&:print " Laufergebnis: ";
      43. 'Ausgabe nicht p&,s&,t& sondern Platz 1,2,3:
      44. print " ";m&;": ",
      45. if verbose&
      46. case p&=1:print " P",
      47. case s&=1:print " S",
      48. case t&=1:print " T",
      49. case p&=2:print "P",
      50. case s&=2:print "S",
      51. case t&=2:print "T",
      52. case p&=3:print "P = ",
      53. case s&=3:print "S = ",
      54. case t&=3:print "T = ",
      55. endif
      56. case p&=1:print "1",
      57. case s&=1:print "2",
      58. case t&=1:print "3",
      59. case p&=2:print "1",
      60. case s&=2:print "2",
      61. case t&=2:print "3",
      62. case p&=3:print "1"
      63. case s&=3:print "2"
      64. case t&=3:print "3"
      65. ifnot (p&=3) and (s&=1) and (t&=2)
      66. sound 2000,400
      67. print "???????"
      68. waitinput
      69. endif
      70. case verbose&:waitinput 500
      71. else
      72. if verbose&
      73. print ansitooem$(" Nachbarschaftsfehler!")
      74. sound 70,70
      75. waitinput 500
      76. endif
      77. endif
      78. endwhile
      Alles anzeigen
    • Abt. Flächenberechnung mal anders
      ==========================
      Für digitale1) reguläre2) Vielecke3), egal ob konvex4) oder mit konkaven5) Eckpunkten, gilt die

      Flächenformel von Pick6)

      Fläche *) = Gitterpunkte_exakt_am_Rand / 2 + Innere_Punkte - 1

      Tipp: Auf kariertem Papier ausprobieren, oder dieses Video schauen!

      Gruss
      ________
      1) Die Eckpunkte liegen auf Gitterpunkten
      2) wo sich die Begrenzungslinien nirgendwo überschneiden
      3) Linienzüge aus geraden Strecken, aka: Polygone
      4) Kein Innenwinkel wäre über 180 °
      5) Es gibt nach innen führende Kanten bzw. Innenwinkel > 180 °
      6) Georg Pick, österr. Mathematiker (1859-1942)
      *) gemessen in Gitterquadraten!
    • Abt. UnvmR 33 ´Median´
      =================
      Median ist ein Begriff aus der ´Beschreibenden Statistik´. Der Median ist der Wert des Elementes in der Mitte einer Zahlengruppe, wenn man diese sortiert nach Größe aufreiht. Anmerkung: Bei geraden Werte-Anzahlen nimmt man den arithmetischen Mittelwert der beiden ´mittigsten´ Elemente als Median.

      Gegeben sei die Reihe: 61, 3, 23, 17, 9 und 1.
      Gesucht: Der Mittelwert der Zahlen sowie der Median.


      P.S.: Der Median wird auch Zentralwert genannt. Seine Position in der sortierten Zahlenabfolge ist Pos = (Werteanzahl + 1) / 2

      Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von p. specht ()

    • Lösung zu UnvmR 33
      --------------------
      Spoiler anzeigen
      Mittelwert: 19, Median: 13, d.h. die Verteilung der Werte ist gegenüber einer linear ansteigenden Verteilung in der Mitte zurückgeblieben. Man spricht von einer "konkaven" Verteilung.

      Programm dazu:

      Quellcode

      1. WindowTitle upper$(\
      2. "Mittelwert und Median einer zuerst ungeordneten Einzelwerte-Reihe")
      3. cls:set("decimals",17):font 2:print
      4. declare z![],tmp$[],data$,n&,sum!
      5. data$=\
      6. "61, 3, 23, 17, 9 und 1 und "+\
      7. "61, 3, 23, 17, 9 und 1."
      8. data$=translate$(data$," und ",",")
      9. tmp$[]=explode(data$,","):clear data$
      10. n&=sizeof(tmp$[]):clear z![]:setsize z![],n&
      11. z![]=val(tmp$[&index]):clear tmp$[]:print " ";
      12. sum!=0:whileloop 0,n&-1:sum!=sum!+z![&Loop]
      13. case n&<200:print format$("%g",z![&Loop]),
      14. endwhile
      15. print "\n\n Anzahl: ";n&;", Mittelwert: ";format$("%g",sum!/n&)
      16. QuickSortUp z![]
      17. print "\n ";:case n&<200:whileloop 0,n&-1:print format$("%g",z![&Loop]),:endwhile
      18. print "\n\n Median: ";
      19. if n&>0
      20. if n& mod 2 'ungerade
      21. print format$("%g",z![(n&-1)\2]),
      22. print " an 0-Index ";format$("%g",(n&-1)\2)
      23. else
      24. print format$("%g",(z![(n&-1)\2]+z![(n&-1)\2+1])/2),
      25. print " an 0-Index ";format$("%g",(n&-1)\2),"und",format$("%g",(n&-1)\2+1)
      26. endif
      27. else
      28. print "0."
      29. endif
      30. print "\n\n OK.":sound 4000,50
      31. waitinput
      32. End
      33. proc QuickSortUp:parameters a![]:declare n&,p&,l&,r&,s&,sl&[],sr&[],w!
      34. declare x!,i&,j&:n&=sizeof(a![]):s&=1:sl&[1]=0:sr&[1]=n&-1
      35. while s&>0:l&=sl&[s&]:r&=sr&[s&]:s&=s&-1:while l&<r&:i&=l&:j&=r&:p&=(l&+r&)\2
      36. if a![l&]>a![p&]:w!=a![l&]:a![l&]=a![p&]:a![p&]=w!:endif
      37. if a![l&]>a![r&]:w!=a![l&]:a![l&]=a![r&]:a![r&]=w!:endif
      38. if a![p&]>a![r&]:w!=a![p&]:a![p&]=a![r&]:a![r&]=w!:endif:x!=a![p&]
      39. while i&<=j&:while a![i&]<x!:inc i&:endwhile:while x!<a![j&]:dec j&:endwhile
      40. if i&<=j&:w!=a![i&]:a![i&]=a![j&]:a![j&]=w!:inc i&:dec j&:endif:endwhile
      41. if (j&-l&)<(r&-i&):if i&<r&:inc s&:sl&[s&]=i&:sr&[s&]=r&:endif:r&=j&:else
      42. if l&<j&:inc s&:sl&[s&]=l&:sr&[s&]=j&:endif:l&=i&:endif:endwhile:endwhile
      43. endproc
      Alles anzeigen
    • Abt. Stringstheorie I.: Statische Strings (XPr-11.2a)
      ===============

      Quellcode

      1. WindowTitle "Stringarrayelemente einzeln byteweise ansprechen"
      2. cls:font 2
      3. declare a$[3],ad&,by&,lup&,ndx&
      4. a$[0]="Null":a$[1]="Eins":a$[2]="Zwei":a$[3]="Schluss"
      5. Whileloop 0,sizeof(a$[])-1:ndx&=&Loop
      6. ad&=addr(a$[ndx&])
      7. lup&=0
      8. repeat
      9. by&=byte(ad&+lup&,0)
      10. print chr$(by&);
      11. inc lup&
      12. until by&=0
      13. print
      14. Endwhile
      15. beep
      16. waitinput
      Alles anzeigen
    • Abt. Stringstheorie II.: Len, String und Schlussbyte 0 aus Speicher auslesen
      ================

      Quellcode

      1. WindowTitle "STATISCHE STRINGARRAY-ELEMENTE: LEN auslesen"
      2. CLS:font 1
      3. declare a$[4],b$[2],le&,x$,n&
      4. a$[0]="ZERO_123"
      5. a$[1]="uno due tre quattro cinque sei sette otto nove dieci"
      6. a$[2]="PREGO"
      7. a$[3]="AVANTI"
      8. a$[4]="FINITO"
      9. b$[0]="B-NULL"
      10. b$[1]="B-EINS"
      11. b$[2]="B-ZWEI"
      12. n&=1
      13. print "\n Addr:",addr(a$[n&]),
      14. print " String:",char$( addr(a$[n&]), 0, long(addr(a$[n&])-4,0) )
      15. print
      16. print " ";long(addr(a$[n&])-16,0);" = ?"
      17. print " ";long(addr(a$[n&])-12,0);" = ?"
      18. print " ";int( addr(a$[n&]) - long(addr(a$[n&])-12,0) );" = Versatz"
      19. print
      20. print " ";long(addr(a$[n&])-8,0);" = 1 Typ?"
      21. print " ";long(addr(a$[n&])-4,0);" = Laenge ";len(a$[1])
      22. print " ";byte(addr(a$[n&])+len(a$[n&]),0);" = Schlussbyte 0 "
      23. print " ";byte(addr(a$[n&])+len(a$[n&]),1);" = Byte nach Schlussbyte"
      24. print " ";Chr$(byte(addr(a$[n&])+len(a$[n&]),1));" = Zeichen nach dem Schlussbyte"
      25. sound 9000,32
      26. waitinput:End
      Alles anzeigen
    • Abt. Programm ermittelt seine Programmlänge selbst
      =======================================
      Nur für prc bzw exe. Letztere enthält dann zusätzlich den ganzen Compiler, daher viel größere Endadresse!
      Möglichkeit für Unversehrtheits-Test oder z.B., ob schon gepatched wurde.
      Gruss

      Quellcode

      1. Print %ProgEnd
      2. waitinput
      3. ProgEnd
    • Abt. XPro 11 only?
      ==============
      cls
      def ! -12.3456
      print ! +" <<<"
      waitinput
      End

      Und hier eine Zusammenfassung des Wissensstandes zum XProfan-11 Variablenverwaltungssystem. Ziel war eigenntlich ein flottes IMPLODE$, leider reichen die mir verfügbaren Daten dazu aber nicht aus. Und mit X1/X2 hat sich sehr sehr vieles verändert. Daher: Nutzung auf eigene Gefahr!

      Quellcode

      1. Cls:font 1
      2. declare Nr1!,A$[3],ad&,a%[3],b$,c&[],d![],e$[10],f$[]
      3. a$[0]="ZILCH":a$[1]="ENE":a$[2]="MENE":a$[3]="MUH"
      4. ad&=addr(a$[]):print "\n ";ad&
      5. var ArrayNr&=a%[]:print " a%[] ist als ";ArrayNr&;". Array deklariert!"
      6. var n&=1
      7. var x!=678
      8. var a!=12.3
      9. declare z!
      10. var b!=4.56
      11. var k%=1
      12. var cccccc!=7.89
      13. var xxx!=55.5
      14. print
      15. print " ";n&;". Floatvariable relativ zu Nr1! :"
      16. print " Name = ";string$(long(addr(Nr1!)-4+(n&)*12,0),0)
      17. print " Inhalt = ";float(addr(Nr1!)+(n&)*12,0)
      18. print " Laenge des ";n&;". Floatvariablennamens inkl. Postfix = ";long(long(addr(Nr1!)-4 +(n&)*12,0)-4,0)
      19. waitinput
      20. cls
      21. print "STRING IN-PLACE VERLÄNGERN"
      22. var a$="Test"
      23. var v&=addr(a$)
      24. char v&,len(a$) = "_d"+chr$(0)
      25. v&=addr(a$)-4:long v&,0 = len(a$)+2
      26. print a$
      27. waitInput
      Alles anzeigen

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von p. specht ()

    • Abt. Billigflieger-Tipps
      ================
      In diesem Youtube-Video gibt ein Buchungs-Spezialist Tipps, wie man an die günstigsten Flugtarife kommt. Etwa ein Viertel aller Passagiere fliegen im Grundpreis deutlich günstiger: Die Preisunterschiede können 1000 % und mehr ausmachen! Klar, dass dann jeder Extra-Handgriff auch extra verrechnet wird - Kostenfallen werden auch behandelt!
      Gruss
    • So ein Implode$ ist doch ab Version 10 nicht schwer :

      Quellcode

      1. Declare String A[], Long B[], Float C[]
      2. CLS
      3. A[] = "Hallo", "du", "da !"
      4. B[] = 1, 2, 3, 4, 5
      5. C[] = 1.5, 2.6, 10.7, 15.0, 20.30
      6. Print Implode(A[], "|")
      7. Print Implode(B[], ",")
      8. Print Implode(C[], ",")
      9. WaitKey
      10. PROC Implode
      11. If PType$(1) = "$[]"
      12. Parameters String B[], String D
      13. ElseIf PType$(1) = "&[]"
      14. Parameters Long B[], String D
      15. ElseIf PType$(1) = "%[]"
      16. Parameters Int B[], String D
      17. ElseIf PType$(1) = "![]"
      18. Parameters Float B[], String D
      19. Set("Decimals", 2)
      20. EndIf
      21. CLEARLIST
      22. Move("ArrToList", B[])
      23. RETURN Move("ListToStr", D)
      24. ENDPROC
      25. End
      Alles anzeigen
      Schneller wirst du es mit den Bordmitteln von XProfan 11 nicht bekommen.

    • @H.Brill: Super, danke!

      Hab´s an XProfan 11.2a free angepasst. Ist natürlich nicht ganz so elegant!
      Gruss

      Quellcode

      1. WindowTitle "H.Brill-Implode for XProfan-11.2a free"
      2. 'Programm von Heinz Brill, von p.specht nach XProfan 11 protiert
      3. CLS:font 2
      4. Declare A$[],B&[],C![],D%[],tmp$[]
      5. A$[] = explode("Hallo,du,da !",",")
      6. tmp$[]=explode("1, 2, 3, 4, 5",",")
      7. setsize B&[],sizeof(tmp$[]):B&[]=val(tmp$[&index])
      8. clear tmp$[]:tmp$[]=explode("1.5, 2.6, 10.7, 15.0, 20.30",",")
      9. setsize C![],sizeof(tmp$[]):c![]=val(tmp$[&index])
      10. clear tmp$[]:tmp$[]=explode("987,654,321",",")
      11. setsize D%[],sizeof(tmp$[]):D%[]=val(tmp$[&index])
      12. clear tmp$[]
      13. print sizeof(A$[]), sizeof(B&[]), sizeof(C![]), sizeof(D%[])
      14. Print "\n Anfang>";Implode(A$[],"|");"<Ende"
      15. Print "\n Anfang>";Implode(B&[],",");"<Ende"
      16. Print "\n Anfang>";Implode(C![]," *** ");"<Ende"
      17. Print "\n Anfang>";IntImplode(D%[],",");"<Ende"
      18. Waitinput
      19. End
      20. PROC Implode :ClearList
      21. If PType$(1)="$[]":Parameters B$[],D$
      22. MoveArrtoList(B$[]):Return MoveListToStr$(D$)
      23. ElseIf PType$(1)="&[]":Parameters B&[],D$
      24. MoveArrtoList(B&[]):Return MoveListToStr$(D$)
      25. ElseIf PType$(1)="%[]":parameters B%[],D$
      26. MoveArrtoList(B%[]):Return MoveListToStr$(D$)
      27. ElseIf PType$(1)="![]":Parameters B![],D$:Set("Decimals",2)
      28. MoveArrtoList(B![]):Return MoveListToStr$(D$)
      29. Else: beep:Return "\n *** IMPLODE ERROR *** ":EndIf
      30. ENDPROC
      31. PROC IntImplode :ClearList
      32. If PType$(1)="&[]":Parameters B%[],D$
      33. MoveArrtoList(B%[]):Return MoveListToStr$(D$)
      34. Else:beep:Return "\n *** IntIMPLODE ERROR *** ":EndIf
      35. ENDPROC
      Alles anzeigen
    • Abt. (Trenn-)Zeichenfolgen in Strings flexibel tauschen
      =========================================
      ... in den Grenzen von XProfan-11.2a free.
      Gruss

      P.S.: Ursprünglicher Gedanke war, Translate$ für in Strings geladene Dateien schneller zu machen.

      Quellcode

      1. WindowTitle "(Trenn)-Zeichenfolgen in Strings tauschen (XProfan-11: <2^18 Einträge)"
      2. Window 0,0-%maxx,%maxy-40:font 2
      3. declare x$,n&,lx&,otrenn$,ntrenn$,t$[]
      4. otrenn$="," : ntrenn$="|Trenner|"
      5. x$=mkstr$("Randomshit"+otrenn$+"1234567890"+otrenn$,131071) '2^17-1 (2 Trenner!)
      6. lx&=len(x$):print "\n String hat ";lx&;" Zeichen in max. 262.142 Zeilen"
      7. print "\n Exploding ..."
      8. t$[]=explode(x$,otrenn$)
      9. clear x$
      10. n&=sizeof(t$[])-1:print "\n ";n&,"mal ´";otrenn$;"´ als Trenner"
      11. beep:print "\n Imploding ... "
      12. x$=Implode$(t$[],ntrenn$)
      13. beep
      14. print " Ausgabe-Stringlänge:",len(x$),"Zeichen"
      15. print "\n ANFANG>";left$(x$,80);"..."
      16. print "...";right$(x$,80);"<ENDE"
      17. waitinput
      18. end
      19. PROC Implode$ :ClearList:declare erg$
      20. If PType$(1)="$[]":Parameters B$[],D$
      21. MoveArrtoList(B$[]):erg$=MoveListToStr$(D$)
      22. return left$(erg$,len(erg$)-len(D$)*2)
      23. Else: beep:Return "\n *** IMPLODE$() ERROR *** ":EndIf
      24. ENDPROC
      Alles anzeigen

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von p. specht ()

    • Abt. Konsolenfenser CMD.EXE: Fehlermeldungen umleiten
      ==========================================
      Beim Umleiten der Ausgabe eines Befehls oder eines Konsolenprogrammes mit dem ">"-Symbol werden Fehlermeldungen normalerweise weiterhin auf den Konsolenschirm ausgegeben. Dies vor allem deshalb, weil Fehlermeldungen von den meisten Programmen auf den separaten Standard-Fehlerstream statt auf den Standard-Outputstream gesendet werden.
      Normale Ausgaben werden stets auf den Standardoutput-Kanal STDOUT gesendet, Fehlermeldungen dagegen auf STDERR. (Ausserdem gibt es noch STDIN).

      Will man auch STDERR umleiten, gibt es den Konsolenbefehl "2>", das Fehlerumleitungssymbol.

      BEISPIEL: Der CMD-Fenster-Befehl "DIR file.xxx" (wobei file.xxx nicht vorhanden ist) bewirkt folgende Ausgabe:

      Datenträger in Laufwerk F ist Candy Zuckerrohr, Datenträger-Seriennummer 34EC 0876

      Datei nicht gefunden.


      Will man den regulären Teil dieser Ausgabe unterdrücken, kann man diese mittels "dir file.xxx > nul" an das Gerät NUL umleiten. Diese Daten verschwinden dann sozusagen im Nichts, und man sieht nurmehr die Fehlermeldung:

      Datei nicht gefunden.

      Um die Fehlermeldung umzuleiten in einen Datei oder z.B. nach NUL, benutzt man den Befehl "2>":

      dir file.xxx 2> nul

      Man kann auch die Ausgabe an einen Ort oder ein Gerät (z.B. PRT, LPT0) umleiten, und die Fehler an einen anderen.

      dir file.xxx > output.msg 2> output.err

      Will man die Fehler und die Standardausgabe gemeinsam ausgeben, kann man den Rückbezug "&1" wie am ein Gerät benutzen, z.B. um die Ausgabe von STDERR nach STDOUT umzuleiten und dann die Ausgabe von STDOUT in eine Datei zu senden:

      dir file.xxx 1> output.msg 2>&1

      Infostand 18.04.2018
    • p. specht schrieb:

      Abt. Programm ermittelt seine Programmlänge selbst
      =======================================
      Nur für prc bzw exe. Letztere enthält dann zusätzlich den ganzen Compiler, daher viel größere Endadresse!
      Die exe enthält nicht den Compiler, sondern das Runtime-Modul, die prfrun32.exe!

      (Genauer gesagt ist in aktuellen XProfan-Versionen (ab Version X3) die exe die umbenannte prfrun32.exe mit dem compilierten Programm als Ressource. Bei früheren Version wurde das Compilat an die prfrun32.exe angehängt.)

      Gruß
      Roland
      Intel Duo E8400 3,0 GHz / 4 GB RAM / 1000 GB HDD / ATI Radeon HD4770 512 MB / Windows 7(32) - XProfan X4
      AMD Athlon II X2 2,9 GHz / 3 GB RAM / 500 GB HDD / ATI Radeon 3000 (onboard) / Windows 10(64) - XProfan X4


      http://www.xprofan.de
    • RGH schrieb:

      die exe die umbenannte prfrun32.exe mit dem compilierten Programm als Ressource.
      Also ist es im Prinzip ab X3 nicht mehr nötig, Icons vor der Compilierung in die PRFRUN32.EXE einzufügen - man könnte die Resourcen auch nachträglich bearbeiten. Sehe ich das so richtig?
      Ist dann ja eigentlich genau so wie bei Autoit.
      ________________________________________________________

      PPFScanner PPFS Android MisterXMail@web.de
      Mfg AHT
    • Abt. Längste gemeinsame Elemente-Kette finden
      ================================
      Wieder eine Rosetta-code Aufgabe: Hier die Lösungsvariante 1 "REKURSIVE METHODE".
      Vorteiil: Relativ einfach. Nachteil: Skaliert zeitlich ab 11*11 Zeichen ziemlich schlecht.
      Anwendung: Durchschnitt zweier geordneter Mengen (aka "Abfolgen") ermitteln.
      Gruss

      P.S.: Schneller sind der Hirschberg-Algorithmus (für lange Inputs - verwendet in der Gentechnik) sowie Dynamische Programmierungsansätze (Speicherintensiv, aber sauschnell).

      Quellcode

      1. Windowtitle upper$("Längste gemeinsame Elemente-Kette finden")
      2. 'Rosetta code http://rosettacode.org/wiki/Longest_common_subsequence
      3. 'Variante 1 - REKURSIVE METHODE, ab len(11*11) auch im Compiler langsam
      4. cls:font 2:declare u1$,u2$, tm&
      5. u1$="1234":u2$="1224533324"
      6. Print "\n Testbeispiel 1 (4 x 10):"
      7. tm&=&GetTickCount
      8. PRINT "\n Ergebnis: ";FNlcs(u1$,u2$)
      9. tm&=&GetTickCount-tm&
      10. print "\n Gefunden in ";tm&;" ms"
      11. sound 3000,30
      12. u1$="thisisatest":u2$="testing12"
      13. print "\n\n Testbeispiel 2 (11 x 9):"
      14. tm&=&GetTickCount
      15. PRINT "\n Ergebnis: ";FNlcs(u1$,u2$)
      16. tm&=&GetTickCount-tm&
      17. print "\n Gefunden in ";tm&;" ms"
      18. sound 2500,80
      19. u1$="thisisatest":u2$="testing123testing"
      20. print "\n\n Langes Testbeispiel 3 (11 x 16), ca. 2 min :"
      21. tm&=&GetTickCount
      22. PRINT "\n Ergebnis: ";FNlcs(u1$,u2$)'
      23. tm&=&GetTickCount-tm&
      24. print "\n Gefunden in ";tm&\1000;" s"
      25. sound 2000,200
      26. waitinput
      27. END
      28. proc fnlcs :parameters a$,b$
      29. case (a$="") or (b$=""):return ""
      30. case right$(a$,1)=right$(b$,1):return \
      31. fnlcs(mid$(a$,1,len(a$)-1), mid$(b$,1,len(b$)-1))+right$(a$,1)
      32. declare x$,y$,tmp$
      33. x$=fnlcs( a$ , mid$(b$,1,len(b$)-1) )
      34. y$=fnlcs( mid$(a$,1,len(a$)-1) , b$ )
      35. if len(y$)>len(x$):tmp$=x$:x$=y$:y$=tmp$:endif
      36. return x$
      37. endproc
      Alles anzeigen

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von p. specht ()