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