ALGORITHMEN TEIL XII: Cogito errare est

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

    Wir verlosen 4 x das Buch Windows 10 - Schritt für Schritt erklärt Schau gleich mal rein!

    • Lösung zu Nr. 50
      -------------------
      Das war natürlich eine Scherzfrage. Drei Jahre später sind alle drei jeweils drei Jahre älter, zusammen also 9 Jahre älter als damals 31, somit gemeinsam 40 Jahre alt.

      Lösung zu Nr. 51 "Medikation"
      ---------------------------------
      Die 1. Tablette nimmt er um 11:05 ein,die 2. nimmt um 11:20 ein,die 3. nimmt er um 11:35 ein und die (gesuchte) 4. Tablette somit um 11:50 Uhr. Anders ausgedrückt: Mit dt=15 Zeiteinheiten (hier: Minuten) nimmt man die N.te Tablette um t*(N-1) Zeiteinheiten später ein. Somit:
      11:05 + 15 min*(4.-1)= 11:00 + 5 + 15*3 = 11:00 + 5 + 45 = 11:50 Uhr.

      Lösung zu Nr. 52 "Einer-Teilbar"
      ------------------------------------
      20:0=+Inf ... Nein
      21:1=21 ... Ja
      22:2 = 11 ... Ja
      23:3 ... Nein
      24:4 = 6 ... Ja
      25:5 = 5 ... Ja
      26:6 ... Nein
      27:7 ... Nein
      28:8 ... Nein
      29:9 ... Nein
      30:0 ... +Inf ... Nein
      ------------------------
      Antwort: 4 mal Ja!

      Und zwischen 1 und 99: Siehe Programm!

      Quellcode

      1. WindowTitle "Rätsel 52 Teil 2"
      2. cls:declare W&, z&, e&, c&
      3. font 2:Print "\n Geprüft wird der Bereich von 1 bis 99:\n":font 0
      4. whileloop 0,9:z&=&Loop
      5. whileloop 1,9:e&=&Loop
      6. w&=z&*10+e&
      7. if e&<>0
      8. ifnot w& mod e&
      9. print " ";w&;"/";e&;"=";int(w&/e&)," ",:inc c&
      10. case %pos>40:print
      11. endif
      12. endif
      13. endwhile
      14. endwhile
      15. font 2:print "\n\n Zusammen sind ";c&;" Zahlen durch ihre Einerstelle teilbar!"
      16. waitinput
      Alles anzeigen
      Lösung zu Nr. 53 "Eineinhalb Hühner"
      ------------------------------------------
      Eineinhalb Hühner legen in eineinhalb Tagen eineinhalb Eier.
      Drei Hühner legen in eineinhalb Tagen drei Eier.
      Drei Hühner legen in drei Tagen sechs Eier.
      Ein Huhn legt in drei Tagen somit zwei Eier.
      Ein Huhn legt also pro Tag 2/3 Eier, das sind 0.6666666periodisch.

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

    • Lösung zu Nr. 55: "Vier Karten"
      ====================
      Man kann eine These nicht "beweisen", man kann sie nur ehrlich versuchen zu widerlegen. Solange man nichts Gegenteiliges erkennt, bleibt sie vorläufig gültig. Um die These "Wenn eine Karte ein D vorne hat, hat sie hinten die Zahl 3 " zu widerlegen, muß man

      [D] umdrehen: Ist dort NICHT 3, ist die These widerlegt. Ferner muß man die Karte mit der
      [7] umdrehen: Zeigt sie hinten "D", ist die These ebenfalls wiederlegt.

      Die Karte [F] hat mit unserer These nichts zu tun, ist daher irrelevant. Und wenn man [3] umdreht, und dort ist kein [D], ist die These auch nicht widerlegt, weil sie ja nicht ausschließt, daß [3] auch bei anderen Buchstaben auftaucht. Vertrackte Sache das, was?
    • Abt. Rätselecke Nr. 56: "Sonnwendfest"
      =========================
      Sonnwendfeste sind uraltes Brauchtum. 40 Burschen und 28 Mädchen fassen sich an den Händen und bilden um das Sonnwendfeuer einen großen Kreis. Genau 18 Burschen geben ihre rechte Hand einem Mädchen. Wie viele Burschen geben die linke Hand einem Mädchen?
      Spoiler anzeigen

      17 + 1 = Auch 18 !
      B B B B B B B B B B B B B B B B B B_________________B B B B B B B B B B B (B)
      _M M M M M M M M M M M M M M M MMMMMMMMMMMMM B B B B B B B B B B B

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

    • Abt. Trunkierbare Primzahlen
      ==================
      sind Primzahlen, die man an einem Ende zifferenweise abschneiden kann, und es bleibt immer noch eine Primzahl über.

      Obwohle es unendlich viele Primzahlen gibt, existieren im Dezimalsystem z.B. genau 83 rechts-trunkierbare Primzahlen. Wird jeweils die Einerstelle abgeschnitten und das ganze nach rechts gerückt, handelt es sich dann neuerlich um eine Primzahl.

      Links-trunkierbar sind Primzahlen, in denen an keiner Stelle die Ziffer Null steht und bei denen das Weglassen einer beliebigen Anzahl führender Stellen wieder zu einer Primzahl führt. Im Dezimalsystem existieren genau 4260 linkstrunkierbare Primzahlen.

      Es gibt aber auch beidseitig trunkierbare Primzahlen: Im Dezimalsystem sind laut Matheforum 2, 3, 5, 7, 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797 und 739397 die einzigen sowohl links- als auch rechtstrunkierbaren Primzahlen.

      Gruss

      P.S.: Die größte linkstrunkierbare Primzahl ist 357.686.312.646.216.567.629.137
      Wer alle anderen auch kennenlernen will, ist mit dieser Internetseite gut bedient!

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

    • Das war bei Primzahlen immer die Frage, Michael! Vielleicht klappts ja damit wieder in der Cryptographie? Im Moment ist es nur Zahlenspielerei...

      Abt. BinSearch im Zahlenfeld
      ==================
      ... und zwar mit GOTO, weil WHILE bei mir (v 11.2a) nicht mit (Z&>a&) AND (Z&<b&) zurechtkommt, sondern anmeckert, daß Variable Z& nicht deklariert sei. Egal, jetzt klappt der BinSearch endlich mit Zahlen!
      Gruss

      Quellcode

      1. Cls
      2. declare da$,a$[],Su$,su&, L&,R&,Z&
      3. da$="1,2,5,88,99,100,101,233,333"
      4. zeig:
      5. print " Geordnete Liste: ";da$
      6. a$[]=explode(da$,",")
      7. Nochmal:
      8. Su$="":print "\n Eingabe: ";
      9. Input Su$:if su$="":cls:goto "zeig":endif
      10. su&=val(su$)
      11. BinSuche:
      12. L&=0:R&=sizeof(a$[])-1
      13. Lup:
      14. if L&>R&:print " Sorry ...":goto "Nochmal":endif
      15. Z&=(R&+L&)/2
      16. print l&,z&,r&
      17. if su&<val(a$[z&]):R&=Z&-1:goto "Lup":endif
      18. if su&>val(a$[z&]):L&=Z&+1:goto "Lup":endif
      19. print " Gefunden an Pos: ";z&;": ";su$;" = ";a$[z&]
      20. goto "Nochmal"
      Alles anzeigen
    • Bin eigentlich nur an den Algorithmen interessiert, Heinz, und das rein als Hobby. Ob die bisher aus TurboPascal, Fortran-77, gwBasic etc. übertragenen Programme auch reibungslos unter X3 funktionieren, kann ich nur hoffen.
      Ginge es mir rein ums Laufen-lassen, könnte ich mir Fortran-Compiler holen, Delphi oder VisualBasic. Aber ich versuche die Algorithmen zu verstehen, und das geht am besten durch "zu Fuß programmieren". Daß es elegantere Programmierstile gibt, z.B. ohne GOTO, ist mir auch klar. Aber mit XProfan-11 habe ich damals begonnen, und es verhält sich wie mit einem alten VW-Käfer: Läuft und läuft und läuft...
      Gruss
    • Bei mir im Schnitt so 2.5 bis 3 Sekunden.

      Ist nur schade, daß der MAT - Befehl &index nicht unterstützt.
      Dann wären die Sekunden bzw. Millisekunden nicht mehr
      messbar.

      Hatte schon vor Tagen darüber nachgedacht, wie man den
      MAT-Befehl überlisten könnte, daß der das gleiche macht,
      wie &index.

      Wenn man oben z.B.

      Quellcode

      1. Mat a[] = 1000
      schreibt, ist es nicht mehr messbar. Da wird ja auch jedes Array - Element auf 1000 gesetzt,
      bzw. man könnte auch multiplizieren usw.

      p.specht : Hättest du eine Idee ?
      Käme drauf an, was XProfan als <Ausdruck> annimmt.
    • H.Brill schrieb:

      Bei mir im Schnitt so 2.5 bis 3 Sekunden.

      Ist nur schade, daß der MAT - Befehl &index nicht unterstützt.
      Dann wären die Sekunden bzw. Millisekunden nicht mehr
      messbar.
      Der MAT-Befehl ist so schnell, weil er den Index eben nicht benutzt. Der Wert, der zugewiesen wird, wird eben nur einmal errechnet und dann allen Elementen zugewiesen. Würde &Index unterstützt werden, müsste der Wert eben für jedes Element neu errechnet werden.

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


      http://www.xprofan.de
    • Heinz, da fällt mir als Zwischenlösung nur der XPSE ein:
      50 Mio Elemente mit Index laden in 777 ms, unsere 200.000 in 3 ms ...
      Gruss

      P.S.: Die For-Schleife in der nProc ist hier interessanterweise schneller als XPSE-whileloop !

      Quellcode

      1. {$cleq}
      2. Cls
      3. var n&=50000000:print n&;" Elemente"
      4. dec n&:Declare A&[n&],ok&,tm&
      5. a&[0]=1
      6. tm&=&gettickcount
      7. ok& = Index0(addr(A&[0]),sizeof(A&[]))
      8. tm&=&gettickcount-tm&
      9. print tm&;"ms ",ok&,a&[sizeof(a&[])-2]
      10. waitinput
      11. end
      12. nProc Index0
      13. parameters base&,size&
      14. declare i&
      15. for i&=0 to size&-1 do begin
      16. long base&,4*i& = i&
      17. end
      18. return size&-1
      19. EndProc
      20. 'nProc Index0
      21. 'parameters base&,size&
      22. 'whileloop 0,size&-1
      23. ' long base&,4*&Loop = &Loop
      24. 'endwhile
      25. 'return size&-1
      26. 'EndProc
      Alles anzeigen

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

    • RGH schrieb:

      H.Brill schrieb:

      Bei mir im Schnitt so 2.5 bis 3 Sekunden.

      Ist nur schade, daß der MAT - Befehl &index nicht unterstützt.
      Dann wären die Sekunden bzw. Millisekunden nicht mehr
      messbar.
      Der MAT-Befehl ist so schnell, weil er den Index eben nicht benutzt. Der Wert, der zugewiesen wird, wird eben nur einmal errechnet und dann allen Elementen zugewiesen. Würde &Index unterstützt werden, müsste der Wert eben für jedes Element neu errechnet werden.
      Gruß
      Roland
      Stimmt so nicht ganz. Wo ich hinaus wollte :

      Quellcode

      1. Declare a&[5]
      2. Cls
      3. a&[0] = 1
      4. a&[1] = 2
      5. a&[2] = 3
      6. a&[3] = 4
      7. a&[4] = 5
      8. Mat a&[] * 10
      9. WhileLoop 0, 4
      10. Print a&[&LOOP]
      11. EndWhile
      12. Waitkey
      13. End
      Alles anzeigen
      Wenn ein Array aber schon vorbelegt ist, so wird aber wohl bei jedem Element gerechnet.
      Bei meinem Code kommt jedenfalls immer der 10fache Wert jedes Elementes raus.
      So macht es ja auch Sinn mit den 4 Rechenoptionen.

      Von daher wollte ich was, das die Elemente vorbelegen kann, z.B. duch Enumeration etc.
      Das muß ja nicht unbedingt &index sein.
      Wie gesagt, obiges geht aber nur, wenn die Elemente schon vorbelegt sind.

      Vielleicht ist mein Anliegen jetzt verständlicher.
    • Hm, mit "a&[] = &index" würdest Du es doch vorbelegen. Das ändert natürlich nichts daran, dass dise Zeile länger dauert, als das nachfolgende "MAT a&[] * 10".
      Und das ist eben so schnell, weil der Ausdruck, mit dem multipliziert wird, nur einmal gelesen und berechnet wird. Dessen Wert dann in einer Schleife mit jedem Arraywert zu multiplizieren, geht dann rasend schnell.

      Relativ zeitaufwendig ist das Parsen (Lesen) und Auswerten eines Ausdrucks, da der Ausdruck ja nahezu beliebig kompliziert sein könnte. Da dieser bei MAT keine variablen Elemente enthält, geschieht das dort nur einmal. Bei "a&[] = &index" wird halt für jedes Array-Element der Ausdruck hinter dem "=" geparst und ausgewertet, den auch dieser könnte ja nahezu beliebg komplex sein.

      Die Routine in XProfan, mit der ich einen Ausdruck aus dem Quelltext (Interpreter) bzw. Bytecode (Runtime) lese ist nun mal sehr komplex und aufwendig. Sie ist quasi das Herz-Stück des Parsers.

      Eine Lösung zur Beschleunigung der Vorbelegung könnte höchstens ein eigener Befehl oder eine eigene Syntax sein, die ein numerisches Array mit dem Element-Index * n belegt, etwa "ENUM A&[], n" oder "MAT A&[] # n" oder wie auch immer.

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


      http://www.xprofan.de
    • ja genau,
      sowas meinte ich :
      eine beschleunigte Vorbelegung eines num. Arrays, weil
      a&[] = &index
      viel zu langsam ist.

      MAT A&[] # n

      würde mir da gefallen. Wobei n die Schrittweite wäre :
      n = 1 --> A&[0] =1, A&[1] = 2, A&[2] = 3 usw.
      n = 10 -->A&[0] = 10, A&[1] = 20, A&[2] = 30 usw.

      PS:
      Der MAT - Befehl rechnet ja auch mit jedem Arrayelement
      und ist sauschnell.
      MAT A&[] + 10 z.B. zählt zu jedem Element 10 dazu.
      Roland, da könntest du doch auch leicht eine Enumeration
      bzw. STEP (wie bei WhileLoop der 3. Parameter) hin bekommen.

      Teilbereiche von Arrays wären bei den MAT - Befehlen auch
      eine Überlegung wert. Daß man z.B nur vom 10.ten bis 20.ten
      Arrayelement ein Array mit dem MAT-Befehl bearbeiten kann,
      wenn optional Startpunkt (10) und Endpunkt (20) eingegeben
      werden. z.B.
      MAT A&[] + 10, 10, 20
      würde dann nicht das ganze Array bearbeiten, sondern nur
      die Elemente ab 10 bis 20 (A&[9]...A&[19])

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von H.Brill ()

    • Gute Anregung, Heinz!

      Abt. Rätselecke Nr. 57
      ==============
      Aus den Ziffern 1 bis 5 als Elemente werden Zahlen gebildet, wobei jede Ziffer in jeder Zahl genau einmal verwendet werden soll ("Permuation"). Wie viele dieser Zahlen haben dann die folgende Eigenschaft (bzw: Kann es so eine Zahl überhaupt geben?)

      Die erste Ziffer (von links) dieser Zahl ist durch 1 teibar, und
      die ersten 2 Ziffern dieser Zahl bilden eine durch 2 teilbare Zahl, und
      die ersten 3 Zifferm bilden eine durch 3 teilbare Zahl, und
      die ersten 4 Ziffern bilden eine durch 4 teilbare Zahl, und
      alle 5 Ziffern bilden eine durch 5 teilbare Zahl ?

      "Lösung im Spoiler"
      Spoiler anzeigen

      cls
      declare a$,b$,c$,d$,e$, n&
      whileloop 5:a$=&Loop
      whileloop 5:b$=&Loop:case b$=a$:continue
      whileloop 5:c$=&Loop:case (c$=b$) or (c$=a$):continue
      whileloop 5:d$=&Loop:case (d$=c$) or (d$=b$) or (d$=a$):continue
      whileloop 5:e$=&Loop:case (e$=d$) or (e$=c$) or (e$=b$) or (e$=a$):continue
      print " Testzahl: ";a$+b$+c$+d$+e$,": ";
      ifnot val(a$+b$) mod 2
      ifnot val(a$+b$+c$) mod 3
      ifnot val(a$+b$+c$+d$) mod 4
      ifnot val(a$+b$+c$+d$+e$) mod 5
      inc n&:sound 200,100
      print "Treffer Nr."+str$(n&)+": "+a$+b$+c$+d$+e$,
      else :print "scheitert an (5)";:endif
      else :print "scheitert an (4)";:endif
      else :print "scheitert an (3)";:endif
      else :print "scheitert an (2)";:endif
      print:endwhile:endwhile:endwhile:endwhile:endwhile:print "---"
      waitinput

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

    • Ja, wenn man da so rum programmiert, kommen einem
      da schon so einige Ideen. Ich habe hier mal kurz was
      zusammen geschrieben, was vielleicht auch noch
      interessant zum Einbau in XProfan sein könnte.

      Spoiler anzeigen

      ' MAT VAR1[] > x VAR2[]
      ' verschiebt alle Zahlen größer x in VAR2[]
      ' Wunsch für relationale Operatoren (>, >=, <, >=, <>)
      ' beide Arrays müssen gleich groß sein.

      ' vielleicht noch eine Systemvariable &MAT, die die Anzahl der
      ' Verschiebungen anzeigt. Damit hätte man dann die Anzahl der
      ' belegten Array-Elemente. Wenn man dann noch ein
      ' Move("ArrToList", A[], optionaleAnzahl) hätte, wäre das auch
      ' praktisch.

      ' MAT VAR1[] # ",", "|"
      ' ersetzt in allen Elementen , durch |


      Jetzt muß ich aufhören, zu denken. Sonst fällt mir noch
      mehr ein. :-)
    • Hab gerade versucht, nicht zu denken. Klappt nicht, endete in "Blödsinn denken".
      Also wie immer *LOL*


      Abt. Rätselecke Nr. 58: "Vier von sieben Kätzchen"
      ================================
      Geg: Eine Katze hat 7 Babykätzchen mit den Farben weiß, schwarz, rot,
      weiß-schwarz, weiß-rot, schwarz-rot und weiß-schwarz-rot im Fell.

      Ges: Auf wie viele Arten kann man vier der sieben Kätzchen so auswählen,
      dass jeweils zwei von ihnen genau eine Farbe gemeinsam haben?

      Gruss

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

    • Lösung zu Nr. 58
      ===========
      Spoiler anzeigen

      Quellcode

      1. WindowTitle "Rätsel 58: Vier von sieben Kätzchen"
      2. ' Eine Katze hat 7 Babykätzchen mit den Farben weiß, schwarz, rot,
      3. ' weiß-schwarz, weiß-rot, schwarz-rot und weiß-schwarz-rot im Fell.
      4. ' Auf wie viele Arten kann man vier Kätzchen so auswählen, dass
      5. ' jeweils zwei von ihnen genau eine Farbe gemeinsam haben?
      6. WindowStyle 24:cls:font 2
      7. var n&=7:var q&=4: declare i&,j&,k&,l& ,m&,o&,p&, r&,s&,t&,u&,v&,w&
      8. Whileloop 1,n&-q&+1:i&=&Loop
      9. Whileloop 2,n&-q&+2:j&=&Loop:case j&<=i&:continue
      10. Whileloop 3,n&-q&+3:k&=&Loop:case (k&<=j&) or (k&<=i&):continue
      11. Whileloop 4,n&-q&+4:l&=&Loop:case (l&<=k&) or (l&<=j&) or (k&<=i&):continue
      12. r&=0:whileloop 0,2:case (testbit(i&,&Loop)>0) and (testbit(j&,&Loop)>0):inc r&:endwhile
      13. s&=0:whileloop 0,2:case (testbit(i&,&Loop)>0) and (testbit(k&,&Loop)>0):inc s&:endwhile
      14. t&=0:whileloop 0,2:case (testbit(i&,&Loop)>0) and (testbit(l&,&Loop)>0):inc t&:endwhile
      15. u&=0:whileloop 0,2:case (testbit(j&,&Loop)>0) and (testbit(k&,&Loop)>0):inc u&:endwhile
      16. v&=0:whileloop 0,2:case (testbit(j&,&Loop)>0) and (testbit(l&,&Loop)>0):inc v&:endwhile
      17. w&=0:whileloop 0,2:case (testbit(k&,&Loop)>0) and (testbit(l&,&Loop)>0):inc w&:endwhile
      18. if r&+s&+t&+u&+v&+w&=4
      19. print "\n Untersuche Kombination ";i&,j&,k&,l&
      20. inc m& :print " wsr wsr wsr wsr"
      21. print " ";m&;": ";right$("00"+bin$(i&),3),right$("00"+bin$(j&),3),\
      22. right$("00"+bin$(k&),3),right$("00"+bin$(l&),3)
      23. endif
      24. endwhile
      25. endwhile
      26. endwhile
      27. endwhile
      28. print "\n\n *** LÖSUNG: Es gibt genau ";m&;" Möglichkeiten ***"
      29. beep:waitinput:end
      Alles anzeigen