Momentan habe ich 11 Aufgaben vorrätig. Vorschläge für neue Rätsel nehme ich immer gerne an (bitte als Mail und als Betreff für Vorschläge rdw-vorschlag enthalten lassen (in klein).
RDW 2007/4 - Raetsel der Woche Nummer 4 des Jahres 2007
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Regeln:
~~~~~~~
       * Bitte nicht vor Ablauf der ersten 72 Stunden (= drei Tage)
         nach Veröffentlichung Hinweise, Spoiler, Lösungen oder
         Lösungsteile posten!

       * Verständnisfragen dürfen selbstverständlich auch vor
         Ablauf der drei Tage in diesem Thread gestellt
         werden. Diskussionen über Lösungsansätze gehören aber
         nicht hierher.

       * Die Verwendung von Modulen ist generell erlaubt, wird jedoch
         das ganze Problem von einem Modul erschlagen, so macht das
         die Lösung langweilig -- und das ist nicht unbedingt der
         Sinn dieser Rätsel.

       * Erst wenn die drei Tage abgelaufen sind, werden Lösungen in
         das Wiki gestellt und hier verlinkt.

       * Sobald die Lösungen veröffentlicht wurden darf hier
         natürlich über sie diskutiert werden.

       * Die Lösungen sollten nicht unbedingt von jedem Einzelnen
         gepostet, sondern vor allem per E-Mail an mich geschickt
         werden, damit ich sie testen, "bewerten"  und zusammenfassen
         kann. Die Adrese dafür lautet:

          stephan <---Punkt---> barth <---At---> gmx <---Punkt---> de

         Im Betreff sollte 'RDW' (also wirklich RDW und nicht Rätsel der
         Woche oder andere Ausformulierungen) und die Nummer des Rätsels
         stehen. Hilfreich wäre neben dem Quelltext der Benutzername
         im Forum sowie Perl- und OS-Version (siehe auch perl -v).


Die Aufgabe:
~~~~~~~~~~~~
        Gib zu einer gegebenen Zahl möglichst wenige Quadratzahlen aus,
           deren Summe diese Zahl ergibt.

Beispiel:
~~~~~~~~~
        Beispiel:
           Eingabe:
           7
           Ausgabe:
           4+1+1+1
           Eingabe:
           23
           Ausgabe:
           9+9+4+1
           Eingabe:
           179
           Ausgabe:
           121+49+9\n\n

<!--EDIT|Ishka|1171934199-->

soo ... ist bestimmt nicht die beste/richtige, aber es tut.\n\n

<!--EDIT|vayu|1171966881-->

Gibt es für dieses Problem eigentlich eine "intelligente" mathematische Lösung? Mir ist bislang nur eine Lösung eingefallen, die verschiedene Varianten durchprobiert.

Also ich habe eine recht gute Lösung gefunden, die schnell ein gutes Ergebnis ausgibt. Ob das immer das beste ist, ist aber nicht gesichert. Um immer die beste Lösung zu finden fällt mir im Moment auch nur Brute-Force ein.

[quote=murphy,21.02.2007, 12:58]Gibt es für dieses Problem eigentlich eine "intelligente" mathematische Lösung? Mir ist bislang nur eine Lösung eingefallen, die verschiedene Varianten durchprobiert.[/quote]
ja, es gibt einige sätze darüber - soweit ich mich da erinnere.
z.b. kann bewiesen werden, dass jede natürliche Zahl als Summe von höchstens X (das X verrate ich jetzt nicht) Quadratzahlen darstellbar ist
und es gibt auch ne mathematische formel, die dir diese quadratzahlen auch berechnen kann!

es gibt das sogenannte "YYYYYYY Problem" das sich damit beschäftigt dass eine Zahl mit maximal X Quadraten auszudrücken ist evtl auch weniger.

allerdings war mir das irgendwie ein bisschen zu hoch muss ich gestehen ^^
hab mir die Dokumente zwar mal zu gemüte geführt aber das zu implementieren fehlt mir echt die Zeit.

ich habs per "Brute Force" realisiert. Allerdings auch nur 2 verschiedene Ansätze hergenommen.

edit: hab die Namen und die anzahl quadrate mal entfernt, durch esskars post angeregt :P\n\n

<!--EDIT|vayu|1172060511-->

Hmm, ich bin ja kein Experte in Zahlentheorie, aber alles was mir bisher eingefallen ist, um eine Zahl additiv in Quadrate zu zerlegen, braucht entweder eine volle Primfaktorisierung der Zahl, ist ein Brute-Force-Ansatz oder liefert nicht garantiert die minimale Anzahl von Summanden.

Nun ist zwar die Lösung über eine Faktorisierung theoretisch sehr befriedigend, aber irgendwie nicht viel schneller als eine schlaue Brute-Force-Methode -- hat hier irgendwer schon eine perfekte Lösung, die schnell und garantiert minimal ist?

Die eigendliche Berechnung machen weniger als 15 Zeilen. Alles weitere ist nur Ästetik. :-)

Wie üblich habe ich die abgegebenen Lösungen ins Wiki gestellt.

Oops!

Habe mit Entsetzen festgestellt, dass meine Lösung für einige Eingaben kein Ergebnis liefert und möchte hier die Korrektur nachschieben:

ersetzen durch:


Gruss, Doc