ALGORITHMEN - Teil XXV: Das Fleisch ist willig, aber der Geist ist schwach...

    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.

    • Lösung zu FGS-08
      --------------------
      Spoiler anzeigen

      Die 1. Ableitung, also der Anstieg, der Funktion y = f(x) = 3,14159... * x
      ergibt sich aus der Überlegung, dass das "nackte" x in Bezug auf eine kleine Änderung von x (- man nennt das dx) stets den Antieg 1 - die 45°-Gerade - produziert. Ein beliebiger Vorfaktor - hier 3,14159..., multipliziert mit Anstieg 1, ergibt immer genau diesen Faktor als Anstieg. Mit anderen Worten: Ein Faktor der Variable, nach der abgeleitet wird (hier: x), bleibt ohne x einfach stehen. Die 1. Ableitung der Funktion f(x) = 3,14159... * x ist also 3,14159...
    • Und wieder hat Rätselrabe ravenheart vollkommen recht! Allerdings hätten manche Rätselfreunde doch gern gewusst, welche konkrete ganze Zahl da gemeint sein könnte. Mein Computer weiss es:

      Quellcode

      1. Windowtitle "FGS-09 Solver":WindowStyle 24
      2. Randomize:cls rnd(2^24):font 2:declare z!,za&,n&
      3. Whileloop 100,999:z!=&Loop+sqrt(&Loop)
      4. :if z!=int(z!):za&=z!:n&=&Loop:endif
      5. endwhile:print "\n Die gesuchte Zahl ist ";
      6. print za&;", denn:\n":print " ";za&;" = ";\
      7. Sqrt(n&)\1,"*",Sqrt(n&)\1,"+",Sqrt(n&)\1:waitkey
    • Lösung zu FGS-10
      -----------------
      Spoiler anzeigen

      Welche Funktion dy/dx = d(f(x))/dx = f´(x) gibt den Anstieg von y = f(x) = 3 * x + 5 korrekt wieder?
      Im Lichte des in vorigen Rätsellösungen bekannt gewordenen können wir ...
      1. den "nackten" Summanden 5 einfach vergessen,
      2. Aus x wird 1, weshalb ...
      3. der Vorfaktor 3 stehen bleibt.

      Die Funktion, die den Anstieg von y = 3*x+5 korrekt wiedergibt, lautet
      dy/dx = f´(x) = 3 * 1 + 0 = 3
      Mit anderen Worten: Die Steigung der Funktion 3*x+5 ist überall gleich groß, nämllich 3.

      P.S.: Sind die Achsen des Funktionsdiagramms y über x mit gleichem Maßstab versehen, kann man diesen Wert 3 in einen Winkel umrechnen: tan(alpha) = 3 ==> alpha = arcTan(3) = 1.249045 rad = 1.249045 / Pi() * 180° = +71,656 °.
      Meist belässt man es aber beim tangens_alpha, also beim Vorfaktor (hier 3).
    • Lösung zu FGS-11
      ------------------
      Spoiler anzeigen

      Antwort: 2 und 17, denn:
      Alle Primzahlen ausser 2 sind ungerade. Ungerade Zahlen zur vierten Potenz (= 2 x quadrieren) plus 1 erheben führt immer auf eine gerade Zahl, kann also keine Primzahl sein, weil ja restlos durch 2 dividierbar. Nur die einzige gerade Primzahl, 2, hoch 4 + 1 = 2*2*2*2+1 = 16+1 = 17 erfüllt diese Bedingung.
    • Lösungsversuch zu FGS-12
      --------------------------
      Spoiler anzeigen
      Im Bereich herkömmlicherm reeller Zahlen ist eine Lösung für x, y, z ALLE positive Ganzzahlen nicht möglich. Mindestens ein Faktor muss kleiner als 1 sein. Wären x, y, z allerdings komplexe Zahlen, gäbe es unendlich viele Lösungen, also keine konkrete Nummer als Ergebnis - die ist aber gefragt.

      Lässt man die Forderung "x, y, z alle Ganzzahlen" fallen, ergibt sich folgender Lösungsweg:
      1. Gleichung: x^² * y * z^³ = 7^³
      mal
      2. Gleichung: x * y^² = 7^9
      ergibt
      x^² * y * z^³ * x * y^² = 7^³ * 7^9
      bzw.
      x^2 * x * y * y^² * z^³ = 7^(3+9),

      etwas schöner

      x^3 * y^3 * z^3 = 7^12

      oder auch

      (x*y*z)^3 = 7^12 ,

      was bedeutet

      x*y*z = 7^(12/3) = 7^4,

      und daher ist das gefragte

      x*y*z / 7 = 7^4 / 7 = 7^3 = 7*7*7 = 49 * 7 = 343

      Somit lautet die Antwort: 343 :8O:

      Da offenbar
      x*y*z = 7^4 = 2401 sein muss, was aber nur der Fall ist für folgende
      (x y z)-Tupel:
      1 * 1 * 2401
      1 * 7 * 343
      1 * 49 * 49
      1 * 343 * 7
      1 * 2401 * 1
      7 * 1 * 343
      7 * 7 * 49
      7 * 49 * 7
      7 * 343 * 1
      49 * 1 * 49
      49 * 7 * 7
      343 * 1 * 7
      343 * 7 * 1
      2401 * 1 * 1 ,
      wovon aber keiines Gleichung 1 und Gleichung 2 erfüllt,
      ist eiine Lösung im Ganzzahlbereich bei dieser Konstellation nicht möglich.
      Sorry! Wieder eiin Übersetzungsfehler aus dem Russischen?? :cursing:
    • Lösung zu FGS-13
      -----------------
      Spoiler anzeigen
      Enumerative Lösung

      Die folgenden dreistelligen Zahlen haben die Quersumme 5:
      104, 113, 122, 131, 140;
      203. 212. 221, 230;
      302, 311, 320;
      401, 410;
      500.

      Antwort: Es gibt insgesamt 15 verschiedene dreistellige positive Ganzzahlen mit Quersumme 5.

      P.S.: Dabei treten an der 1. Stelle
      5 x "1"
      4 x "2"
      3 x "3"
      2 x "4" und
      1 x "5" auf.

      5+4+3+2+1 = 15 ... passt!
    • Lösungsprogramm für FGS-14
      ----------------------------

      Quellcode

      1. WindowTitle "Auswertung für 4 Stellen mit Quersumme 5"
      2. cls:font 2
      3. declare s&, t&,h&,z&,e&, n&,p&
      4. declare ct&[4,9]
      5. whileloop 1,9:t&=&Loop
      6. whileloop 0,9:h&=&Loop
      7. whileloop 0,9:z&=&Loop
      8. whileloop 0,9:e&=&Loop
      9. s&=t&+h&+z&+e&
      10. if s&=5
      11. inc n&
      12. print " ";n&;".:",t&;h&;z&;e&,
      13. case %pos>50:print
      14. ct&[4,t&]=ct&[4,t&]+1
      15. ct&[3,h&]=ct&[3,h&]+1
      16. ct&[2,z&]=ct&[2,z&]+1
      17. ct&[1,e&]=ct&[1,e&]+1
      18. elseif s&>5
      19. break
      20. endif
      21. Endwhile
      22. Endwhile
      23. Endwhile
      24. Endwhile
      25. print "---"
      26. waitinput 2000
      27. print "Zeichenhäufigkeit pro Stelle:"
      28. Whileloop 4,1,-1:p&=&Loop
      29. print p&;".Stelle: ";
      30. whileloop 0,9
      31. case ct&[p&,&Loop]:print &Loop;":";ct&[p&,&Loop];"x",
      32. endwhile
      33. print
      34. endwhile
      35. print "---"
      36. waitinput
      37. End
      Alles anzeigen
      Mit anderen Worten: Es gibt 35 verschiedene vierstellige Zahlen mit Quersumme 5.

      In der Tausenderstelle gibt es |{1,..,5}|=5 verschiedene Ziffern, in allen weiteren Stellen könnten im Prinzip |{0,..,5}| = 6 verschiedene Ziffern stehen. Eines ist klar: Die Summe der Häufigkeiten dieser Ziffern entspricht der Gesamtzahl aller verschiedenen 4-stelligen Ganzzahlen mit Quersumme 5. An Häufigkeiten gibt es im Einzelnen

      "1": 15 mal, "2": 10 mal, "3": 6 mal, "4": 3 mal, "5": 1 mal.
      15+10+6+3+1 = 35 , q.e.d.

      Eine Formel für die Häufigkeit der Ziffer an der 1. Stelle von links wäre
      z = 6-n, Häufigkeit(z) = n*(n+1)/2

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

    • Abt. FGS-15
      =========
      Wieviele 10-stellige positive Ganzzahlen des Dezimalsystems mit Quersumme 7 gibt es?

      P.S.: Anbei ein kleiner Generator mit Stellenstatistik dazu

      Brainfuck-Quellcode

      1. WindowTitle "FGS-15: 10 Stellen mit Quersumme Q<9"
      2. Cls:font 2
      3. declare s&, mrd&,hm&,zm&,mio&,ht&,zt&,t&,h&,z&,e&, n&,p&,L&
      4. declare ct&[11,9]
      5. WHILELOOP 7,9:L&=&LOOP' maximal 9 (wg. Beschleunigungsverfahren)
      6. WindowTitle "Generator für 10-stellige pos.Ganzzahlen mit Quersumme "+str$(L&)
      7. CLS:n&=0:clear ct&[]
      8. whileloop 1,L&:mrd&=&Loop
      9. whileloop 0,L&-mrd&:hm&=&Loop
      10. whileloop 0,L&-mrd&-hm&:zm&=&Loop
      11. whileloop 0,L&-mrd&-hm&-zm&:mio&=&Loop
      12. whileloop 0,L&-mrd&-hm&-zm&-mio&:ht&=&Loop
      13. whileloop 0,L&-mrd&-hm&-zm&-mio&-ht&:zt&=&Loop
      14. whileloop 0,L&-mrd&-hm&-zm&-mio&-ht&-zt&:t&=&Loop
      15. whileloop 0,L&-mrd&-hm&-zm&-mio&-ht&-zt&-t&:h&=&Loop
      16. whileloop 0,L&-mrd&-hm&-zm&-mio&-ht&-zt&-t&-h&:z&=&Loop
      17. whileloop 0,L&-mrd&-hm&-zm&-mio&-ht&-zt&-t&-h&-z&:e&=&Loop
      18. 'für <10stellig von innen nach aussen auskommentieren, auch das entspr. EndWhile!
      19. s&=mrd&+hm&+zm&+mio&+ht&+zt&+t&+h&+z&+e&
      20. if s&=L&
      21. inc n&
      22. print " ";n&;".:",mrd&;hm&;zm&;mio&;ht&;zt&;t&;h&;z&;e&,
      23. case %pos>55:print
      24. ct&[10,mrd&]=ct&[10,mrd&]+1
      25. ct&[9,hm&]=ct&[9,hm&]+1
      26. ct&[8,zm&]=ct&[8,zm&]+1
      27. ct&[7,mio&]=ct&[7,mio&]+1
      28. ct&[6,ht&]=ct&[6,ht&]+1
      29. ct&[5,zt&]=ct&[5,zt&]+1
      30. ct&[4,t&]=ct&[4,t&]+1
      31. ct&[3,h&]=ct&[3,h&]+1
      32. ct&[2,z&]=ct&[2,z&]+1
      33. ct&[1,e&]=ct&[1,e&]+1
      34. endif
      35. Endwhile
      36. Endwhile
      37. Endwhile
      38. Endwhile
      39. Endwhile
      40. Endwhile
      41. Endwhile
      42. Endwhile
      43. Endwhile
      44. Endwhile
      45. sound 1000,50
      46. print " !!!"
      47. WAITINPUT
      48. haeuf
      49. ENDWHILE
      50. End
      51. proc haeuf
      52. print "--------------------------------------------------"
      53. print "Zeichenhäufigkeit pro Stelle für diese",n&,"Zahlen:"
      54. Whileloop 10,1,-1:p&=&Loop:print p&;".Stelle: ";
      55. whileloop 0,9
      56. case ct&[p&,&Loop]:print ct&[p&,&Loop];"x´";&Loop;",",
      57. endwhile
      58. print
      59. endwhile
      60. print "--------------------------------------------------"
      61. waitinput
      62. endproc
      Alles anzeigen

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

    • Spoiler anzeigen
      Ergebnistabelle, ermittelt mit obigem Generator:

      Quersumme:
      Stellenzahl
      12345678910*11*
      1
      1
      1
      1
      1
      1
      1
      1
      1
      1
      0*
      0*
      2
      1
      2
      3
      4
      5
      6
      7
      8
      9
      9*
      8*
      3
      1
      3
      6
      10
      15
      21
      28
      36
      45
      54
      61
      4
      1
      4
      10
      20
      35
      56
      84
      120
      165
      219
      279
      5
      1
      5
      15
      35
      70
      126
      210
      330
      495
      714
      992
      6
      1
      6
      21
      56
      126
      252
      462
      792
      1287
      2001
      2992
      7
      1
      7
      28
      84
      210
      462
      924
      1716
      3003
      5004
      7995
      8
      1
      8
      36
      120
      330
      792
      1716
      3432
      6435
      11439
      19440
      9
      1
      9
      45
      165
      495
      1287
      3003
      6435
      12870
      24310
      43749
      10
      1
      10
      55
      220
      715
      2002
      5005
      11440
      24310
      ?
      ?
      11
      111?




      `*´: Da ab 10 der Zeichenvorrat 0-9 erschöpft ist, ist die Tabelle ab hier nicht mehr diagonalsymetrisch !

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

    • Abt. ROTATE RIGHT / ROTATE LEFT
      ===========================
      In XProfan gibt es zwar schnelle SHIFT-Befehle, für manche Algorithmen (etwa SHA256) benötigt man aber flotte Rotationen der bits von 32-bit-Variablen - und zwar solchen ohne Vorzeichen! Das nachstehende Progi testet solche Prozeduren auf Geschwindigkeit. Für File-Hashes wie SHA2 sind allerdings utraschnelle Maschinencode-Routinen erforderlich.
      Gruss

      Quellcode

      1. WindowTitle "RoR32 & RoL32"
      2. Window 0,0-%maxx,%maxy-41
      3. CLS:font 2:declare a&,b&,ld$, tm&
      4. ld$=mkstr$("0",31)
      5. Proc RoR32 :parameters a&,b&
      6. b&=(b& & 31) mod 32
      7. var m&=2^b&-1
      8. return ((a& & m&)<<(32-b&)) | ((a& & (2^32-1-m&))>>b&)
      9. EndProc
      10. Proc RoL32 :parameters a&,b&
      11. b&=(-b& & 31) mod 32
      12. var m&=2^b&-1
      13. return ((a& & m&)<<(32-b&)) | ((a& & (2^32-1-m&))>>b&)
      14. EndProc
      15. ' Hauptschleife
      16. a& = %10110011100011110000111110000000
      17. Whileloop -1024,1024 : b&=&Loop
      18. print " ";b&,tab(9);right$(ld$+bin$( RoL32(a&,b&) ),32),
      19. print tab(42);right$(ld$+bin$( RoR32(a&,b&) ),32),
      20. print tab(76);right$(ld$+bin$( RoR32(RoL32(a&,b&),b&)),32)
      21. endwhile
      22. 'Bench
      23. tm&=&Gettickcount
      24. Whileloop -1024,1024 : b&=&Loop
      25. ifnot a&=RoR32(RoL32(a&,b&),b&)
      26. sound 1000,200
      27. print " Matching error!"
      28. Waitinput
      29. endif
      30. endwhile
      31. tm&=&gettickcount-tm&
      32. print "\n--- 4194 Net Rotations done in",tm&,"ticks ---"
      33. sound 200,50
      34. waitinput
      35. END
      Alles anzeigen
    • Abt. ROTATE, aber flotter
      ===================
      Mein Routinenvergleich hat derzeit folgende Favoriten (~31 µs/Rotation)

      Quellcode

      1. Proc RoR32 :parameters a&,b&
      2. b&=b& & 31
      3. return (a&<<(32-b&)) | (a&>>b&)
      4. EndProc
      5. Proc RoL32 :parameters a&,b&
      6. b&= -b& & 31
      7. return (a&<<(32-b&)) | (a&>>b&)
      8. EndProc