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. Schwerstes Rätsel bisher - UnvmR 28 ´Zauberinsel´
      ==========================================
      In den Wäldern eines magischen Inselreichs gibt es drei Tierarten: Löwen, Wölfe und Ziegen.

      Wölfe können Ziegen fressen und Löwen können sowohl Wölfe als auch Ziegen fressen.

      Da es sich um ein magisches Inselreich handelt, verwandelt sich ...
      - ein Wolf, der eine Ziege frisst, in einen Löwen.
      - Ein Löwe, der eine Ziege frisst, verwandelt sich in einen Wolf und
      - ein Löwe, der einen Wolf frisst, verwandelt sich in eine Ziege.

      Zu Beginn befanden sich 17 Ziegen, 55 Wölfe und 6 Löwen auf der Insel.

      Nach einiger Zeit ist kein weiteres Fressen mehr möglich.
      Frage: Wie groß ist die minimale und die maximale Anzahl der Tiere,
      die sich dann noch auf der Insel befinden können?

      Q: Känguru´15
    • Abt. UnvmR 29 ´Mein Name ist Hase´
      ============================
      Der Hase hatte 20 Möhren (Norddeutsch: Mohrrüben, Gelbe Rüben, Ö: Karotten, CH: Rüebli). Jeden Tag frisst er 2 davon. Die 12. hat er an einem Mittwoch gefressen. Frage: An welchem Wochentag hat er mit dem Fressen der Möhren (Norddeutsch: Mohrrübe, Gelbe Rübe, Ö: Karotte, CH: Rüebli) begonnen?
    • Lösung zu UnvmR 28 ´Zauberinsel´
      ---------------------------------
      Mit simpler Simulation geht es nicht - man bekommt höchstens einen Eindruck für das Minumum an Tieren, die überbleiben können: 1. Das ist immerhin schon die halbe Aufgabe, aber betreffend Maximalzahl würde man hier praktisch ewig warten, weil die Wahrscheinlichkeit dafür gegen Null geht. Also erst mal der Fehlversuch:

      Quellcode

      1. WindowTitle "Populationsdynamik"
      2. cls:randomize:declare L&,W&,Z&,stand&,MAX&,Runde&,prt&,altmax&
      3. :proc WfZ :if W&>0:if Z&>0:dec W&:dec Z&:inc L&:prt&=1:endif:endif:endproc
      4. :proc LfZ :if L&>0:if Z&>0:dec L&:dec Z&:inc W&:prt&=1:endif:endif:endproc
      5. :proc LfW :if L&>0:if W&>0:dec L&:dec W&:inc Z&:prt&=1:endif:endif:endproc
      6. proc Hunger :parameters x&
      7. if x&=1:WfZ :elseif x&=2:LfZ :elseif x&=3:LfW :endif
      8. endproc
      9. Whileloop 100000:Runde&=&Loop
      10. L&=6:W&=55:Z&=17
      11. While W& and z& OR L& and W& OR L& and Z&
      12. prt&=0:Hunger(Rnd(3)+1)
      13. Stand&=L&+W&+Z&
      14. 'case prt&:print " ",L&,W&,z&,"",Stand&
      15. endwhile
      16. case Max&<Stand&:Max&=Stand&
      17. ::locate 1,1 ' oder statt dessen obige Zeile mit CASE
      18. if max&>altmax&:altmax&=max&:sound 500,60
      19. print "----- Runde ";Runde&;", Stand: ";Max&;" --------"
      20. endif
      21. endwhile
      22. print " Max= ";max&
      23. waitinput
      24. End
      Alles anzeigen

      Bleibt nur schärfste Logik, viele trickreiche Überlegungen und ein wenig Zahlentheorie. Wie ihr Euch denken könnt, ist diese Lösung also nicht von mir.
      Gruss

      Logische Lösung zur Maximalmenge der Tiere in UnvmR 28
      --------------------------------------------------------
      Spoiler anzeigen
      Nochmals kurz die Aufgabenstellung:
      In den Wäldern eines magischen Inselreichs gibt es drei Tierarten: Löwen, Wölfe und Ziegen.
      Wölfe können Ziegen fressen und Löwen können sowohl Wölfe als auch Ziegen fressen.
      Da es sich um ein magisches Inselreich handelt, verwandelt sich ...
      - ein Wolf, der eine Ziege frisst, in einen Löwen.
      - Ein Löwe, der eine Ziege frisst, verwandelt sich in einen Wolf und
      - ein Löwe, der einen Wolf frisst, verwandelt sich in eine Ziege.
      Zu Beginn befanden sich 17 Ziegen, 55 Wölfe und 6 Löwen auf der Insel.
      Nach einiger Zeit ist kein weiteres Fressen mehr möglich. Wie groß ist
      die maximale Anzahl der Tiere, die sich dann noch auf der Insel befinden können?

      Überlegung I:
      Kein Fressen mehr ist dann erst möglich, wenn nur noch eine Tierart übrig bleibt!

      Wir hatten anfangs Löwen 6, Wölfe 55, Ziegen 17
      Schritt 1: 17 Wölfe fressen je eine Ziege und werden zu Löwen
      'Löwen 23, Wölfe 38, Ziegen 0
      Schritt 2: 19 Löwen fressen je einen Wolf und werden zu Ziegen
      Wir haben nun: Löwen 4, Wölfe 19, Ziegen 19
      Schritt 3: 19 Wölfe fressen je eine Ziege und werden zu Löwen
      'Löwen 23, Wölfe 0, Ziegen 0
      ----------------------------------------------------
      Überlegung II:
      Aber ist 23 auch wirklich die Maximalzahl?

      Zunächst wissen wir, dass es drei Arten von Fressvorgängen gibt und betrachten, wie sich
      diese auf die Gesamtpopulation auswirken:

      A: Löwe frisst Ziege und wird zu Wolf: (Löwen, Wölfe, Ziegen)= (-1,+1,-1)
      B: Wolf frisst Ziege und wird zu Löwe: (+1,-1,-1)
      C: Löwe frisst Wolf und wird zu Ziege: (-1,-1,+1)
      ----------------------------------------------------
      Überlegung III:
      Wir sehen also, dass die Geradzahligkeit/Ungeradzahligkeit der Differenz zweier Arten immer gleich bleibt!
      * Wenn die Differenz zwischen zwei Arten vor dem Fressen ungerade ist, so ist sie es auch danach.
      * Ist die Differenz dagegen vorher gerade, so bleibt sie gerade.
      ----------------------------------------------------
      Überlegung IV folgt aus I:
      Damit kein weiteres Fressen mehr möglich ist, müssen zwei Arten auf 0 reduziert werden.
      0 ist eine gerade Zahl!
      ----------------------------------------------------
      Überlegung V:
      Zu Beginn ist die Anzahl der Löwen gerade, die der Wölfe und Ziegen ungerade.
      'Nehmen wir an, die Löwen wären eine der beiden Arten, die auf 0 reduziert werden.

      Die Differenz zwischen Löwen und Wölfen ist am Anfang ungerade, und bleibt es somit auch während des gesamten Verlaufes.

      Das bedeutet: Falls es am Ende 0 Löwen gibt, muss es also eine ungerade Anzahl von Wölfen geben, also mehr als 0 Wölfe.
      ----------------------------------------------------
      Überlegung VI:
      Aber auch die Differenz zwischen Löwen und Ziegen ist ungerade, also müsste am Ende auch eine ungerade Anzahl von Ziegen existieren. Auch diese Zahl könnte, falls 0 Löwen existieren, nicht 0 sein.
      ----------------------------------------------------
      Überlegung VII:
      Es ist also nicht möglich, eine Situation zu erreichen, in der die Anzahl der Löwen und die Anzahl einer weiteren Tierart gleichzeitig 0 sind!
      ----------------------------------------------------
      Schlussfolgerung:
      Folglich müssen es die Löwen sein, die am Ende übrig bleiben.
      ----------------------------------------------------

      Überlegung VIII:
      Nehmen wir nun an, insgesamt wurde
      A mal die erste Art des Fressens durchgeführt,
      B mal die zweite, und
      C mal die dritte.

      Dann gilt für die Anzahl am Ende:
      Löwen = 6 – A + B – C
      Wölfe = 55 + A – B – C = 0
      Ziegen = 17 – A – B + C = 0

      Überlegung IX:
      Wir addieren die letzten beiden Zeilen und erhalten 72 – 2B = 0, also B = 36.
      Es muss - im gesamten Verlauf summiert - also genau 36 mal
      ein Wolf durch das Fressen von einer Ziege zu einem Löwen geworden sein.

      Würde das gleich am Anfang passieren, wäre der Populationsstand somit folgender:
      (Löwen, Wölfe, Ziegen) = Anfangs (6, 55, 17)
      36 Wölfe fressen je eine Ziege und werden zu Löwen:
      (42, 19, -19)

      Überlegung X:
      Da die Anzahl der Ziegen am Ende aber nicht negativ sein kann, müssen noch
      mindestens 19 Ziegen entstehen. Wie? Indem 19 Löwen je einen Wolf fressen:
      19 Löwen fressen je einen Wolf und werden zu Ziegen
      (23,0,0)
      Damit haben wir unseren Endstand erreicht und benötigen keine weiteren Fressvorgänge mehr.

      Schlussfolgerung und Antwort:
      Somit haben wir bewiesen, dass höchstens 23 Tiere überleben können.

      P.S. Dass es eine Reihenfolge gibt, mit der wir diese obere Grenze auch tatsächlich erreichen können,
      haben wir ja schon am Anfang dargelegt.
    • Das ist einfach. 1/4 des Eimers sind zwei Liter - die sind ja dazugekommen. Die vierfache Menge passt in den ganzen Eimer.
      Etwas komplexer gerechnet:
      1/2x + 2l = 3/4x
      2l = 3/4x - 1/2x
      2l = 3/4x - 2/4x
      2l = 1/4x
      x = 2l * 4
      x = 8l

      So was kann man natürlich auch sehr einfach mit dem Computer lösen:
      [Computerlösung auf Wunsch des Users gelöscht]
      ________________________________________________________

      PPFScanner PPFS Android MisterXMail@web.de
      Mfg AHT

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von AHT ()

    • Lösung zu UnvmR 30: Siehe vorigen Beitrag, @AHT hat korrekt gelöst.
      ----------------------
      Anmerkung: Quelle wie schon in Rätsel 28 angegeben. Text wurde dabei adaptiert / modernisiert, ausserdem habe ich keine Antwort-Alternativen angegeben, was die Sache deutlich interessanter macht. Weitere Quellen waren: Norwegische Mathe-Olympiade(n), Math contest (UK) übersetzt, und eine Auswahl aus der Wiki-Liste der Mathematical Competitions, Link hier.
      Gruss

      P.S.: Natürlich muss hier auch auf Textgebundenheit Rücksicht genommen werden. Geometrische Rätsel erfordern einen viel größeren Darstellungsaufwand.

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

    • ... wir nehmen da nur zwei Leute - das ist einfacher. Ist die Anzahl, in der sie die Positionen ändern, ungerade, ist immer derjenige vorne, der zuerst hinten war.
      Ist die Anzahl, in der sie die Positionen ändern,gerade, ist immer derjenige vorne, der zuerst vorne war.
      Am Sonntag ist also Sekundus vor Primus im Ziel (21), da neunmal die Position geändert. Tertitus ist dabei aber vor Primus angekommen (231), da elfmal die Position geändert. Den Rest kann man vernachlässigen, da sich bei zehnmaligen Positionswechsel die Endposition nicht ändert.

      Mit dem Computer gelöst: [Computerlösung auf Wunsch des Users gelöscht]
      ________________________________________________________

      PPFScanner PPFS Android MisterXMail@web.de
      Mfg AHT

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von AHT ()

    • Abt. UnvmR 31: ´Erdingers´
      ===================
      Maulwurf Jonas Erdinger gräbt 1 m Tunnel in 1,5 Stunden. Seine Partnerin Mizzi schafft in dieser Zeit 1/2 m.
      Die beiden wollen einen 9 m langen Tunnel graben - Wie lange müssen sie dafür arbeiten, bis sie sich beim Durchbruch treffen?

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

    • Bei der Zauberinsel kann die Brute-Force das mit dem Löwen zumindest bestätigen.

      Spoiler anzeigen

      Quellcode

      1. var int max_loop = 11
      2. Declare long L,Z,W, sammel[2,max_loop], int aktion,durchlauf
      3. Proc WZ_L // Wolf_frisst_Ziege
      4. aktion = 0
      5. ' Locate 1,1
      6. If (W > 0) and (Z > 0)
      7. Z = Z - 1
      8. W = W - 1
      9. L = L + 1
      10. aktion = 1
      11. Print "L:";L;",W:";W;",Z:";Z,1;" "
      12. EndIf
      13. ' CaseNot aktion : Print "L:";L;",W:";W;",Z:";Z,0;" "
      14. Return aktion
      15. EndProc
      16. Proc LZ_W // Loewe_frisst_Ziege
      17. aktion = 0
      18. ' Locate 1,1
      19. If (L > 0) and (Z > 0)
      20. Z = Z - 1
      21. L = L - 1
      22. W = W + 1
      23. aktion = 1
      24. Print "L:";L;",W:";W;",Z:";Z,1;" "
      25. EndIf
      26. ' CaseNot aktion : Print "L:";L;",W:";W;",Z:";Z,0;" "
      27. Return aktion
      28. EndProc
      29. Proc LW_Z // Loewe_frisst_Wolf
      30. aktion = 0
      31. ' Locate 1,1
      32. If (L > 0) and (W > 0)
      33. W = W - 1
      34. L = L - 1
      35. Z = Z + 1
      36. aktion = 1
      37. Print "L:";L;",W:";W;",Z:";Z,1;" "
      38. EndIf
      39. ' CaseNot aktion : Print "L:";L;",W:";W;",Z:";Z,0;" "
      40. Return aktion
      41. EndProc
      42. for durchlauf,0,max_loop
      43. Z = 17 : W = 55 : L = 6 : aktion = 0
      44. Repeat
      45. Select durchlauf
      46. CaseOf 0
      47. while WZ_L() : endwhile '1
      48. while LZ_W() : endwhile '2
      49. while LW_Z() : endwhile '3
      50. CaseOf 1
      51. while WZ_L() : endwhile '1
      52. while LW_Z() : endwhile '3
      53. while LZ_W() : endwhile '2
      54. CaseOf 2
      55. while LZ_W() : endwhile '2
      56. while WZ_L() : endwhile '1
      57. while LW_Z() : endwhile '3
      58. CaseOf 3
      59. while LZ_W() : endwhile '2
      60. while LW_Z() : endwhile '3
      61. while WZ_L() : endwhile '1
      62. CaseOf 4
      63. while LW_Z() : endwhile '3
      64. while WZ_L() : endwhile '1
      65. while LZ_W() : endwhile '2
      66. CaseOf 5
      67. while LW_Z() : endwhile '3
      68. while LZ_W() : endwhile '2
      69. while WZ_L() : endwhile '1
      70. CaseOf 6
      71. WZ_L() : LZ_W() : LW_Z()
      72. CaseOf 7
      73. WZ_L() : LW_Z() : LZ_W()
      74. CaseOf 8
      75. LZ_W() : WZ_L() : LW_Z()
      76. CaseOf 9
      77. WZ_L() : LZ_W() : LW_Z()
      78. CaseOf 10
      79. LZ_W() : LW_Z() : WZ_L()
      80. CaseOf 11
      81. LW_Z() : LZ_W() : WZ_L()
      82. EndSelect
      83. Until (aktion = 0) and (((Z=0) and (L=0)) or ((Z=0) and (W=0)))
      84. sammel[0,durchlauf]=L:sammel[1,durchlauf]=W:sammel[2,durchlauf]=Z
      85. ' Locate 2+durchlauf,1 : Print "L:";sammel[0,durchlauf];",W:";sammel[1,durchlauf];",Z:";sammel[2,durchlauf];" "
      86. endfor
      87. print ""
      88. for durchlauf,0,max_loop
      89. Print "L:";sammel[0,durchlauf];",W:";sammel[1,durchlauf];",Z:";sammel[2,durchlauf];" "
      90. endfor
      91. waitinput
      92. end
      Alles anzeigen

      Programmieren, das spannendste Detektivspiel der Welt.
    • Wie wäre es mal damit:
      (müsste Nr. 32 sein)


      Das Muttertagsgeschenk
      Drei Jungen möchten ihrer Mutter zum Muttertag ein Geschenk machen und wollen ihr einen neuen Hut kaufen. Es bedient der Lehrling, der für den von den Jungen ausgewählten Hut 30 Euro verlangt.
      Die Jungen bezahlen jeder nen Zehner und gehen nach Hause.

      Kurz darauf kommt der Meister, der die Jungen beim Verlassen des Geschäftes noch gesehen hat. Auf seine Nachfrage erklärt der Lehrling, dass er den Hut für 30 Euro verkauft hat.

      Der Meister ist aber etwas entsetzt, weil der Hut eigentlich nur 25 Euro kostet. Und weil er an zufriedenen Kunden interessiert ist, schickt er den Lehrling schnell mit 5 Euro (3 x 1 Euro und 1 x 2 Euro) den Jungen hinterher, damit er das zuviel gezahlte Geld an die drei zurückgibt.

      Jeder Junge nimmt einen Euro zurück, aber weil sie die restlichen 2 Euro nicht gerecht aufteilen können, und weil sie sich über das ehrliche Zurückgeben freuen, schenken sie die 2 Euro dem Lehrling.

      Auf dem weiteren Heimweg fängt dann aber einer der drei Jungen zu rechnen an und überlegt:

      Wir haben jeder erst 10 Euro gegeben, dann einen Euro zurück bekommen, also 3 x 9 Euro für den Hut bezahlt, also 27 Euro.
      Der Lehrling hat zwei Euro behalten.
      Das ergibt zusammen 29 Euro.

      Wir sind aber mit 30 Euro gekommen.
      Wo ist der eine Euro geblieben???????
      Computer setzen logisches Denken fort!
      Unlogisches auch....

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von ravenheart ()

    • Abt. Der Stoff aus dem Wir gebaut sind
      =============================
      [IMG:http://members.aon.at/startup/20_Proteine.jpg]

      Das sind die 20 Eiweiss-Bausteine, aus denen unser Körper (auf Anweisung der Doppelhelix der DesoxyRiboNuclein-Säure DNS im Zellkern) alle anderen Aminosäuren, Zellorgane, Zell-Arten, Gewebe und Organe aufbaut. Fast alle Zellen können dann auch mit Natrium und seiinem Gegenspieler Kalium umgehen - Stoffe, die Technikern wegen ihres elektrischen Spannungsgefälles als Batterie-Bestandteile sehr liebt wären, wären sie nicht viel zu agressiv und gefährlich ausserhalb des Körpers. In uns steckt eben das Know How eines tollen Ingeneurs: Evolution!
      Gruss
    • Abt. Gradientenabstieg
      =================
      Das Newton-Raphson-Verfahren funktioniert auch mit Funktionen in 2 Dimensionen, sprich: Z =Z(x,y). Leider ist das Verfahren insofern eher anspruchsvoll, als die partiellen Ableitungen der bekannten Funktion nach x und y ebenfalls bekannt sein sollten. Bei nicht allzu komplizierten Formeln sollte das aber gehen. Liegen allerdings nur Zahlen / Datensätze, z.B. mit Messwerten über 2 Dimensionen vor, dann empfehlen sich andere, rein numerische Verfahren, z.B. Nelder-Mead udgl.
      Gruss

      P.S.: Hier wurde versucht, die Auswirkungen der Wahl des Startpunktes auf den Algorithmus darzustellen.

      Brainfuck-Quellcode

      1. WindowTitle "Minimumsuche mit Gradientenabstieg (Newtonverfahren im R2)"
      2. AppendMenuBar 100,"Geg.: Z(x,y)=(x+sin(y))*exp(-sqr(x)*-sqr(y)) Ges.: Ort des lokalen Minimus"
      3. Window 0,0-%maxx,%maxy-40:font 2
      4. declare z!,x!,y!,xh&,yh&,f!,g!,s!
      5. xh&=width(%hwnd)\2:yh&=height(%hwnd)\2
      6. g!=1.5:s!=0.1:f!=220
      7. proc Z :parameters x!,y!
      8. return (x!+sin(y!))*exp(-sqr(x!)-sqr(y!))
      9. endproc
      10. proc dZdx :parameters x!,y!
      11. return exp(-sqr(y!)-sqr(x!))*(1-2*x!*(x!+sin(y!)))
      12. endproc
      13. proc dZdy :parameters x!,y!
      14. return exp(-sqr(y!)-sqr(x!))*(cos(y!)-2*y!*(x!+sin(y!)))
      15. endproc
      16. ' ------ Z-Feld darstellen ----
      17. cls
      18. x!=-g!:Repeat
      19. y!=-g!:While y!<=g!
      20. z!=Z(x!,y!)
      21. usepen 0,7+7*z!,rgb(0,0,400*z!)
      22. line xh&+x!*f!+z!*7,(yh&-y!*f!-z!*11) - xh&+x!*f!,yh&-y!*f!
      23. y!=y!+s!:endwhile
      24. x!=x!+s!:until x!>=g!
      25. '-------------------------------------------------------
      26. ' Gradientenabstieg
      27. '-------------------------------------------------------
      28. declare gstep!,xx!,yy!,xxo!,yyo!,dx!,dy!,dz!,eps!,n&,xxx!,yyy!
      29. gstep!=0.15
      30. whileloop 50,-50,-5:yyy!=&Loop/50
      31. whileloop -50,50,5 :xxx!=&Loop/30
      32. xx!=xxx!
      33. yy!=yyy! 'Startpunkt
      34. n&=0
      35. REPEAT
      36. dx!=dZdx(xx!,yy!)
      37. dy!=dZdy(xx!,yy!)
      38. xxo!=xx!:yyo!=yy!
      39. xx!=xx!-dx!*gstep!
      40. yy!=yy!-dy!*gstep!
      41. usepen 0,4,rgb(255,0,0)
      42. line xh&+xx!*f!,(yh&-yy!*f!)-xh&+xx!*f!,yh&-yy!*f!
      43. locate 2,2:print xx!,yy!,Z(xx!,yy!),n&;" "
      44. inc n&
      45. UNTIL ((xx!=xxo!) and (yy!=yyo!)) or (n&>=250)
      46. WEND
      47. WEND
      48. beep
      49. waitinput
      50. End
      Alles anzeigen