Martin Dunst: Rechenaufgabe: 500 Euro

0 60

Rechenaufgabe: 500 Euro

Martin Dunst
  • sonstiges
  1. 0
    Vinzenz Mai
    1. 0
      Vinzenz Mai
      1. 0
        Matze
        1. 0
          Vinzenz Mai
          1. 0
            Matze
            1. 0
              Vinzenz Mai
              1. 0
                Matze
                1. 0
                  Vinzenz Mai
                  1. 0
                    Matze
                    1. 1
                      Vinzenz Mai
                      1. 0
                        Matze
                        1. 0
                          Der Martin
                          1. 0
                            Gert
                            1. 0
                              Der Martin
                  2. 0
                    Matze
                    1. 0
                      Rouven
                    2. 0
                      Vinzenz Mai
              2. 0

                Lösung: 500 Euro

                Ashanti
                1. 0
                  Ashanti
                2. 0
                  Vinzenz Mai
                  1. 0
                    Ashanti
                    1. 0
                      Vinzenz Mai
                      1. 0
                        Ashanti
                        1. 0
                          Ashanti
                          1. 0
                            Vinzenz Mai
                            1. 0
                              Ashanti
                              1. 0

                                Anzahl Lösungen=24.813.354 Anzahl Rekursionen=28.258.486

                                Ashanti
                                1. 0
                                  Patrick Andrieu
                                  1. 0
                                    Patrick Andrieu
                                    1. 0

                                      Anzahl Lösungen=6.017.023 Anzahl Iterationen=7.302.334

                                      Vinzenz Mai
                                      1. 0
                                        Ashanti
                                      2. 0

                                        Anzahl Lösungen= 24813353 Anzahl Rekursionen= 28258321

                                        Ashanti
                                        1. 0
                                          Ashanti
                                          1. 0
                                            Ashanti
                                            1. 0

                                              Anzahl Lösungen= 24813353 Anzahl Iterationen 76567748

                                              Vinzenz Mai
                                              1. 0
                                                Ashanti
                                                1. 0
                                                  Ashanti
                                                  1. 0
                                                    Vinzenz Mai
                                                    1. 0
                                                      Ashanti
                                                      1. 0
                                                        Vinzenz Mai
                                                        1. 0
                                                          Ashanti
                                                          1. 0
                                                            Vinzenz Mai
                                                            1. 0
                                                              Ashanti
                                                              1. 0
                                                                Ashanti
                                                                1. 0

                                                                  Algo durch Caching tunen

                                                                  Ashanti
                                                                  1. 0

                                                                    Maximum Münzen=347

                                                                    Ashanti
                                  2. 0
                                    Ashanti
                3. 0
                  Don P
                  1. 0
                    Ashanti
          2. 0
            Sven Rautenberg
            1. 1
              Daniel Thoma
        2. 0
          Cheatah
  2. 0
    Daniel Thoma
    1. 0
      Vinzenz Mai
      1. 0
        Frank (no reg)
    2. 0
      Micha
  3. 0

    Allerliebst ...

    Ashanti
    • menschelei
    1. 0
      Sven Rautenberg
      1. 0
        Ashanti

Hallo,

Ich hab wieder eine kleine Rechenaufgabe auf meine private Website gestellt.
Wer mag: Die Aufgabe dreht sich um 500 Euro.
Bin gespannt, wer diesmal der/die Erste ist!

lg
Martin Dunst

