Algorithmus (Summe aller Zahlen) = 2008, Kehrwert aller Summanden =1

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Algorithmus (Summe aller Zahlen) = 2008, Kehrwert aller Summanden =1

    Hej ho...
    Also ich bin gerade dabei einen Algoritmus zum lösen des folgenden Problemes zu erstellen:
    Mir stellte letztlich jemand folgende Frage:
    Die Summe einer Menge natürlicher Zahlen ergibt genau 2008 und die Summe der Kehrwerte dieser Zahlen genau 1!
    Natürliche Zaheln heißt nur 1,2,3,4,5,6,7,....
    Die anzahl der Zahlen ist Sch*** Egal!
    ICh habs mal mit Backtracing versucht, aber des klappt ne ganz, i hab schon nen code, aber der funzt ne ganz un ich will ja niemandem hier beeinflussen ... also ich bitte um vorschläge, danke schon mal!
    Edit:

    Quellcode

    1. Java Code wird bevorzugt!!!!

  • Habe gerade ne Denkblockade.

    "Summe einer Menge natürlicher Zahlen ergibt genau 2008"
    Das ist klar. Beispiel: 2007 + 1

    "die Summe der Kehrwerte dieser Zahlen genau 1!"
    Der Kehrwert einer natürlichen Zahl ist doch ein Bruch mit dem Zähler=1...

    Muss der Nenner da nicht immer gleich sein? D.h. 1/2+1/2 oder 1/3+1/3+1/3
    X Info
    An alle Teilnehmer des
    Bundeswettbewerb Mathematik:
    "Ehrlichkeit währt am längsten."

  • "d0nut" schrieb:

    Muss der Nenner da nicht immer gleich sein?
    D.h. 1/2+1/2 oder 1/3+1/3+1/3


    Jein, gleich oder Vielfache voneinander, das würde ja auch gehen (z.B. 1/4 + 1/4 + 1/2). Ich knobel auch ml ne Runde und meld mich nochmal ;)

    "Deepestfear" schrieb:

    und jetzt ist eine Menge natürlicher zahlen gesucht für die das gilt (beliebig viele)!!!

    Die Anzahl der Kombinationen von natürlichen Zahlen, die aufsummiert die 2008 ergeben ist endlich. Das lässt naiv erstmal in Richtung Brute-Force denken. Allerdings muss es nicht zwingend eine Kombination geben auf die die zweite Bedingung zutrifft (Summe Kehrwert = 1). Soll heißen, für einige Zahlen gibt es keine Lösung.


    Kleiner Tipp für alle: 2008 hat eine ungünstige Primfaktorzerlegung (2³*251) ich würds erstmal mit ner kleineren ausprobieren.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • Moin!

    Frisch angemeldet und gleich nen alten Thread ausgegraben :)

    Diese Aufgabe scheint irgendwo in Mathematikerkreisen zu geistern. Leider findet man nicht viel, deswegen poste ich mal, falls es noch jemanden interessiert, meine bisherigen Ergebnisse.

    Habe ein Java Prog geschrieben, leider ist mein Ansatz nicht sehr effizient, er erfasst alle Lösungen, aber mit einer Zahl mit 46 Stellen an möglichen Kombinationen, für die einige Operationen zur Generierung und zur Überprüfung der Bedingung erforderlich sind, wird das wohl nicht vollst. zu berechnen sein.

    Idee meiner Lösung:

    Bilde alle Partitionen von 2008 (d.h. alle Möglichkeiten, 2008 als Summe von natürlichen Zahlen darzustellen). Damit habe ich die eine Bedingung direkt erfüllt, aber eben P( 2008 ) = 5913339135941752405965378691599572441324623941 Möglichkeiten. Ich habe im englisch sprachigen Raum einen Algorithmus gefunden, der lt. Untersuchung vom Autor relativ geringer Komplexität ist (Sieht für mich auch so aus). Die Berechnungszeit für einzelne Partitionen ist also nicht das Problem, nur die gesammte Anzahl an Möglichkeiten.

    Schließlich wird nur noch für jede gefundene Partition überprüft, ob die Summe der Kehrwerte = 1 ist, die Überprüfung wird abgebrochen, sobald 1 überschritten wurde. Denke mal, ich kann da auch nicht mehr viel optimieren.

    Der von mir verwendete Algorithmus fängt mit {2008} an, erzeugt dann {{2007},{1}} usw. - bin aber jetzt bei dem Ende der Rechenleistung nahezu angekommen, eine weitere Zahl dauert schon über 3 Stunden :) (habs nen Tag jetzt am Laufen, irgendwann muss ich wohl abbrechen)


    Ergebnisse bisher:

    found {1890,54,35,7,7,6,6,3}
    found {1890,54,30,14,7,5,5,3}
    found {1890,54,21,18,10,9,3,3}
    found {1890,54,21,15,10,10,6,2}
    found {1890,54,21,12,8,8,5,5,5}
    found {1890,54,15,14,14,14,5,2}
    found {1890,54,15,14,10,10,7,4,4}
    found {1890,54,14,12,12,10,7,6,3}
    found {1872,52,18,16,13,13,8,6,6,4}
    found {1872,39,16,13,13,13,12,9,9,8,4}
    found {1872,26,18,16,13,13,13,13,13,8,3}
    found {1870,66,17,17,15,10,5,4,4}
    found {1870,66,17,17,12,12,6,5,3}
    found {1870,42,17,17,12,11,11,8,8,7,5}
    found {1870,40,24,17,17,11,11,10,5,3}
    found {1870,40,17,17,11,11,10,10,10,8,4}
    found {1870,30,24,17,17,11,11,10,8,5,5}
    found {1870,30,24,17,17,11,11,8,8,8,4}
    found {1870,30,22,22,17,17,12,11,4,3}
    found {1870,30,17,17,15,12,12,11,11,10,3}
    found {1870,28,21,17,17,12,12,11,11,5,4}
    found {1870,24,24,17,17,15,11,11,10,5,4}
    found {1870,24,22,22,17,17,11,8,6,6,5}
    found {1870,24,20,17,17,15,12,11,11,8,3}
    found {1870,22,22,20,17,17,15,12,11,2}
    found {1870,22,22,20,17,17,11,10,10,5,4}
    found {1870,22,22,17,17,16,16,11,8,5,4}
    found {1870,20,20,20,20,17,17,11,11,2}
    found {1870,20,20,17,17,11,11,10,8,8,8,8}
    found {1870,20,17,17,15,15,11,11,10,8,8,6}
    found {1870,20,17,17,15,12,11,11,10,10,10,5}
    found {1870,18,17,17,15,15,11,11,10,10,9,5}
    found {1870,17,17,16,16,15,12,11,11,10,8,5}
    found {1870,17,17,14,14,14,14,14,11,11,7,5}
    found {1860,62,60,6,5,5,5,5}
    found {1860,62,40,24,8,8,3,3}
    found {1860,62,40,16,16,6,6,2}
    found {1860,62,40,12,12,8,6,4,4}
    found {1860,62,40,10,10,10,8,5,3}
    found {1860,62,36,18,12,6,5,5,4}
    found {1860,62,35,14,10,10,10,4,3}
    found {1860,62,33,22,11,6,5,5,4}
    found {1860,62,30,30,12,6,6,2}
    found {1860,62,30,28,14,7,5,2}
    found {1860,62,30,24,8,8,8,5,3}
    found {1860,62,30,20,20,10,4,2}
    found {1860,62,30,20,15,6,6,6,3}
    found {1860,62,30,12,9,9,9,6,6,5}
    found {1860,62,30,10,10,10,8,8,5,5}
    found {1860,62,30,10,10,8,8,8,8,4}
    found {1860,62,28,21,12,12,5,5,3}
    found {1860,62,28,20,14,10,7,4,3}
    found {1860,62,28,14,10,10,7,6,6,5}
    found {1860,62,28,14,9,9,9,7,5,5}
    found {1860,62,24,24,15,10,5,5,3}
    found {1860,62,24,24,15,8,8,4,3}
    found {1860,62,24,15,15,12,10,8,2}
    found {1860,62,24,15,14,8,7,7,7,4}
    found {1860,62,24,15,10,10,10,8,5,4}
    found {1860,62,20,20,10,9,9,9,5,4}
    found {1860,62,20,18,18,10,9,9,2}
    found {1860,62,20,18,12,12,9,5,5,5}
    found {1860,62,20,15,15,15,15,3,3}
    found {1860,62,20,15,12,12,12,6,5,4}
    found {1860,62,20,15,12,10,10,8,8,3}
    found {1860,62,20,12,12,12,12,10,4,4}
    found {1860,62,18,18,18,8,8,6,5,5}
    found {1860,62,18,15,15,10,9,8,8,3}
    found {1860,62,18,15,12,12,12,9,4,4}
    found {1860,62,16,16,16,16,6,6,5,5}
    found {1860,62,16,16,15,12,8,8,8,3}
    found {1860,62,15,15,15,12,10,10,6,3}
    found {1860,62,15,12,9,9,9,8,8,8,8}


    Die Lösungen sollten eigentlich passen, ich hab etwas gefuscht bei der Überprüfung, hab es nicht auf nen Hauptnenner gebracht sondern nur als double berechnet, bis jetzt aber keine Rundungsfehler :) (Hoffe mal, ich verliere keine Lösungen durch den Fusch, aber kann das Programm jetzt schlecht abbrechen und neu starten).

    Falls noch was kommt, werde den Thread hier noch ne Weile beobachten.

    Update: Hab den Code noch etwas optimieren können, bin etwas verschwenderischer mit double Zahlen umgegangen, also mehr Speicherbedarf, dafür wenigern Konvertierungen nötig. Und die überprüfende Funktion konnte ich noch etwas früher abbrechen lassen. Gefühlt 3 Mal schneller geworden :)

    Gruß Fred

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

  • So, Ende der Rechenleistung erreicht, hab gerade noch eine Zahl geraten, 1820 als grösste Zahl, das hat über einen Tag gedauert, alle Möglichkeiten zu berechnen :-/

    1848 88 24 14 12 8 6 4 4
    1848 88 14 12 12 8 8 6 6 6
    1848 84 22 14 14 11 8 4 3
    1848 84 22 11 8 8 8 7 6 6
    1848 66 33 24 14 11 4 4 4
    1848 66 33 14 12 11 8 6 6 4
    1848 56 28 22 14 14 11 6 6 3
    1848 56 24 22 12 11 8 7 7 7 6
    1848 44 44 22 22 14 8 3 3
    1848 44 42 33 21 8 4 4 4
    1848 44 24 14 12 11 11 11 11 8 8 6
    1848 42 33 24 21 11 11 11 4 3
    1848 42 28 24 22 11 7 7 7 6 6
    1848 42 28 22 21 21 11 8 4 3
    1848 42 24 22 22 22 14 7 4 3
    1848 42 24 22 21 12 12 11 6 6 4
    1848 42 24 22 14 14 14 11 8 8 3
    1848 42 22 22 22 14 14 14 8 2
    1848 42 22 21 12 12 11 8 8 8 8 8
    1848 42 22 14 14 14 14 11 8 7 7 7
    1848 33 28 28 24 12 11 11 11 2
    1848 33 28 24 12 11 11 11 8 8 7 7
    1848 33 24 24 24 14 11 11 11 4 4
    1848 33 24 24 14 12 11 11 11 8 6 6
    1848 33 21 21 14 14 12 11 11 11 8 4
    1848 33 14 12 12 12 12 12 12 11 11 11 8
    1848 28 28 28 22 21 12 11 8 2
    1848 28 28 22 21 12 11 8 8 8 7 7
    1848 28 24 24 22 21 14 11 8 4 4
    1848 28 24 22 21 14 12 11 8 8 6 6
    1848 28 24 22 14 14 12 12 12 11 7 4
    1848 28 21 14 12 11 11 11 11 11 11 11 8
    1848 24 24 24 24 22 14 11 8 6 3
    1848 24 24 24 22 22 22 14 6 2
    1848 24 24 24 22 14 14 11 7 7 7 6
    1848 24 24 22 21 21 11 8 8 8 7 6
    1848 24 22 22 22 21 21 12 7 6 3
    1848 24 22 22 22 14 12 12 12 8 8 4
    1848 22 22 22 21 14 14 14 12 8 7 4
    1848 22 21 14 14 14 14 14 12 11 8 8 8
    1840 80 23 23 20 10 4 4 4
    1840 80 23 23 10 10 10 10 2
    1840 80 23 23 8 8 8 8 5 5
    1840 46 46 23 20 16 10 5 2
    1840 40 40 23 23 20 16 4 2
    1840 40 23 23 20 20 16 10 8 4 4
    1840 40 23 23 20 16 16 16 5 5 4
    1840 23 23 20 20 20 20 16 8 8 5 5
    1840 23 23 20 20 16 16 16 16 16 2
    1840 23 23 20 20 16 10 10 10 10 10 8 8
    1840 23 23 20 16 16 16 10 10 10 8 8 8
    1840 23 23 16 16 16 16 16 10 8 8 8 8
    1820 91 35 26 14 10 4 4 4
    1820 91 28 26 14 10 10 7 2
    1820 70 65 20 13 7 5 4 4
    1820 70 65 14 14 13 4 4 4
    1820 70 28 26 14 13 13 7 7 5 5
    1820 70 26 20 20 13 13 10 7 5 4
    1820 70 26 20 14 14 13 13 10 4 4
    1820 65 35 35 20 13 5 5 5 5
    1820 65 35 28 14 13 7 7 7 7 5
    1820 65 35 28 13 10 10 10 7 5 5
    1820 65 35 20 20 13 10 7 7 7 4
    1820 65 28 28 28 20 13 4 2
    1820 65 28 28 20 13 10 7 7 5 5
    1820 65 28 28 14 14 13 10 7 5 4
    1820 65 28 26 26 10 7 7 7 7 5
    1820 65 28 20 20 14 13 10 10 4 4
    1820 65 26 26 20 14 14 14 7 2
    1820 65 20 14 14 14 14 14 13 10 5 5
    1820 52 52 20 14 13 13 7 7 5 5
    1820 52 52 14 14 14 13 13 7 5 4
    1820 35 35 26 26 26 20 13 5 2
    1820 35 28 26 14 14 14 13 13 10 7 7 7
    1820 35 28 26 14 14 13 13 10 10 10 10 5
    1820 35 26 20 20 20 13 13 10 10 7 7 7
    1820 28 28 28 26 26 26 13 5 4 4
    1820 28 28 28 26 20 20 13 13 10 2
    1820 28 28 26 20 14 14 13 13 10 10 7 5
    1820 28 28 26 14 14 14 14 13 13 10 10 4
    1820 28 26 26 26 20 20 14 13 5 5 5
    1820 28 26 26 26 14 14 13 10 10 7 7 7
    1820 28 26 26 26 14 13 10 10 10 10 10 5
    1820 28 26 20 20 20 20 13 13 7 7 7 7
    1820 28 26 20 20 20 14 13 13 10 10 10 4
    1820 26 26 26 26 26 20 14 7 7 5 5
    1820 26 26 26 26 26 14 14 14 7 5 4



    Also bis 1840 runter hab ich es regulär laufen lassen, danach nur noch geraten Hab das Programm mal nach C++ portiert, hab von C nicht so die Ahnung, aber läuft ungefähr halb so schnell wie das Java Prog (*stolz auf Java* aber *ärgerlich über C++*). Da sich keiner mehr meldet, werde ich wohl gleich mal ein paar PM's raushauen



    Gruß Fred

  • SeBa schrieb:




    d0nut schrieb:


    D.h. 1/2+1/2 oder 1/3+1/3+1/3

    Jein gleich oder Vielfache voneinander, das würde ja auch gehen (z.B. 1/4 + 1/4 + 1/2). Ich knobel auch ml ne Runde und meld mich nochmal ;)




    Scheint aber anders zu sein, siehe z.B.:

    1820 28 26 20 20 20 20 13 13 7 7 7 7

    Stelle gerade fest, oben stehen noch ein paar Zahlen drin, bei denen die kleineren Zahlen nicht Teiler der grossen sind - entweder ist mein Programm jetzt falsch, oder es war es am Anfang der Berechnung. Evtl. bin ich hier doch noch auf einen Rundungsfehler gestossen. Jedenfalls jetzt gibt das Prog nur noch Zahlen aus, die Teiler der grossen Zahl sind ...


    EDIT: Habe gerade mal nachgeguckt, meine Einschränkung, die kleineren Zahlen sollen Teiler der grossen sein ist offensichtlich falsch :( Naja, werde wohl eh nie alle Lösungen finden ...


    Gruß Fred

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von sfrederik ()

  • Hab den Algorithmus nochmal geändert, zum Glück kann ich ihn an einem gewünschten Startwert wieder beginnen lassen (ich gebe einfach als Anfangs-Partition z.B. {2000,8} mit der Summe 2008 an, und lasse ab da rechnen).


    Habe dann noch mal bei 1820 starten lassen, und siehe da, nach kurzer Zeit, eine neue Lösung:

    1820 = 2*2*5*7*13
    105 = 3*5*7
    39 = 3*13
    21 = 3*7
    12 = 2*2*3
    4 = 2*2
    4 = 2*2
    3 = 3

    Habe mal zur weiteren Überlegung (falls ein mathematisch Bewanderter dazu lusst hätte) die Primfaktorzerlegungen mit angegeben. Ausser das jeder Faktor wenigstens 2 Mal vorkommt, fällt mir da nich viel zu ein. Erst recht nichts, was die Berechnung effizient vereinfachen würde ... Achja, der Hauptnenner hier wäre 2*2*3*5*7*13 = 5460.

    Habe den Algorithmus jetzt so zurückgebaut, dass er wieder nur einfach mit Double Brüchen rechnet, jetzt läuft er wieder nen gutes Stück langsamer, aber dafür spuckt er mehr Lösungen aus. Und die kann man ja notfalls nochmal überprüfen, falls man an Rundungsfehler glaubt.

    Mich stört nur, dass die Geschwindigkeit jetzt wieder ein gutes Stück down ist. Aber Versuche mit auf Hauptnenner bringen (Stichwort ggT, kgV) waren noch viel viel langsamer als einfach stumpf die Double Brüche zu addieren.

    Evtl. könnte man jetzt durch die Idee mit den Startwerten daran denken, das ganze auf Threads bzw. Multiprocessor umzubauen, oder gleich distributed auf mehrere Rechner ...

    Ok, aber erstmal gucken, ob jemandem zum Programm nicht noch was einfällt. Mache den Quellcode mal schier, und bei Interesse wandert der hier rein.

    EDIT: Die Idee nur mit Double Brüchen war auch nich gut, habe gerade die ersten Rundungsfehler gesichtet. Als Workaround erweitere ich nun mit der grössten Zahl, die die meißten Primfaktoren enthält. Ich behaupte aber so natürlich nicht, alle Lösungen zu finden :(


    Gruß Fred

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von sfrederik ()

  • Ähm, wo siehst Du nen Rundungsfehler? Ich meinte mit Rundungsfehler nur, dass mir Lösungen durch die lappen gehen, weil beim Berechnen der Summe der Kehrwerte eben nicht genau 1.0 rauskommt. Die Lösungen, die ich bisher bestimmt hab (jedenfalls fast alle) habe ich händisch noch mal auf den Hauptnenner gebracht und addiert, das passte soweit.

    Demnach müssen also nicht alle Brüche aus den gleichen Primfaktoren zusammengesetzt sein. Stelle ich mal so in den Raum :)

  • 1820 28 26 20 20 20 20 13 13 7 7 7 7

    Erstens multiplizierst du da wohl anstatt zu addieren und zweitens komme ich nach mehrmaligen Rechnen nicht auf eins: 1/28 + 1/26 + 4/20 + 2/13 + 4/7 = 0.999540549 also nicht eins. Und auch bei allen anderen Kombinationen die du hier aufgelistet hast, kommt als Kehrwert nicht eins raus. Teilerfremde Brüche kannst du nie zu eins zusammenaddieren.

    Ich kann ja nochmal ein paar durchgehen:
    1820 = 2*2*5*7*13 -> 1/2 + 1/2 + 1/5 + 1/7 + 1/13 =1.419780219
    105 = 3*5*7 -> 1/3+1/5+1/7 = 0.67190476
    ...

    Da ich weiterhin an meiner Behauptung festhalte, gehe ich davon aus, dass kein einizger deiner "Lösungen" im Kehrwert 1 ergibt (ohne alle Überprüft zu haben).
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • Ups, ich glaube Du verwechselst da was.



    Die Aufgabe war: Summe aller gefunden Zahlen = 2008, die Summe der Kehrwerte dieser Zahlen = 1. Das ist für das von Dir bearbeitete Beispiel der Fall. Behaupte ich jedenfalls immernoch :)



    EDIT: die 1820 gehört zu der lösung dazu!



    D.H. 1820+28+26+20+20+20+20+13+13+7+7+7+7=2008



    Die Summe der Kehrwerte musste selber noch mal eben schauen, hatte ja den Hauptnenner schon angegeben :)



    EDIT: Ich glaube, die Primfaktorzerlegung hat Dich verwirrt. Ich habe hier nur Lösungen für 2008 geposted, wobei ich zu Testzwecken auch kleinere Zahlen ausprobiert hab.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von sfrederik ()

  • SeBa schrieb:

    1820 28 26 20 20 20 20 13 13 7 7 7 7

    Erstens multiplizierst du da wohl anstatt zu addieren und zweitens komme ich nach mehrmaligen Rechnen nicht auf eins: 1/28 + 1/26 + 4/20 + 2/13 + 4/7 = 0.999540549


    + 1/1820 und es sollte stimmen ...

    Ich lasse mich gerne eines besseren belehren. Danke schon mal SeBa für die Zeit.

    EDIT: Mist, warst wieder schneller *g*

    Problem ist halt wirklich, dadurch dass die kleineren Zahlen nicht Teiler der größten sind, dass ich keinen gescheiten Hauptnenner in kurzer Rechenzeit bekommen. Ich überlege schon, ob ich eine Fehlertoleranz (1.0001 bis 0.9999 oder so) zu lasse, jedoch fürchte ich, bekommt man dann viel zu viele falsche Lösungen. Gut, die könnte man dann immer noch relativ schnell mit "echter" Bruchrechnung überprüfen, aber irgendwie schmeckt mir das nicht ... - auf der anderen Seite, jetzt fährt das Programm an vielen Lösungen vorbei, weil eben nicht genau 1 rauskommt, hatte halt genau so einen Fall entdeckt, ich hatte eine Lösung, die aber vom Programm nicht (mehr) akzeptiert wurde - dabei hatte ich die Brüche nur in umgekehrter Reihenfolge aufaddieren lassen.

    Andere Idee war, eine Primfaktorzerlegung zu implementieren. Ich habe ja eine feste Menge an Zahlen (in diesem Fall von 1 bis 2008 ) -> Für die könnte man einmal beim Programmstart die Zerlegungen bestimmen. Dann müsste bei der Bruchadditionen nur noch die Primfaktorzerlegungen nachsehen, und die Primzahlen mit den jeweils grössten Exponenten multiplizieren, dann hätte man den Hauptnenner. Aber ob das ganze noch schnell genug ist, um viele Möglichkeiten durchzuprobieren?

    Sorry, wenn das ganze hier etwas chaotisch klingt, ich glaube, ich habe mich schon zu lange mit dem Kram beschäftigt :)

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

  • ok ehm wegen der beschleunigung deines programms hier mal eine idee (ich weiss net ob du des schon gemacht hast, wahrscheinlich hast du des aber schon so) :
    wenn dein prog so abläuft (also so hab ich es verstanden): 2007+1=2008; 2006+2=2008 .... dann müsste dein prog bei 1004+1004=2008 aufhören, dann gehts halt um einges schneller.

  • So, Quellcode gibts gleich noch :)

    Das mit der Primfaktorzerlegung für nen Hauptnenner wird auch irgendwie nich wirklich gut, da Fallen mir viel zu viele Operationen ein... Vllt. hab ich irgendwann dazu noch mal Lust, weil es ärgert mich schon, dass momentan Lösungen nicht als solche erkannt werden.

    @mioweber: Der Algorithmus läuft momentan so:

    {2008}->{2007,1}->{2006,2}->{2006,1,1}->{2005,3}->{2005,2,1}->{2005,1,1}->...

    Nun verstehe ich Deine Idee nicht, warum ich bei 1004 schon am Ende sein soll?

    Was mir vorhin noch eingefallen ist, ich könnte noch eine kleine Optimierung machen, die ich gleich noch mal einbaue. Danach gibts den Source, einmal hier (auch wenn etwas lang), dann zum Download.

    Gruß Fred

  • rapidshare.com/files/84375171/Suchen.zip.html

    Quellcode

    1. import java.util.Date;
    2. import java.text.SimpleDateFormat;
    4. /**
    5. * Diese Klasse sucht für die via Startparameter angegebene Zahl ihre möglichen Partitionen
    6. * und ermittelt dann die Summe der Kehrwerte der einzelnen Summanden in jeder Partition.
    7. * Ist diese Summe = 1, wird die gefundene Zahlenmenge ausgegeben. Zusätzlich wird als
    8. * Statusanzeige jeweils die erste Zahl der Partition nach Abschluss aller Partitionen die
    9. * mit dieser Zahl beginnen ausgegeben.
    10. *
    11. * @author Frederik Suhr
    12. * @version 1.01 17.01.2008
    13. */
    15. public class Suchen {
    16. /**
    17. * Diese Methode wird über die Kommandozeile mit zu untersuchender Zahl und ggf. einem Startwert versorgt
    18. *
    19. * Beispiel 1: Suchen 2008
    20. * Beispiel 2: Suchen 2008 1890
    21. * Beispiel 3: Suchen 10
    22. *
    23. * @param args zahl [optional Startwert)
    24. */
    25. public static void main(String[] args) {
    26. // Hier wird der Suchalgorythmus gestartet, wenn Paramter übergeben wurden.
    28. switch (args.length){
    29. case 1:
    30. if (Integer.parseInt(args[0]) != 0)
    31. zs1(Integer.parseInt(args[0]), Integer.parseInt(args[0]));
    32. break;
    34. case 2:
    35. if (Integer.parseInt(args[0]) != 0 && Integer.parseInt(args[1]) != 0)
    36. zs1(Integer.parseInt(args[0]), Integer.parseInt(args[1]));
    37. break;
    39. default:
    40. System.out.println("Fehler. Aufruf mit Paramter: Zu untersuchende Zahl [optional startwert]");
    41. break;
    42. }
    43. }
    45. /**
    46. * Diese Methode überprüft für ein Array von Zahlen ob die Summe der Kehrwerte vom Element sAnzahlZuPruefen
    47. * bis zum Element 1 gleich 1 ist. Wird 1 überschritten, bricht die Analyse ab.
    48. *
    49. * Die Rückwärtssuche bietet sich an, da das Array absteigend sortiert ist, d.h. die grössten
    50. * Brüche entstehen hinten. (Genial *g*)
    51. *
    52. * @param iZahl Array von zu untersuchenden Zahlen
    53. * @param sAnzahlZuPruefen selbst definierte obere Grenze des Arrays
    54. */
    55. private static void fktCheckZahl(int iZahl[], int sAnzahlZuPruefen) {
    57. // hier doch etwas fusch aber ohne die Erweiterung auf die grösste Zahl, die ja die meißten
    58. // Primfaktoren enthält, habe ich zuviele Lösungen durch Rundungsfehler verloren
    59. // und einfach das epsilon für einen vergleich runtersetzen ist mir auch irgendwie schwammig,
    60. // könnte man aber evtl machen, dann die möglichen kandidaten genau prüfen ... hmmm
    61. // analyse mit Epsilon durchführen, mögliche Lösungen dann genauer untersuchen (Hauptnenner)
    63. double hauptNenner = iZahl[1];
    65. double summeZaehler = 1.0; // iZahl[1] auf hauptNenner
    66. int k; //Zählvariable für zu prüfende Zahl
    69. if (iZahl[sAnzahlZuPruefen]==1) // wenn nich der triviale Fall {1} vorliegt, wird der bruch immer grösser 1
    70. return;
    72. for (k=sAnzahlZuPruefen;k>1;k--) {
    73. summeZaehler = summeZaehler + hauptNenner / (double)iZahl[k];
    74. if (summeZaehler > hauptNenner)
    75. return;
    76. }
    78. // Prüfe ob Summe der Kehrwerte gleich 1
    79. if (summeZaehler == hauptNenner) {
    80. System.out.println("found " + arrayPrint(iZahl,sAnzahlZuPruefen));
    81. }
    83. }
    86. /**
    87. * Partitionen erzeugen und auf gewünschte Eigenschaften überprüfen
    88. *
    89. * Algorithmus zs1 nach ANTOINE ZOGHBIU und IVAN STOJMENOVIC
    90. * (siehe http://www.site.uottawa.ca/~ivan/F49-int-part.pdf )
    91. *
    92. * @param n zu partitionierende Zahl
    93. * @param startWert bilde erste Partition anhand Startwert
    94. */
    95. private static void zs1(int n, int startWert) {
    97. SimpleDateFormat dateFormatter = new SimpleDateFormat("(dd.MM. HH:mm:ss)"); // Anzeigeformat festlegen
    99. System.out.println("Beginne Analyse von " + Integer.toString(n) + " absteigend ab "+ Integer.toString(startWert) +" " + dateFormatter.format(new Date()));
    101. if (n==1) {
    102. System.out.println("Trivialer Fall, Summe von {1} = 1 und der Kehrwert auch 1");
    103. System.exit(0);
    104. }
    107. int oldN; // Speicher für letzten Wert an Position 1 der Menge --> Ausgabe bei Änderung
    108. oldN = startWert;
    110. int xi[]=new int[n+1]; // hier finden alle Berechnungen statt, xi enthält die jeweils aktuelle Partition, +1 weil es sonst zu nem überlauf kaum, die letzte speicherstelle wird aber nicht wirklich benutzt!
    112. int m; // Anzahl Partitionen
    113. int h; // Index der letzten Zahl in der Partition grösser 1
    114. int r,t; // Variablen für Iteration ...
    116. int i; // Laufvariable Erstbefüllung mit 1en
    117. for (i=1;i<n+1;i++) {
    118. xi[i]=1;
    119. }
    122. xi[1] = startWert; // Startwert setzen
    124. if (startWert != n) {
    125. // erzeuge Partition der Form
    126. // {startWert,n-startWert}
    127. xi[2] = n - xi[1];
    128. m = 2;
    129. h = 2;
    131. // wenn xi[h] grösser als der Vorgänger, ausgleichen
    132. while (xi[h] > xi[h-1]) {
    133. r = xi[h] - xi[h-1];
    134. xi[h]-= r;
    135. h++;
    136. xi[h]= r;
    137. m++;
    138. }
    140. // neues h bestimmen: weil letzte stelle evtl gleich 1, vgl def von h
    141. while (xi[h] <= 1) {
    142. h--;
    143. }
    145. r=0;
    146. }
    147. else {
    148. // Partition gleich die Zahl selbst --> ermittle alle Partitionen
    149. m = 1;
    150. h = 1;
    151. }
    153. // hier beginnt der eigentliche Algorithmus zs1
    154. while (xi[1]!=1) { // da der zs1 absteigend iteriert, endet er, wenn die erste Zahl = 1 ist
    156. if (xi[h]==2) {
    157. m++;
    158. xi[h] = 1;
    159. h--;
    160. }
    161. else {
    162. r = xi[h] - 1;
    163. t = (m - h + 1);
    164. xi[h] = r;
    166. while (t >= r) {
    167. h++;
    168. xi[h] = r;
    169. t = t - r;
    170. }
    171. if (t == 0) {
    172. m = h;
    173. }
    174. else {
    175. m = h + 1;
    176. if (t > 1) {
    177. h++;
    178. xi[h] = t;
    179. }
    180. }
    181. }
    183. // zs1 hat eine neue Partition in xi erzeugt:
    185. if (oldN > xi[1]) { // erster Wert hat sich geändert, Lebenszeichen geben
    186. System.out.println("Alle Partitionen mit " + Integer.toString(oldN) + " als grösster Zahl überprüft. " + dateFormatter.format(new Date()));
    187. oldN = xi[1];
    188. }
    189. fktCheckZahl (xi, m); // Frage: Ist der Methodenaufruf langsam oder schnell, ggf. Überprüfung hier einfügen?
    190. }
    192. // Vollzug melden
    193. System.out.println("Alle Partitionen mit " + Integer.toString(oldN) + " als grösster Zahl überprüft. Fertig. " + dateFormatter.format(new Date()));
    194. fktCheckZahl (xi, m);
    195. }
    198. /**
    199. * Gibt das Array als Mengenklammer von seinen Elementen zurück
    200. *
    201. * @param arr Array von Zahlen
    202. * @param ub selbst definierte obere Grenze des Arrays
    203. * @return String der Form "{A1,A2,...,Aub}"
    204. */
    205. private static String arrayPrint(int arr[], int ub) {
    206. String str = "{";
    207. short i;
    208. for (i = 1;i <= ub; i++) {
    209. str = str + String.valueOf(arr[i]);
    210. if (i<ub) str = str + ",";
    211. }
    212. str = str + "}";
    214. return str;
    215. }
    216. }
    Alles anzeigen