--
Do what I say, not what I do.
--Tim Berners-Lee
  1. Hallo Martin,

    Ich hab wieder eine kleine Rechenaufgabe auf meine private Website gestellt.
    Wer mag: Die Aufgabe dreht sich um 500 Euro.

    nettes Rätsel (für Leute mit Programmiererfahrung sehr einfach).
    Es gibt allerdings mehrere richtige Lösungen.

    Freundliche Grüße

    Vinzenz

    1. Hallo Ingrid,

      Es gibt allerdings mehrere richtige Lösungen.

      die vier von mir getesteten und unterschiedlichen Lösungen wurden auch alle
      akzeptiert :-)

      Freundliche Grüße

      Vinzenz

      1. Hallo,

        die vier von mir getesteten und unterschiedlichen Lösungen wurden auch alle
        akzeptiert :-)

        Cheater^^ *SCNR

        Grüße, Matze

        1. Hallo Matze,

          die vier von mir getesteten und unterschiedlichen Lösungen wurden auch alle
          akzeptiert :-)

          gib doch mal eine Schätzung ab, wieviele richtige Lösungen es gibt:

          [ ] weniger als 1 Million
          [ ] mehr als 1 Million

          Freundliche Grüße

          Vinzenz

          1. Hallo,

            gib doch mal eine Schätzung ab, wieviele richtige Lösungen es gibt:

            [ ] weniger als 1 Million
            [ ] mehr als 1 Million

            schätzen? Ts ts, also entweder man kennt die Antwort oder nicht.
            Schätzen in Mathe geht ja gar nicht ;)

            Nee nee, ich bin nicht sehr gut in solchen Rätseln, daher versuch ichs gar nicht erst^^
            Die Formel dafür ist aber bestimmt gaaaanz einfach hehe...

            Grüße, Matze

            1. Hallo Matze,

              schätzen? Ts ts, also entweder man kennt die Antwort oder nicht.
              Schätzen in Mathe geht ja gar nicht ;)

              selbstverständlich geht das. Und wird auch gern genutzt.

              Nee nee, ich bin nicht sehr gut in solchen Rätseln, daher versuch ichs gar nicht erst^^
              Die Formel dafür ist aber bestimmt gaaaanz einfach hehe...

              die für die Gesamtzahl ist nicht ganz einfach, die für meine Abschätzung schon:
              Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

              Freundliche Grüße

              Vinzenz

              1. Hallo,

                selbstverständlich geht das. Und wird auch gern genutzt.

                mach das mal an der Supermarktkasse^^

                Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

                Und wie kommst du auf die 115? Geschätzt? Nach welcher Grundlage?
                Die 10 kommt sicher von den 10 Säcken oder?

                Grüße, Matze

                1. Hallo

                  Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

                  Und wie kommst du auf die 115? Geschätzt? Nach welcher Grundlage?

                  ich kenne 115 Möglichkeiten mit 10 verschiedenen Zahlen und 7 mit neun verschiedenen Zahlen, ich habe mir aber keine Gedanken gemacht, ob das alle
                  Lösungen sind :-)

                  Die 10 kommt sicher von den 10 Säcken oder?

                  Eben, da die Säcke numeriert sind, gibt es für einen Satz mit 10 verschiedenen
                  Zahlen 10! verschiedene Möglichkeiten, diesen einen Satz auf die Säcke zu
                  verteilen, die 7 mir bekannten Fälle mit 9 verschiedenen Zahlen habe ich für
                  meine Schätzung einfach vernachlässigt.

                  Mir bisher noch unbekannte Lösungen habe ich ebenfalls vernachlässigt, aber
                  meine Untergrenze gilt.

                  Freundliche Grüße

                  Vinzenz

                  1. Hallo,

                    hm... ich hätte doch Abi machen sollen ^^
                    Das ist mir zu hoch.

                    Grüße, Matze

                    1. Hallo Matze,

                      hm... ich hätte doch Abi machen sollen ^^

                      dafür ist es nie zu spät. Es gibt Abendschulen.

                      Das ist mir zu hoch.

                      wir fangen einfach klein an, mit einer Zahl und einem Sack:

                      Zahl: 1
                      Sack: 1

                      Nun kannst Du auf genau eine Art Deine Zahl verteilen.

                      Nächste Stufe: zwei Zahlen (1, 2) und zwei Säcke

                      Jetzt hast Du zwei Möglichkeiten, das ist 1 * 2:

                      1 2
                      2 1

                      3. Stufe: drei Zahlen (1, 2, 3) und drei Säcke

                      1 2 3  - 3 an letzter Position eingefügt
                      2 1 3
                      1 3 2  - 3 an zweiter Position eingefügt
                      2 3 1
                      3 1 2  - 3 an erster Position eingefügt
                      3 2 1

                      Du hast also drei mal soviele Möglichkeiten wie bei zwei Säcken: 1 * 2 * 3

                      4. Stufe

                      Nimm die Möglichkeiten aus der dritten Stufe und füge die 4
                       - an erster
                       - an zweiter
                       - an dritter
                       - an vierter
                      Position ein.
                      Siehst Du, dass es jetzt viermal soviele Möglichkeiten gibt, wie bei drei Zahlen? Also 1 * 2 * 3 * 4

                      Analog werden es bei 5 Zahlen 5 mal soviele sein wie bei 4 Zahlen,
                      ... und bei 10 Zahlen 10 mal soviele wie bei 9, das heisst bei x Zahlen

                      1 * 2 * 3 * 4 * ... * x = x!

                      Die Funktion, die diesen Wert hat, ist die Fakultätsfunktion, diese wird
                      mit einem Ausrufezeichen gekennzeichnet. Sie wächst verd^w sehr schnell.

                      Freundliche Grüße

                      Vinzenz

                      1. Hallo,

                        dafür ist es nie zu spät. Es gibt Abendschulen.

                        Soweit ich weiß kosten die aber was und auch wenn mein Einkommen zur Zeit recht gut ist, weiß ich nicht ob der Kosten/Nutzen Faktor für mich stimmt. Dabei bin ich eigentlich nichtmal bildungsfaul, vielleicht eher autodidaktisch.

                        wir fangen einfach klein an, mit einer Zahl und einem Sack:
                        (...)
                        Analog werden es bei 5 Zahlen 5 mal soviele sein wie bei 4 Zahlen,
                        ... und bei 10 Zahlen 10 mal soviele wie bei 9, das heisst bei x Zahlen

                        1 * 2 * 3 * 4 * ... * x = x!

                        Die Funktion, die diesen Wert hat, ist die Fakultätsfunktion, diese wird
                        mit einem Ausrufezeichen gekennzeichnet. Sie wächst verd^w sehr schnell.

                        Aha. Jetzt muss ich mir nur noch überlegen wofür man das ausser zur Kernspaltung noch gebrauchen könnte^^
                        Danke.

                        Grüße, Matze

                        1. Hallo Matze,

                          Die Funktion, die diesen Wert hat, ist die Fakultätsfunktion, diese wird mit einem Ausrufezeichen gekennzeichnet. Sie wächst verd^w sehr schnell.
                          Aha. Jetzt muss ich mir nur noch überlegen wofür man das ausser zur Kernspaltung noch gebrauchen könnte^^

                          wenn man Wahrscheinlichkeitsrechnung, Kombinatorik, statistische Methoden anwenden will, kommt man um die Fakultät nicht herum. Also beispielsweise wenn man ausrechnen will, wie hoch die Wahrscheinlichkeit ist, 6 Richtige im Lotto zu haben:

                          49 * 48 * 47 * 46 * 45 * 44       49! / 43!          1
                           -----------------------------  =  -----------  ~  ---------
                                        6!                        6!          84 Mio.

                          Die Division durch 6! kommt übrigens nur dadurch, dass die Reihenfolge der Zahlen keine Rolle spielt.
                          Aber wer will das wirklich wissen ... ?

                          So long,
                           Martin

                          --
                          Die meisten Menschen werden früher oder später durch Computer ersetzt.
                          Für manche würde aber auch schon ein einfacher Taschenrechner genügen.
                          1. 49 * 48 * 47 * 46 * 45 * 44       49! / 43!          1
                            -----------------------------  =  -----------  ~  ---------
                                          6!                        6!          84 Mio.

                            Das ist aber völlig falsch!
                            1. Zähler und Nenner vertauscht und zweitens sind es ca. 14 Mio.

                            1. Hallo Gert,

                              49 * 48 * 47 * 46 * 45 * 44       49! / 43!          1
                              -----------------------------  =  -----------  ~  ---------
                                            6!                        6!          84 Mio.

                              Das ist aber völlig falsch!

                              1. Zähler und Nenner vertauscht

                              stimmt, ich hatte im Ansatz "die Anzahl der Möglichkeiten" im Kopf. Die Wahrscheinlichkeit, mit der eine dieser Möglichkeiten auftritt, ist dann natürlich der Kehrwert.

                              und zweitens sind es ca. 14 Mio.

                              Stimmt auch. Aber wie zum Geier bin ich dann auf 84 gekommen? Sieht aus, als hätte ich mich vertippt und nicht durch 6!, sondern durch 5! dividiert.

                              Danke für die Klarstellung,
                               Martin

                              --
                              Nicht jeder, der aus dem Rahmen fällt, war vorher im Bilde.
                              http://aktuell.kennst.net/messe-stuttgart
                  2. Hallo nochmal,

                    Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

                    Was ist das eigentlich für eine Rechenart?
                    Wenn ich beim Win-Rechner x^y verwende, erhalte ich 404555773570791015625 !?
                    Das weicht irgendwie leicht von deinem Ergebnis ab.

                    Grüße, Matze

                    1. Hello,

                      Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!
                      Was ist das eigentlich für eine Rechenart?

                      die angegebene! :-) Das Satzzeichen gehört dazu, !=Fakultät, schematisch: 4!=4*3*2*1

                      MfG
                      Rouven

                      --
                      -------------------
                      sh:| fo:} ch:? rl:( br:& n4:{ ie:| mo:} va:) js:| de:] zu:| fl:( ss:) ls:& (SelfCode)
                      Ambition is the last refuge of failure.  --  Oscar Wilde (Irish Poet, Novelist, Dramatist and Critic, 1854-1900)
                    2. Hallo

                      Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

                      Was ist das eigentlich für eine Rechenart?

                      wie erwähnt, ist es die Fakultätsfunktion,

                      Wenn ich beim Win-Rechner x^y verwende, erhalte ich 404555773570791015625 !?

                      In der wissenschaftlichen Ansicht n! verwenden.

                      Freundliche Grüße

                      Vinzenz

              2. Salam!

                Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

                In der Aufgabenstellung steht nix von nummerierten Säckchen, deswegen kannst du die 10! auch weglassen. Und selbst wenn würde man als erstes in einer allgemeinen Lösung o.B.d.A fordern das die Säckchen aufsteigend nummeriert werden, um solche Isomorphien auszuschließen.

                Das hätte auch den Vorteil dass du alle 122 offensichtliche Lösungen nennen könntest, statt dich auf die 115 mit 10! Permutationen zu beschränken (die anderen 7 haben doppelte Säcke sodass man nur noch 10!/2 Permutationen hätte).

                Ich möchte mal eine Annahme über den kompletten Lösungsraum anstellen:

                Seien die Säcke aufsteigend durchnummeriert, d.h mit s_i Anzahl der Münzen im Sack i gelte s_i =< s_{i+1} für i aus {1,..,9}.

                Annahme: Eine aufsteigende Zahlenfolge (s_1,..s_10)
                mit S_i= s_1 + ... + s_i = Summe { s_j | j<i }
                ist genau dann eine Lösung wenn gilt:

                a) s_1 =  1

                b) s_i =< 1 + S_{i-1} für i={2,..,10}

                c) s_10 =  500 - S_9

                d) S_10 =  500

                insbesondere gilt s_10 =< 250!

                Beispiel:
                (1, 2, 4, 6, 10, 16, 33, 65, 129, 234)

                s_1=2   =< 1+1=2
                s_2=4   =< 1+1+2=4
                s_3=6   =< 1+1+2+4=8
                s_4=10  ist > 2^3 und <= 1+1+2+4+6=13
                usw.

                Beweis: vollständige Induktion:
                Man zeigt einfach sukzessive für n =1 bis 10 dass für die Teilfolgen (s_1,..s_n) gilt, dass sich alle Zahlen kleinergleich S_n durch Addition aus Teilfolgenelementen darstellen lassen.

                Für die Zahlen kleinergleich S_{n-1} brauchen wir das nicht zu zeigen, das folgt unmittelbar aus dem vorhergehenden Induktionsschritt. Und für alle Zahlen x im Intervall S_{n-1} bis S_n gilt wg. Bedingung b) unmittelbar dass x - s_n =< S_{n-1} womit wir eine Summendarstellung erhalten.

                Für die Rückrichtung, dass es keine weiteren Lösungen gibt, muss man sich überlegen das mit

                b*)   s_i > 1 + S_{i-1}

                Folgen würde das 1 + S_{i-1} schon nicht mehr darstellbar wäre.

                Und d) s_10 =< 250  gleichbedeutend mit S_9 >= 250

                q.e.d.

                bekomme ich jetzt 500€?

                :) Ashanti

                1. Salam!

                  In einfachen Worten ausgedrückt:

                  Die Säcke müssen von klein nach groß bestückt werden, dabei darf der jeweils nächste Sack höchstens so groß werden wie die Summe aller kleineren Säcke plus eins.

                  Konnte ich mit den kleineren Säcken alle Beträge kleiner ihrer Gesamtsumme darstellen, dann kann ich mit dem neuen Sack auch alle Beträge bis zur neuen Gesamtsumme darstellen.

                  Das Spielchen wiederholt man bis man 10 Säcke hat deren Gesmtsumme 500 ergibt.

                  Aleikum!
                   Ashanti

                2. Hallo

                  Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

                  In der Aufgabenstellung steht nix von nummerierten Säckchen, deswegen kannst du die 10! auch weglassen.

                  selbstverständlich sind die Säckchen numeriert, sonst muss man sie entweder öffnen oder wiegen :-)

                  Und selbst wenn würde man als erstes in einer allgemeinen Lösung o.B.d.A fordern das die Säckchen aufsteigend nummeriert werden, um solche Isomorphien auszuschließen.

                  Das ist aber nicht gefordert - und Du kannst selbstverständlich auch eine absteigende Folge eingeben, die Lösung wird korrekterweise als richtig akzeptiert. Also ist es eine korrekte Lösung. Daher gibt es ja soviele Lösungen, denn es gilt:

                  a) Die Säckchen sind unterscheidbar
                  b) Es gibt keine Einschränkung hinsichtlich: nur aufsteigend bestückbar o.ä.

                  Damit resultiert die hohe Gesamtzahl von möglichen Lösungen.

                  Annahme: Eine aufsteigende Zahlenfolge (s_1,..s_10)
                  mit S_i= s_1 + ... + s_i = Summe { s_j | j<i }
                  ist genau dann eine Lösung wenn gilt:

                  a) s_1 =  1
                  b) s_i =< 1 + S_{i-1} für i={2,..,10}
                  c) s_10 =  500 - S_9
                  d) S_10 =  500

                  das hatte ich mir inzwischen - ohne es mathematisch zu formulieren - auch
                  zusammengereimt.

                  Im Sinne: Es gibt konkrete Lösungen für die konkrete Aufgabenstellung bleibt
                  eben noch zu berechnen, wieviele verschiedene Lösungen das sind. Meine untere
                  Grenze bleibt selbstverständlich bestehen :-)

                  Die tatsächliche Gesamtzahl auszurechnen, bleibt als Übung :-)

                  Freundliche Grüße

                  Vinzenz

                  1. Hallo Vinzenz!

                    Ich weiß, dass es deutlich mehr als 417312000 Lösungen gibt, das ist 115•10!

                    In der Aufgabenstellung steht nix von nummerierten Säckchen, deswegen kannst du die 10! auch weglassen.

                    selbstverständlich sind die Säckchen numeriert, sonst muss man sie entweder öffnen oder wiegen :-)

                    Sorry mathematisch ist das blabla... du musst unterscheiden zwischen Aufgabenstellung und Implementierung, in der Aufgabenstellung redet er nur von einer Menge von 10 Säcken (keine Ordnung).

                    Und selbst wenn würde man als erstes in einer allgemeinen Lösung o.B.d.A fordern das die Säckchen aufsteigend nummeriert werden, um solche Isomorphien auszuschließen.

                    Das ist aber nicht gefordert - und Du kannst selbstverständlich auch eine absteigende Folge eingeben, die Lösung wird korrekterweise als richtig akzeptiert.

                    Das ist nur die Web-Implementierung die erlaubt die gleiche Lösung auf bis zu 10! Arten und Weisen einzugeben.

                    Eine korrekte Antwort auf die Aufgabenstellung könnte z.B. Lauten:
                    "2 Säcke mit 1 Münze, 3 mit 4, ...usw."

                    Ein Feedbackformular für sowas ist aber deutlich aufwendiger zu imlementieren.

                    Ein Mathematiker würde im erst beim Beweisen zur Bequemlichkeit und O.B.d.A. eine Ordnung einführen.

                    Glaub mir ich habe dank Doppelstudium zumindest ein Mathevordiplom einer der tollen "Eliteunis" in der Tasche udn kann das beurteilen.

                    b) Es gibt keine Einschränkung hinsichtlich: nur aufsteigend bestückbar o.ä.

                    Na ... schlag mal nach was O.B.d.A bedeutet. Sich hier mit Permutationen größer rumzuärgern ist (sorry) unprofessionel..

                    Salam!
                      Ashanti

                    1. Hallo ashanti,

                      Na ... schlag mal nach was O.B.d.A bedeutet. Sich hier mit Permutationen größer rumzuärgern ist (sorry) unprofessionel..

                      wieso sollte ich etwas nachschlagen, was ich schon lange weiß?
                      Ich ärgere mich auch nicht mit Permutationen herum, wie kommst Du auf diese Idee?

                      Schließe bitte nicht von Dir auf andere. *scnr*

                      Professionelle Grüße

                      Vinzenz

                      1. Hallo

                        Ich ärgere mich auch nicht mit Permutationen herum, wie kommst Du auf diese Idee? Schließe bitte nicht von Dir auf andere. *scnr*

                        "So seltsam es auch klingen mag, die Stärke der Mathematik beruht auf dem Vermeiden jeder unnötigen Annahme und auf ihrer großartigen Einsparung an Denkarbeit."

                        Ernst Mach

                        habe den Lösungsalgo in Javascript realisiert, leider geht mein Firefox ab der 8 Rekursion bzw. Sack in die Knie, man müsste noch ein paar sinnvolle Schranken einbauen um den Suchbaum zu kürzen, d.h. z.B. mit einem Anfang wie (1,1,1,1,1) würde man sowieso nie die Gesamtsumme 500 erreichen.

                        Salam!
                         Ashanti

                        1. Hi

                          habe den Lösungsalgo in Javascript realisiert, leider geht mein Firefox ab der 8 Rekursion bzw. Sack in die Knie, man müsste noch ein paar sinnvolle Schranken einbauen um den Suchbaum zu kürzen, d.h. z.B. mit einem Anfang wie (1,1,1,1,1) würde man sowieso nie die Gesamtsumme 500 erreichen.

                          OK, habe ein paar Baumabschneider eingebaut, aber alleine für 500€ mit 9 Säcken gibts bereits 14 Lösungen:

                          1: (1,2,4,8,16,32,64,128,245) rec:8
                          2: (1,2,4,8,16,32,64,127,246) rec:9
                          3: (1,2,4,8,16,32,64,126,247) rec:10
                          4: (1,2,4,8,16,32,64,125,248) rec:11
                          5: (1,2,4,8,16,32,64,124,249) rec:12
                          6: (1,2,4,8,16,32,64,123,250) rec:13
                          7: (1,2,4,8,16,32,63,127,247) rec:15
                          8: (1,2,4,8,16,32,63,126,248) rec:16
                          9: (1,2,4,8,16,32,63,125,249) rec:17
                          10: (1,2,4,8,16,32,63,124,250) rec:18
                          11: (1,2,4,8,16,32,62,126,249) rec:20
                          12: (1,2,4,8,16,32,62,125,250) rec:21
                          13: (1,2,4,8,16,31,63,126,249) rec:24
                          14: (1,2,4,8,16,31,63,125,250) rec:25

                          Bei 10 Säcken hat das Script nach 98.000 Rekursionen bereits 42.000 Lösungen ausgespuckt...da hab ich's dann auch abgebrochen.... Ohne Worte!

                          Salam!
                           Ashanti

                          1. Hallo

                            habe den Lösungsalgo in Javascript realisiert, leider geht mein Firefox ab der 8 Rekursion bzw. Sack in die Knie, man müsste noch ein paar sinnvolle Schranken einbauen um den Suchbaum zu kürzen, d.h. z.B. mit einem Anfang wie (1,1,1,1,1) würde man sowieso nie die Gesamtsumme 500 erreichen.

                            Mit etwas Überlegung kannst Du z.B. 125 als kleinsten Wert für Sack 10 ermitteln :-)

                            1: (1,2,4,8,16,32,64,128,245) rec:8

                            Das ist die "triviale Lösung", die Grundlage meiner ersten 122 Lösungen war.
                            Weiter hab' ich gar nicht erst nachgedacht ...

                            2: (1,2,4,8,16,32,64,127,246) rec:9
                            3: (1,2,4,8,16,32,64,126,247) rec:10
                            4: (1,2,4,8,16,32,64,125,248) rec:11
                            5: (1,2,4,8,16,32,64,124,249) rec:12
                            6: (1,2,4,8,16,32,64,123,250) rec:13
                            7: (1,2,4,8,16,32,63,127,247) rec:15
                            8: (1,2,4,8,16,32,63,126,248) rec:16
                            9: (1,2,4,8,16,32,63,125,249) rec:17
                            10: (1,2,4,8,16,32,63,124,250) rec:18
                            11: (1,2,4,8,16,32,62,126,249) rec:20
                            12: (1,2,4,8,16,32,62,125,250) rec:21
                            13: (1,2,4,8,16,31,63,126,249) rec:24
                            14: (1,2,4,8,16,31,63,125,250) rec:25

                            Bei 10 Säcken hat das Script nach 98.000 Rekursionen bereits 42.000 Lösungen ausgespuckt...da hab ich's dann auch abgebrochen.... Ohne Worte!

                            wie wäre es, wenn Du Deinen Algorithmus bekannt gäbest, vielleicht kann der
                            eine oder andere eine Verbesserung vorschlagen.

                            Deine 42.000 Lösungen gelten nun ohne Berücksichtigung der Reihenfolge.
                            Stell' Dir vor, wenn nun - wie im Lösungsformular - noch numerierte Säcke
                            dazukommen :-)

                            Friede,

                            Vinzenz

                            1. Hi

                              Mit etwas Überlegung kannst Du z.B. 125 als kleinsten Wert für Sack 10 ermitteln :-)

                              ja aber in den Bereich dieser unteren Schranke würde der Algo eh nie kommen .. zumindest nicht bei Zahlen so nahe an einer 2er Potenz wie 500.

                              wie wäre es, wenn Du Deinen Algorithmus bekannt gäbest, vielleicht kann der
                              eine oder andere eine Verbesserung vorschlagen.

                              ähm den Algorithmus hab ich doch bereist beschrieben?!?

                              Du meinst den JS Code? ich schick die HTML-Seite unten mit.

                              Die Aufwandskomplexität  des Codes kann man m.E. kaum noch optimieren (fast jede zwote Rekursion spuckt eine Lösung aus)!

                              Interessanter wäre eine mathematische Betrachtung wie aus der Lösung für 9 Säcke sich die Lösungen für 10 Säcke konstruieren (grob gesprochen, man nimmt Münzen aus den 9 Säcken udn stopft sie so in nen 10. Sack, den man so einreiht dass die Reihenfolge gewahrt bleibt, aber keine Lösungen doppelt kosntruiert werden). Und aus dieser Mathematischen Betrachtung sollte sich mit etwas Glück auch ne Formel für die ANzahl der Lösungen ableiten lassen.

                              Aber ehrlich, das Problem ist ausgelutscht und nicht sonderlich ergiebig. Es gibt AFAIK Mathematiker/Informatiker die sich mit ählichen Aufgaben herumschlagen, wo man aber mit Münzen bestimmter unterschiedlicher Werte bezahlen muss. Dass hat dann auch einen echten praktischen Hintergrund, z.B. bei der Optimierung von Machinenlaufzeiten.

                              Viel Spass mit dem Code, ist ein Draft ... und nicht verwirren lassen dass er erst ab 1 indiziert aber trotzdem 0 ausgibt.

                              Salam
                               Aschanti

                              ------------------------- HTML+JS-Code 500Euro.html

                              <html>
                                <head>
                                  <title>500 Euro Rtsel</title>
                                </head>

                              <body>
                                  <h1>500 Euro Rtsel</h1>

                              <script>
                              var s=new Array(0,1);  // Scke, s[0] ignorieren, weil es keinen nullten Sack gibt
                              var S=new Array(0,1);  // Zwischensummen
                              var S_min=new Array(); // minimale Schranken fr Zwischensummen
                              var muenzen=500;
                              var saecke=10;
                              var rec=0;      // # Rekursionen

                              function sack(i) {
                                rec++;

                              // letzter Sack erreicht => Ausgabe falls Lsung
                                if ( i == saecke) {
                                  s[i]=muenzen-S[i-1];
                                  if ( s[i] <= S[i-1]+1 && s[i] >= s[i-1] ) {
                                 document.writeln (l++ + ": (" +s+ ") rec:"+rec+"<br>"); // nullten Index ignorieren
                                  }
                                  return;
                                }

                              // ansonsten tiefer Suchen
                                for (var j = S[i-1]+1; j >= s[i-1]; j-- ) {
                               // Vorwrtszhlen liefert die Ergebnisse sehr spt
                               //for (var j = s[i-1] ; j <= S[i-1]+1 ; j++ ) {

                              s[i]=j;
                                  S[i]=S[i-1]+s[i];

                              if ( S[i] >= S_min[i] ) {
                                 sack(i+1);
                               }
                                }
                              }

                              function init_schranken() {
                                S_min[saecke]=muenzen;
                                for (var i=saecke-1 ; i > 0 ; i--) {
                               S_min[i]=Math.floor(S_min[i+1]/2);
                                }
                                document.writeln( "Minimale Zwischensummen:"+ S_min +"<br>");
                              }

                              var i=1; // Sack index
                              var l=1; // Lsung counter
                              init_schranken();
                              sack(2);

                              document.writeln( " Anzahl Rekursionen="+rec);

                              </script>
                                </body>
                              </html>

                              1. hab mal Opera drauf angesetzt, läuft zwar 10 mal lamer als Firefox, fragt mich aber nicht alle 5 Sekunden ob ich das langsam laufende Skript unterbrechen möchte.

                                1. Hallo Ashanti!

                                  Das war die Aufgabe:

                                  500 Stück 1€-Münzen sollen in zehn Säckchen so verteilt werden, dass jede Summe zwischen 1€ und 500€ gebildet werden kann, ohne dass ein Säckchen geöffnet werden muss.
                                  ---> In jedem der zehn Säckchen muss sich mindestens eine Münze befinden. <---

                                  Bei allem Respekt für Deine Programmierkunst, aber die ersten Zeilen, die mein Browser anzeigt (Sanduhr läuft noch, er wird es nicht schaffen - das Rechnen hat die CPU überstanden, das Rendern schafft der IE nicht mehr), sehen so aus:

                                  1: (0,1,2,4,8,16,32,64,--- mehr sehe ich nicht, da ein Fenster davor stand, alle Reichen sind an der Kante abgeschnitten)

                                  Von Säcken mit 0 Münzen war in der Aufgabe nie die Rede. Genauso wenig wie von einer 9-Säcken-Lösung ;)

                                  Viele Grüße aus Frankfurt/Main,
                                  Patrick

                                  --

                                  _ - jenseits vom delirium - _
                                  [link:hatehtehpehdoppelpunktslashslashwehwehwehpunktatomicminuseggspunktcomslash]
                                  Nichts ist unmöglich? Doch!
                                  Heute schon gegökt?
                                  1. Ups...

                                    alle Reichen sind an der Kante abgeschnitten

                                    Ja. Und die Nicht-Reichen sind arm dran...

                                    Viele Grüße aus Frankfurt/Main,
                                    Patrick

                                    --

                                    _ - jenseits vom delirium - _
                                    [link:hatehtehpehdoppelpunktslashslashwehwehwehpunktatomicminuseggspunktcomslash]
                                    Nichts ist unmöglich? Doch!
                                    Heute schon gegökt?
                                    1. Hallo,

                                      meine völlig unelegante iterative Vorgehensweise kommt auf:
                                      7302334 Iterationen durch die innerste Schleife und
                                      6017023 Lösungen, die letzte ist

                                      [1, 2, 4, 8, 16, 32, 64, 124, 124, 125]

                                      Mein Code, alles andere als beispielhaft, die Wahl fiel deswegen auf Python,
                                      weil es an der Konsole gerade verfügbar war:

                                        
                                      # Belege die Saecke mit der Mindestanzahl von Muenzen vor  
                                      sack  = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]  
                                      summe = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]  
                                        
                                      # Wir muellen das Wurzelverzeichnis von C: voll :-)  
                                      namepart = 'c:/martin.'  
                                        
                                      # Brute-Force mit nur wenig Ueberlegungen:  
                                      # Grenzen  
                                      # Index  Sack     Untergrenze   Obergrenze  
                                      #   0      1        1             1          - trivial  
                                      #   1      2        1             2          - trivial  
                                      #   2      3        1             4          - trivial  
                                      #   3      4        2             8          - Obergrenze trivial, Untergrenze, da sonst max. moegliche Zahl nicht erreichbar  
                                      #   4      5        4            16          - Obergrenze trivial, Untergrenze, siehe Sack 4  
                                      #   5      6        8            32          - Obergrenze trivial, Untergrenze, siehe vorher  
                                      #   6      7       16            64          - Obergrenze trivial, Untergrenze wie gehabt  
                                      #   7      8       32           128          - Obergrenze trivial, Untergrenze wie gehabt  
                                      #   8      9       63           167          - Untergrenze wie gehabt, Obergrenze: 1/3 unterhalb, 1/3 oberhalb und 1/3 fuer Sack 9  
                                      #   9     10      125           250          - aber Sack 10 = 500 - Summe(Saecke 1 bis 9)  
                                        
                                        
                                      filename = namepart + '0'  
                                      f = file(filename, "w")  
                                      iter  = 0  
                                      count = 0  
                                      for sack[1] in range(1,3):  
                                        # der naechste Sack muss mindestens soviel enthalten, wie der vorhergehende  
                                        summe[1] = sack[0] + sack[1]  
                                        for sack[2] in range(max(1, sack[1]), min(summe[1] + 2, 5)):  
                                          summe[2] = summe[1] + sack[2]  
                                          for sack[3] in range(max(2, sack[2]), min(summe[2] + 2, 9)):  
                                            summe[3] = summe[2] + sack[3]  
                                            for sack[4] in range(max(4, sack[3]), min(summe[3] + 2, 17)):  
                                              summe[4] = summe[3] + sack[4]  
                                              for sack[5] in range(max(8, sack[4]), min(summe[4] + 2, 33)):  
                                                summe[5] = summe[4] + sack[5]  
                                                for sack[6] in range(max(16, sack[5]), min(summe[5] + 2, 65)):  
                                                  summe[6] = summe[5] + sack[6]  
                                                  for sack[7] in range(max(32, sack[6]), min(summe[6] + 2, 128)):  
                                                    summe[7] = summe[6] + sack[7]  
                                                    for sack[8] in range(max(63, sack[7]), min(summe[7] + 2, 168)):  
                                                      # zaehle die Iterationen  
                                                      iter = iter + 1  
                                                      summe[8] = summe[7] + sack[8]  
                                                      # 1. Bedingung erfuellt: Summe der Inhalte ist 500 durch  
                                                      sack[9] = 500 - summe[8]  
                                        
                                                      if ((sack[9] > 250) or (sack[9] < 125) or sack[9] < sack[8]):  
                                                        # Sack 10 nicht im richtigen Intervall, oder kleiner als vorhergehender  
                                                        # passt nicht  
                                                        break;  
                                        
                                                      # Hier angelangt, haben wir eine richtige Loesung  
                                                      # zaehle die Treffer  
                                                      count = count + 1  
                                        
                                                      # Ausgabevorbereitung  
                                                      line = str(sack) + "\n"  
                                        
                                                      # Dateihandling  
                                                      # Nur 100.000 Eintraege je Datei - und auch nur dann eine Ausgabe auf die Konsole  
                                                      if ((count % 100000 == 0) and (count / 100000 > 0)):  
                                                        f.close()  
                                                        filename = namepart + str((count / 100000))  
                                                        f = file(filename, "w")  
                                                        print iter, " - ", count, ":", line,  
                                        
                                                      # Schreibe sie weg  
                                                      f.write(line)  
                                        
                                      # Fertig, Gesamtzahl noch ausgeben:  
                                      print iter, " - ", count, ":", line,  
                                      f.close()  
                                      
                                      

                                      Freundliche Grüße

                                      Vinzenz

                                      1. Hi

                                        Also offensichtlich ist einer unserer beiden Algos falsch, könten wir für kleinere Parameter vergleichen?

                                        Was spuckt dein programm für Muenzen 500 Säcke 9 aus?

                                        ich nix Python ...

                                        Salam
                                         Ashanti

                                      2. Hi

                                        Brute-Force mit nur wenig Ueberlegungen:

                                        Vielleicht zu wenig ?

                                        #   7      8       32           128          - Obergrenze trivial, Untergrenze wie gehabt

                                        Tatsächlich?

                                        dann ist wohl ne Fälschung im Umlauf
                                        (1,2,4,8,16,31,63,125,125,125)

                                        SCNR!
                                         Ashanti

                                        1. Ok, ich nehme alles zurück, aber sorry, ich verstehe deinen Code nicht.

                                          Salam!
                                           Ashanti

                                          1. Ok, ich nehme alles zurück, aber sorry, ich verstehe deinen Code nicht.

                                            Gut nochmal, soweit ich es verstehe sollten deine Lösungen mit der Ausgabe lexikografisch wachsen.

                                            Die erste Zeile die dein Script liefert ist:

                                            [1, 1, 3, 5, 10, 21, 42, 84, 84, 249]

                                            und sollte minimal sein.

                                            Lasse ich mein Script aufwärts rechnen bekomme ich aber

                                            1 1 1 4 8 16 31 63 125 250

                                            was eine deutlich kleinere und korrekte Lösung ist.

                                            => Dein Script ist fehlerhaft!

                                            ... insbesondere verstehe ich nicht wie du deine Schranken herleitest, eine richtige Begründung gibst du leider nicht an (???)

                                            Gute Nacht!
                                             Ashanti

                                            1. Hallo

                                              Ok, ich nehme alles zurück, aber sorry, ich verstehe deinen Code nicht.

                                              Gut nochmal, soweit ich es verstehe sollten deine Lösungen mit der Ausgabe lexikografisch wachsen.

                                              Die erste Zeile die dein Script liefert ist:

                                              [1, 1, 3, 5, 10, 21, 42, 84, 84, 249]

                                              und sollte minimal sein.

                                              Lasse ich mein Script aufwärts rechnen bekomme ich aber

                                              1 1 1 4 8 16 31 63 125 250

                                              was eine deutlich kleinere und korrekte Lösung ist.

                                              => Dein Script ist fehlerhaft!

                                              Du hast recht => man sollte um diese Zeit keinen Code mehr schreiben
                                              und erst recht keine unnötigen "Abkürzungen" einbauen, die sich als Fehler
                                              entpuppen

                                              if ((sack[9] > 250) or (sack[9] < 125) or sack[9] < sack[8]):
                                                                # Sack 10 nicht im richtigen Intervall, oder kleiner als vorhergehender
                                                                # passt nicht

                                              # hier steckt der Fehler
                                                                  # verlaesst die innere Schleife statt direkt den
                                                                  # naechsten Schleifendurchlauf vorzunehmen

                                              # break;

                                              # Entweder ein continue oder ein einfaches else
                                                                  continue

                                                
                                              
                                              > ... insbesondere verstehe ich nicht wie du deine Schranken herleitest, eine richtige Begründung gibst du leider nicht an (???)  
                                                
                                              Zu den Grenzen:  
                                              Die Obergrenzen sollten klar sein:  
                                                
                                              1) Bis Sack 8 die Zweierpotenzen,  
                                                
                                              2) bei Sack 9 ist es erforderlich:  
                                                 a) die Summe von Sack 1-8 maximal um 1 kleiner ist als der Inhalt von Sack 9  
                                                 b) Sack 10 hat mindestens soviel Inhalt wie Sack 9  
                                                 => Minimale Summe = 3\* Inhalt von Sack 9 - 1  
                                                 => 3 \* Inhalt von Sack 9 = 501  
                                                 => Maximaler Inhalt von Sack 9 = 167  
                                                
                                              3) Sack 10: Grenze klar (hast Du ja begründet)  
                                                
                                              Die Untergrenzen ergaben sich durch gezieltes Probieren :-)  
                                              Verkleinere die Untergrenze jeweils um 1 und ermittle die maximal erreichbare  
                                              Summe, bis zu der jede Zahl darstellbar ist => die Summe wird kleiner als 500  
                                              sein.  
                                                
                                              Deine Vorgehensweise ist deutlich schneller :-)  
                                              Freundliche Grüße  
                                                
                                              Vinzenz
                                              
                                              1. Salam Vinzenz

                                                Deine Vorgehensweise ist deutlich schneller :-)

                                                Heisst das du kannst mein Ergebnis bestätigen?

                                                Und die Javascriptlösung ist schneller als die mit Python ???

                                                Oder wieviele Ergebnisse bekommst du jetzt?
                                                Bei wievielen Rekursionen?

                                                (oder rechnet dein Script noch ;)

                                                Viele Grüße
                                                 Ashanti

                                                1. Guten Morgen Vinzenz

                                                  Habe gerade die veränderte Überschrift registriert :)

                                                  Meine Fragen haben sich erübrigt, außer

                                                  Und die Javascriptlösung ist absolut schneller als die mit Python ???

                                                  Salam
                                                    Ashanti

                                                  1. Hallo

                                                    Und die Javascriptlösung ist absolut schneller als die mit Python ???

                                                    zu absolut kann ich nichts sagen - hab' ich noch nicht getestet.
                                                    Derzeit gehe ich davon aus, dass vor allem die Dateizugriffe viel Zeit kosten.

                                                    Freundliche Grüße

                                                    Vinzenz

                                                    1. Hi

                                                      zu absolut kann ich nichts sagen - hab' ich noch nicht getestet.

                                                      ich schon hab aber hier nen alten P2:
                                                      35min ohne ausgabe
                                                      45min mit

                                                      Salam!
                                                       Ashanti

                                                      1. Hallo

                                                        ich schon hab aber hier nen alten P2:
                                                        35min ohne ausgabe
                                                        45min mit

                                                        ohne Ausgabe, Celeron 3GHz, Dein Code 1:1 nach Python übersetzt:

                                                        rekursiv: 01:37 min
                                                        iterativ: 06:45 min (mein Notebook mit einem Pentium M, 1500MHz ist schneller)

                                                        Deine Ersparnis von ungefähr 48.000.000 macht sich da sicher bemerkbar.
                                                        Außerdem ist mein Code extrem unflexibel und nicht auf vergleichbare
                                                        Probleme anwendbar.

                                                        Freundliche Grüße

                                                        Vinzenz

                                                        1. Hi Vinzenz!

                                                          Deine Ersparnis von ungefähr 48.000.000 macht sich da sicher bemerkbar.
                                                          Außerdem ist mein Code extrem unflexibel und nicht auf vergleichbare
                                                          Probleme anwendbar.

                                                          Rekursiv ist natürlich flexibler als Iterativ, aber schneller sollte letzteres sein, (zumindest ein paar Prozent) man spart nämlcih 28.000.000 Funktiosnaufrufe.

                                                          Es liegt an der Art der Schrankenberechnung wenn mein Code schneller ist.

                                                          Aber wer will schon 25.000.000 Lösungen ausrechnen???

                                                          Oder kommt jetzt als nächstes ein Agent der die Webseite mit Lösungen zubombt??? ;-)

                                                          Salam
                                                           Ashanti

                                                          1. Hallo

                                                            Oder kommt jetzt als nächstes ein Agent der die Webseite mit Lösungen zubombt??? ;-)

                                                            Wenn man jetzt noch berücksichtigt, dass man jede Lösung auf viele verschiedene
                                                            Arten eintragen könnte, könnte man gewaltig spammen, ohne das Formular zweimal
                                                            auf die gleiche Art und Weise auszufüllen. *g*

                                                            Die nächste Frage, die ich per brute-force und einer modifizierten Version
                                                            Deiner Lösung mir beantworten lassen will, ist folgende:

                                                            Bei welcher Anzahl von Münzen bei gegebener Anzahl von Säcken (Test natürlich mit 10) ist die Anzahl der Lösungen maximal.

                                                            Bei n Säcken und n Münzen gibt es ebenfalls genau eine Lösung
                                                            Bei n Säcken und (2^n)-1 Münzen gibt es genau ein Lösung

                                                            Bei wievielen Münzen gibt es die maximale Anzahl von Möglichkeiten.
                                                            Wäre jemand so freundlich gewesen und hätte das Problem mathematisch analysiert,
                                                            könnte man es einfach ausrechnen, bei 10 Säcken lasse ich lieber den Rechner laufen ...

                                                            Freundliche Grüße

                                                            Vinzenz

                                                            1. Hi

                                                              Die nächste Frage, die ich per brute-force und einer modifizierten Version
                                                              Deiner Lösung mir beantworten lassen will, ist folgende:

                                                              Bei welcher Anzahl von Münzen bei gegebener Anzahl von Säcken (Test natürlich mit 10) ist die Anzahl der Lösungen maximal.

                                                              Du bist schon ein  Optimist! Nur weil der Fall für 500 Münzen in knapp einer Minute durchgerechnet wurde muss das nicht für die anderen Fälle gelten.

                                                              ich würde versuchen aus den Schranken etwas abzuleiten, so in der Art "wenn die Summe der Differenzen aller min und max Schranken maximal ist dann auch die Anzahl der Löungen.

                                                              Übrigens probier mal 150 Münzen mit 9 Säcken :)

                                                              Salam
                                                               Ashanti

                                                              1. Hi Vinzenz

                                                                und rechnet der Laptop immer noch :-)

                                                                Salam
                                                                 Ashanti

                                                                1. Hi Vinzenz

                                                                  IMHO kann man den Algo nochmals rasant beschleunigen wenn man Zwischenergebnisse cachet.

                                                                  Die rekursive Funktion müsste überprüfen ob sie schonmal mit der gleichen letzten Zwischensumme und Sackfüllung aufgerufen wurde, falls
                                                                  nein: Anzahl der Folgelösungen berechnen und merken!
                                                                  ja:   Anzahl der Folgelösungen übernehmen.

                                                                  Beispiel:

                                                                  Muenzen/Saecke: 30/6
                                                                  ...
                                                                  53:   1 2 2 4 6 15  rec:70  ite:53
                                                                  54:   1 2 2 3 9 13  rec:72  ite:54
                                                                  55:   1 2 2 3 8 14  rec:73  ite:55
                                                                  56:   1 2 2 3 7 15  rec:74  ite:56
                                                                  57:   1 2 2 2 8 15  rec:76  ite:57
                                                                  ...
                                                                  72:   1 1 3 4 6 15  rec:96  ite:72
                                                                  73:   1 1 3 3 9 13  rec:98  ite:73
                                                                  74:   1 1 3 3 8 14  rec:99  ite:74
                                                                  75:   1 1 3 3 7 15  rec:100 ite:75
                                                                  76:   1 1 2 5 10 11  rec:103 ite:76

                                                                  die Teilsequenzen 1 2 2 3 und 1 1 3 3 haben die gleiche Summe
                                                                  und die gleichen Endzahl, deswegen folgen immer 3 weitere Teillösungen (54-56 = 73-75).

                                                                  Auf diese Art und Weise verlagert man effektiv Zeitkomplexität
                                                                  auf Speicherkomplexität :)

                                                                  Salam
                                                                   Ashanti

                                                                  1. Hallo

                                                                    IMHO kann man den Algo nochmals rasant beschleunigen wenn man Zwischenergebnisse cachet.

                                                                    Tatsächlich ist so mehr als Faktor 100 Beschleunigung machbar:

                                                                    Opera sagt:

                                                                    "Maximum für Säcke=10 liegt bei Münzen=347 mit 47.493.951 Möglichkeiten"

                                                                    Ich denke das Thema ist jetzt erschöpfend diskutiert ...

                                                                    Salam!
                                                                      Ashanti

                                  2. Lieber Patrick

                                    1: (0,1,2,4,8,16,32,64,--- mehr sehe ich nicht, da ein Fenster davor stand, alle Reichen sind an der Kante abgeschnitten)

                                    Der Code ist ein Hack ... aber wer lesen kann ist klar im Vorteil ... ich schrieb

                                    "und nicht verwirren lassen dass er erst ab 1 indiziert aber trotzdem 0 ausgibt."

                                    und im Code steht nochmal "nullten Index ignorieren"

                                    Um analog zum beschriebenen Algo zu bleiben hab ich das Array
                                    ab 1 indiziert, deswegen gibt er auch einen "0-ten Sack" aus.
                                    Würde dein IE nicht beim Rendern zusammenbrechen, hättest du gesehen dass pro Zeile 11 Zahlen ausgegeben werden.

                                    Habe nochmal rumoptimiert, und dieses "0-ter-Index-Feature" rausgeschmissen.

                                    Die Optimierung hat aber wie befürchtet nur wenig
                                    an Geschwindigkeit gebracht ich erhalte jetzt:

                                    Anzahl Rekursionen= 28258321
                                    Anzahl Lösungen= 24813353

                                    habe also 165 Rekursionen und 1 Lösung eingespart (letzteres würde ich als Bug bezeichnen, den zu finden ich dem Forum überlasse)[*]

                                    Ach ja dass die Browser Probleme haben 24 Millionen Zeilen auszugeben ist nachvollziehbar, deswegen habe ich auch beim 10 Sack-Fall die Ausgabe der Lösungen in Opera auskommentiert.

                                    Um es dir einfacher zu machen hab ich dir jetzt ne GUI eingebaut, ob die allerdings in deinem IE funktioniert kann ich dir mangels Windoof nicht sagen (dafür gehen meine Umlaute beim cut&paste aus emacs flöten ... ).

                                    Salam nach FFM
                                      Ashanti

                                    [*] ich habs, ich habs!!! (TIP: das Alte Ergebnis war falsch)

                                    ---------------- neue version 500Euro.html

                                    <html>
                                      <head>
                                        <title>500 Euro Rtsel</title>
                                      </head>

                                    <body>
                                        <h1>500 Euro Rtsel </h1>

                                    Aufgabestellung siehe
                                    <a href="http://www.mindfile.org/Spiele/Eurosack">
                                    http://www.mindfile.org/Spiele/Eurosack
                                    </a>

                                    <p>

                                    <form>
                                    Muenzen <input name="muenzen" value="500"><br>
                                    Scke <input name="saecke" value="9"><br>
                                    Ausgabe <input type="checkbox" name="ausgabe" checked>
                                    <input type="submit" value="leg los" onClick="main()">
                                    </form>

                                    <script>

                                    function main() {

                                    var s=new Array();  // Scke,
                                    var S=new Array();  // Zwischensummen
                                    s[1]=1;S[1]=1;      //s[0] ignorieren, weil es keinen nullten Sack gibt
                                    var S_min=new Array(); // minimale Schranken fr Zwischensummen
                                    var s_max=new Array(); // maximale Schranken fr Scke

                                    // Defaultwerte fr onLoad-Ausfhrung
                                    var muenzen=500;
                                    var saecke=10;
                                    //var muenzen=250;
                                    var saecke=9;
                                    var ausgabe="on";

                                    var l=0;    // init Lsung counter

                                    var rec=0;      // init # Rekursionen

                                    // Parameter einlesen
                                      saecke=document.forms[0].saecke.value;
                                      muenzen=document.forms[0].muenzen.value;
                                      ausgabe=document.forms[0].ausgabe.checked;

                                    document.open();
                                       document.writeln( "<pre>");

                                    init_schranken();

                                    document.writeln( "<hr><h3>BERECHNUNG:</h3>" );
                                     start=write_Time();
                                     sack(2);  // Rekursion starten
                                     ende=write_Time();
                                     document.writeln( "Dauer: "+(ende-start)+" millisec" );

                                    document.writeln( "<hr><h3>ERGEBNIS:</h3>" );
                                     document.writeln( "Anzahl Rekursionen=\t"+rec );
                                     document.writeln( "Anzahl Lsungen=\t"+l );
                                     document.writeln( "</pre>");
                                     document.close();

                                    function sack(i) {
                                      rec++;

                                    // letzter Sack erreicht => Ausgabe falls Lsung, Rekursion abbrechen
                                      if ( i == saecke) {
                                        s[i]=muenzen-S[i-1];
                                        if ( s[i] <= S[i-1]+1 && s[i] >= s[i-1] ) {
                                       l++;
                                       if (ausgabe ) {
                                      document.writeln (l + ":\t <b>" +s.join(" ")+ "</b>\t rec:"+rec); // Ausgabe hier auskommentieren
                                       }
                                        }
                                        return;
                                      }

                                    // ansonsten tiefer Suchen
                                      var max,min;

                                    max=S[i-1]+1;
                                      max=Math.min( max, s_max[i] );

                                    min=s[i-1];
                                      s_min=S_min[i] -S[i-1];   // wg S[i] = S[i-1]+j >= S_min[i]
                                      min=Math.max( min, s_min);

                                    for (var j = max ; j >= min ; j-- ) {
                                     // Abwrtsszhlen liefert eher Ergebnisse als Aufwrts
                                     //for (var j = min ; j <= max ; j++ ) {

                                    s[i]=j;
                                        S[i]=S[i-1]+s[i];

                                    //if ( S[i] >= S_min[i] ) {
                                     sack(i+1);
                                     //}
                                      }
                                    }

                                    function init_schranken() {
                                      S_min[saecke]=muenzen;
                                      for (var i=saecke-1 ; i > 0 ; i--) {
                                     S_min[i]=Math.floor(S_min[i+1]/2);
                                      }

                                    // da Saecke aufsteigend sortiert, kann i-ter Sack hoechstens soviele
                                      // Muenzen enthalten wie man noch maximal in alle groeeren stecken kann.
                                      for (var i=saecke ; i >0 ; i--) {
                                     var kleinere_saecke=i-1;
                                     var groessgleich_saecke=saecke-kleinere_saecke;
                                     s_max[i]=Math.floor( (muenzen-kleinere_saecke)/groessgleich_saecke);
                                      }
                                      document.writeln( "<hr><h3>INIT:</h3>");
                                      document.writeln( "Minimale Zwischensummen:"+ S_min.join("\t"));
                                      document.writeln( "Maximale Sackfllung:\t"+ s_max.join("\t") );
                                      document.writeln( "Muenzen/Saecke:\t" + muenzen+"  "+saecke );
                                    }

                                    function write_Time() {
                                      var Jetzt = new Date();
                                      document.writeln("Zeit: "+Jetzt.toLocaleString());
                                      var Zeit = Jetzt.getTime();
                                      return Zeit;
                                    }

                                    }

                                    </script>

                                    </body>
                                    </html>

                3. Hallo,

                  Annahme: Eine aufsteigende Zahlenfolge (s_1,..s_10)
                  mit S_i= s_1 + ... + s_i = Summe { s_j | j<i }
                  ist genau dann eine Lösung wenn gilt:

                  a) s_1 =  1

                  b) s_i =< 1 + S_{i-1} für i={2,..,10}

                  c) s_10 =  500 - S_9

                  d) S_10 =  500

                  insbesondere gilt s_10 =< 250!

                  Beispiel:
                  (1, 2, 4, 6, 10, 16, 33, 65, 129, 234)

                  s_1=2   =< 1+1=2
                  s_2=4   =< 1+1+2=4
                  s_3=6   =< 1+1+2+4=8
                  s_4=10  ist > 2^3 und <= 1+1+2+4+6=13
                  usw.

                  In a) verlangst du s_1 = 1, aber im Beispiel erklärst du s_1 = 2. Soll das jetzt eher ein Gegenbeispiel sein, oder hattest du aus Versehen ein s_0 im Sinn und die Erklärung zum Beispiel (1, 2, 4, 6, 10, 16, 33, 65, 129, 234) ist also falsch?

                  Gruß, Don P

                  1. Hi Don,

                    s_1=2   =< 1+1=2 ...

                    In a) verlangst du s_1 = 1, aber im Beispiel erklärst du s_1 = 2. Soll das jetzt eher ein Gegenbeispiel sein, oder hattest du aus Versehen ein s_0 im Sinn und die Erklärung zum Beispiel (1, 2, 4, 6, 10, 16, 33, 65, 129, 234) ist also falsch?

                    Danke für den Hinweis, ist natürlich ein Versehen, sollte  s_2 heißen.

                    Das normale zerebrale Kuddelmuddel mit Indizierungen die mal mit 1 oder 0 anfangen. (So wie ich mir seit der Euroumstellung
                    nur noch Geldbeträge mit einer 2er Potenz Unschärfe merken kann. ;-)

                    Egal wie man jetzt indiziert, für den 2. Sack muss gelten:
                     er hat mind. eine und höchstens 2 Münzen.

                    Salam
                      Ashanti

          2. Moin!

            gib doch mal eine Schätzung ab, wieviele richtige Lösungen es gibt:

            [X] weniger als 1 Million
            [ ] mehr als 1 Million

            Ich habe 10 Säcke. In jeden kann ich zwischen 1 und 500 Münzen reintun, also 500 Zustände erzeugen. Das mal 10 ergibt 5000 Lösungen.

            Als obere Schranke sollte das also ausreichen. :)

            - Sven Rautenberg

            --
            "Love your nation - respect the others."
            1. Hallo Sven,

              Ich habe 10 Säcke. In jeden kann ich zwischen 1 und 500 Münzen reintun, also 500 Zustände erzeugen. Das mal 10 ergibt 5000 Lösungen.

              Was ist das denn für eine Rechnung? Wenn man einfach nur die Anzahl der Möglichkeiten in jedes Säckchen 1..500 Münzen zu tun (ohne die Summe zu berücksichtigen) hat man ja 499^10 Möglichkeiten also ... viele ;-)

              Wenn man die Summe und die Unabhängigkeit von der Reihenfolge berücksichtigt, wird das deutlich weniger. Auf den ersten Blick sehe ich aber nicht, wie man das einfach berechnen kann.

              Grüße

              Daniel

        2. Hi,

          Cheater^^ *SCNR

          hier bin ich. Und bitte schreib meinen Namen richtig. Was gibt's?

          Cheatah, SCNR2 ;-)

          --
          X-Self-Code: sh:( fo:} ch:~ rl:° br:> n4:& ie:% mo:) va:) de:] zu:) fl:{ ss:) ls:~ js:|
          X-Self-Code-Url: http://emmanuel.dammerer.at/selfcode.html
          X-Will-Answer-Email: No
          X-Please-Search-Archive-First: Absolutely Yes
  2. Hallo Martin,

    Warum eigentlich 10 Säckchen wenn die naheliegendste Lösung mit 9 Säckchen auskommt? ;-)

    Grüße

    Daniel

    1. Hallo Daniel,

      Warum eigentlich 10 Säckchen wenn die naheliegendste Lösung mit 9 Säckchen auskommt? ;-)

      das hat Martin bestimmt absichtlich gemacht, damit wir hier Stoff für eine
      Diskussion haben :-) Vielleicht dürfen wir nachher auch raten, was die
      häufigst genannte Lösung (ohne Beachtung der Reihenfolge) ist.

      Freundliche Grüße

      Vinzenz

      1. Hi,

        der Bitte, eine Statistik über die Antworten auszugeben, ist er doch schon für die letzte (Tierquälerei-)Rechenaufgabe nicht nachgekommen. :(

        So long, so short
        Frank

    2. Hallo Daniel Thoma,

      Warum eigentlich 10 Säckchen

      Habe ich mich auch gefragt, nachdem ich erstmal munter drauf los getippt habe und dann den Hinweis bekam, es seien mehr als 500 Taler ;-)

      Mit freundlichem Gruß
      Micha

  3. Hallo Martin,

    500 Euro.

    ich habe auf der Webseite einen Eintrag hinterlassen das es um die 25 Millionen Lösungen für dein Problem gibt, kannst du mir erklären wieso du den kommentarlos löschst???

    Salam!
      Ashanti

    1. Moin!

      500 Euro.

      ich habe auf der Webseite einen Eintrag hinterlassen das es um die 25 Millionen Lösungen für dein Problem gibt, kannst du mir erklären wieso du den kommentarlos löschst???

      Auszug aus dem Impressum: "Der Betreiber dieser Website behält sich vor, Leserkommentare ohne Angabe von Gründen teilweise oder ganz zu löschen."

      - Sven Rautenberg

      --
      "Love your nation - respect the others."
      1. Hallo

        Auszug aus dem Impressum: "Der Betreiber dieser Website behält sich vor, Leserkommentare ohne Angabe von Gründen teilweise oder ganz zu löschen."

        Tja und ich behalte mir vor nachzufragen.

        Auszug aus meinem Verständnis:

        a) Er braucht nicht antworten
        b) Ich brauch ihn dann künftig nicht zu beachten

        Salam!
         Ashanti