Project Euler Nr. 13

[pudeldestodes]

Eigentlich ist das kein Pythonproblem, aber da hier schon einmal andere Threads mit ähnlichem Thema standen, hoffe ich, dass es passt.

Eines der Probleme (Nr. 13) von Project Euler beschäftigt sich mit dem Addieren mehrerer großer Zahlen. Es gibt 100 Zahlen mit jeweils 50 Ziffern. Gefragt ist nach den ersten zehn Ziffern der Summe dieser hundert Zahlen.

Im zugehörigen Lösungsthread behaupten manche, man müsse nur einfach die Teilzahlen aus den ersten 11. Ziffern bilden und aufeinander addieren (das geht bei den in diesem Fall gegebenen Zahlen, ist aber für den allgemeinen Fall meiner Meinung nach falsch), oder aber man müsse auf jeden Fall alle Ziffern in Betracht ziehen. Leider gibt es zu dem Problem keine erklärende Lösungsdatei.

Ich habe mich an einem Lösungsansatz versucht, weiß aber nicht, ob das wirklich verallgemeinert richtig ist.

Ich rechne mit dem Additionsschema aus der 1. Klasse - allerdings von links nach rechts.

Angenommen ich habe für *fünf* hunderstellige Zahlen die ersten Ziffern jeder Zahl aufeinander addiert:
13
Es soll die erste Ziffer des Ergebnisses herausgefunden werden. Wie viele zusätzliche Ziffern muss ich berechnen, damit sich die erste Ziffer (derzeit die 1) nicht mehr ändert?

Meine Idee:
bei fünf Zahlen kann bei der nächsten Ziffer maximal 9*5=45 hinzukommen. Damit sich die '1' nicht ändert, muss 99 - '3' * 10 >= 45 sein. Dementsprechend könnte ich hier abbrechen.

Die Frage: stimmt das? Ich habe jetzt kein Gegenbeispiel gefunden, aber das will ja nichts heißen. Aus meiner Schulmathematik habe ich mal die vollständige Induktion hervor gekramt, bin aber kläglich gescheitert (keine Ahnung, ob das überhaupt das richtige Mittel zum Beweis wäre).

Mein Lösungsskript:http://paste.pocoo.org/show/195019/
Die Zahlen: http://paste.pocoo.org/show/195022/

[hendrikS]

Verstehe nicht wo Dein Problem ist. Lies die Zahlen ein und addiere sie.
Bsp. für die ersten beiden:

Code: Alles auswählen

a = "37107287533902102798797998220837590246510135740250"
b = "46376937677490009712648124896970078050417018260538"
print int(a)+int(b)

[LanX]

Im zugehörigen Lösungsthread behaupten manche, man müsse nur einfach die Teilzahlen aus den ersten 11. Ziffern bilden und aufeinander addieren

das ist falsch, es reichen die ersten 10 Ziffern aufzuaddieren, und du bekommst bei 100 Additionen maximal eine 12 stellige Zahl heraus.

Das sind pi mal Daumen 40bit die du zur Darstellung dieser brauchst, das sollten heutzutage alle Sprachen fehlerfrei können.

Falls du Probleme hast es dir zu erklären, wenn du vom Aldi nen Kassenbeleg mit 100 Posten hast werden die 2 Nachkommastellen sich auch nur aus den addierten Cents ergeben und nicht den Euros.

[BlackJack]

@hendrikS: Das Problem ist, dass Euler-Probleme mit Mathe zu tun haben, und auch wenn man etwas "brute force" lösen kann, dort eher nach "mathematisch intelligenten" Lösungen gesucht werden soll und nicht nach "ach Rechner können das heute schon problemlos". Also eine Lösung, die man auch mit Papier und Bleistift hinbekommt ohne einen Monat addieren zu müssen.

@pudeldestodes: Den Kommentar mit dem Aldi-Kassenbon verstehe ich nicht. Das die Cents nicht von den Euro's beeinflusst werden ist klar -- die Frage ist doch eher andersherum: Wieviele Stellen von den Euros können die Cents bei `n` Additionen maximal beeinflussen.

[HWK]

das ist falsch, es reichen die ersten 10 Ziffern aufzuaddieren

Das stimmt nicht. Gegenbeispiel:
Bei allen 100 Zahlen die erste Ziffer 1, die nächsten 8 Ziffern 0, die letzten 40 Ziffern 9. Die 10. Ziffer bei 99 Zahlen 0, bei einer Zahl 1.
Würde man nur die ersten 10 Ziffern betrachten, käme 10**9 heraus. Das korrekte Ergebnis ist aber 10**9 + 1.
MfG
HWK

[LanX]

@pudeldestodes: Den Kommentar mit dem Aldi-Kassenbon verstehe ich nicht. Das die Cents nicht von den Euro's beeinflusst werden ist klar -- die Frage ist doch eher andersherum: Wieviele Stellen von den Euros können die Cents bei `n` Additionen maximal beeinflussen.

OK, das sind 2 verschiedene Fragen ...

bei der Originalaufgabenstellung " Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. reichen 10 statt 11 Ziffern wen einen das rechte Ende interessiert.

Interessiert das linke Ende braucht man im Allgemeinen alle Ziffern weil man immer einen Übertrag konstrieren kann wo sich die niedrigste Ziffer auswirkt.

Das wäre z.B. anders wenn bekannt ist dass alle Summanden an einer bestimmten Stelle mindestens 2 Nullen hätten.Das würde den Übertrag der weiter rechts liegenden Stellen ausbremsen.
also bei hundert Zahlen der Form: (L[0],L[1],..,L[n], 0, 0, R[0]..R[m] ), würde es reichen die ersten n Stellen zu betrachten, weil die Summe der rechten Ziffern nach 100 Additionen niemals die n-te Stelle erreichen können.

[BlackJack]

@LanX: Na bei Projekt Euler darf man schon davon ausgehen das nicht sowas triviales wie die rechten 10 Ziffern gefragt sind.

[LanX]

@LanX: Na bei Projekt Euler darf man schon davon ausgehen das nicht sowas triviales wie die rechten 10 Ziffern gefragt sind.

Bei euler gibts die unterschiedlichsten niveaus, damit auch Anfänger nen Einstieg finden.

Du kannst die aufgaben auch irgendwo so ranken lassen. ... ja gehört zu den 15 einfachsten Aufgaben überhaupt.


Du meinst also mit first digits sind die 10 höchsten gemeint??? Seltsamer Sprachgebrauch...

Aber tatsächliche die 10 höchstwertigsten Ziffern waren gefragt, hab die Antwort schnell getestet.

[LanX]

Das wäre z.B. anders wenn bekannt ist dass alle Summanden an einer bestimmten Stelle mindestens 2 Nullen hätten.Das würde den Übertrag der weiter rechts liegenden Stellen ausbremsen.
also bei hundert Zahlen der Form: (L[0],L[1],..,L[n], 0, 0, R[0]..R[m] ), würde es reichen die ersten n Stellen zu betrachten, weil die Summe der rechten Ziffern nach 100 Additionen niemals die n-te Stelle erreichen können.

OK jetzt wo ich die Aufgabenstellung verstehe, hab ich müll erzählt.

Aber die skizzierte Argumentation reicht um klarzustellen das man links jeweils 12 Ziffern braucht (hier also n=9 + 2weitere Ziffern).

R[0] wären die 13ten Ziffer und könnten sich unmöglich noch auf die 10 stelle auswirken.

UPDATE:
OK um nachmal die Euro/Cent analogie zu bemühen, wenn ich hundert Geldbeträge aufaddiere und mich an der Summe nur der Betrag über hundert Euro interessiert, kann ich die Cents ignorieren.

Weil die Centbeträge alle unter 1 Euro liegen liegt ihre Summe folglich auch unter 100 Euro und hat keinen Einfluss!

[mkesper]

Naja, auf jeden Fall ist das Problem in Python keines...

[BlackJack]

@LanX: Das mit dem seltsamen Sprachgebrauch kann ich überhaupt nicht finden. Wenn mir jemand sagt, das bei 123 die drei die *erste* Ziffer sei, fände ich das viel seltsamer. Ich gehe jedenfalls davon aus, dass die Frage von Personen gestellt wurde, in deren Kulturkreis im allgemeinen von links nach rechts gelesen wird.

[LanX]

@LanX: Das mit dem seltsamen Sprachgebrauch kann ich überhaupt nicht finden. Wenn mir jemand sagt, das bei 123 die drei die *erste* Ziffer sei, fände ich das viel seltsamer. Ich gehe jedenfalls davon aus, dass die Frage von Personen gestellt wurde, in deren Kulturkreis im allgemeinen von links nach rechts gelesen wird.

Vielleicht verstört ein Mathestudium. xD

Die erste Stelle ist für mich 10^0 wertig, die zwote 10^1 wertig usw.

Ich wette auch mal dass ein Großteil der Mathematiker die Aufgabenstellung nicht ohne Rückfrage verstehen würden.

Vielleicht liegts daran dass es "Arabische Ziffern" sind und die Arabische Schrift von rechts nach links geht.

[BlackJack]

@LanX: Also ich bin beim Inf-Studium ja auch ein wenig mit Mathematikern in Kontakt gekommen und ich glaube nicht, dass das einer von denen so verstanden hätte. Nicht bei *der* Aufgabenstellung. Es hätte vielleicht Rückfragen gegeben wenn die Zahlen in der Aufgabe als Polynom dargestellt gewesen wären, aber bei ganz normalen Zahlen mit arabischen Ziffern zur Basis 10 sind die ersten Ziffern IMHO auch bei Mathefreaks links. Wer da nachfragt ist in der Regel einfach nur ein Klugscheisser der unbedingt zeigen will dass man das auch "präziser" ausdrücken kann, aber ganz genau weiss was gemeint war.

[LanX]

Wer da nachfragt ist in der Regel einfach nur ein Klugscheisser

Zugegeben Mathematiker sind penibel, manche auch nervige Klugscheisser ...

Aber ich find die Aufgabenstellung unzureichend, ein einfaches "leftmost" hätte gereicht.

Anyway dass ist schon recht offtopic!

[pudeldestodes]

OK um nachmal die Euro/Cent analogie zu bemühen, wenn ich hundert Geldbeträge aufaddiere und mich an der Summe nur der Betrag über hundert Euro interessiert, kann ich die Cents ignorieren.

Weil die Centbeträge alle unter 1 Euro liegen liegt ihre Summe folglich auch unter 100 Euro und hat keinen Einfluss!

Wieso? Wenn ich nur die "Eurostellen" der einhundert Zahlen addiere mag 99999,00€ herauskommen. Durch die vernachlässigten Centbeträge können noch 0.99€*100 = 99€ dazukommen -> hier wird sogar die 10000er Stelle beeinflusst.

@pudeldestodes: Den Kommentar mit dem Aldi-Kassenbon verstehe ich nicht. Das die Cents nicht von den Euro's beeinflusst werden ist klar -- die Frage ist doch eher andersherum: Wieviele Stellen von den Euros können die Cents bei `n` Additionen maximal beeinflussen.

Ehrlich gesagt weiß ich gerade nicht, welchen Kommentar du meinst (Aldi-Kassenbon?). Eigentlich war es genrell so gemeint, wie du schreibst (Centstellen können eventuell Eurostellen beeinflussen). Ich versuche mich nochmal an einer Erklärung:
Fünf gegebene Zahlen:
9234, 5678, 9012, 9456, 7890
Ich will die erste Ziffer des Ergebnisses der Summation dieser Zahlen herausfinden.

Also addiere ich die ersten Ziffern:
9 + 5 + 9 + 9 + 7 = 39
Bei *fünf* Zahlen können durch die Summation der zweiten Ziffern maximal 9*5 = 45 addiert werden. Im schlechtesten Fall muss ich also 45 auf 390 (39*10 (da nächste Ziffer)) addieren. Damit die '3' (erste Ziffer meines "Teil"ergebnisses) stehen bleibt, muss nun 99 - 90 (die neunzig aus den 3'90') >= 45 sein. Das ist offensichtlich nicht erfüllt, also darf ich noch nicht abbrechen und muss die nächste (2.) Ziffer der gegebenen Zahlen berechnen:
2 + 6 + 0 + 4 + 8 = 20
also erhalte ich als Zwischenergebnis nun: 390 + 20 = 410
Muss ich die nächste Ziffer auch noch berechnen, oder bleibt die '4' meines Teilergebnisses auf jeden Fall stehen? Im schlechtesten Fall müssen wieder 45 hinzuaddiert werden, und zwar zu 410 * 10 = 4100.
Damit sich die 4 nicht ändert, muss 999 - 100 >= 45 sein. Das ist erfüllt, und ich kann abbrechen.

Hm, leider kann ich das nicht präziser ausdrücken.

[LanX]

Wieso? Wenn ich nur die "Eurostellen" der einhundert Zahlen addiere mag 99999,00€ herauskommen. Durch die vernachlässigten Centbeträge können noch 0.99€*100 = 99€ dazukommen -> hier wird sogar die 10000er Stelle beeinflusst.

ich bin langsam selbst verwirrt, aber du hast recht! Alleine deine Beispielzahlen stimmen nicht ganz, 99999 sind nicht möglich.

wenn du 99 mal 899€ und ein mal 998€ addierst bekommst du 89999. Das heißt bereits eine Übertrag von 1 € in den Centbeträgen ändert das Ergebnis an allen Stellen.

Ich denke dein Ansatz stimmt, man muss von links nach rechts immer mehr Stellen in die Addition mit aufnehmen bis man rechts ein Ergebnis hat wo jedweder mögliche Übertrag der ausgelassenen Stellen keinen Einfluss auf die relevanten Stellen hat.

Konkret so sieht die Summe aus wenn man die höchsten 10 -13 Stellen mit aufnimmt

10: abcdefgh2992
11: abcdefgh30342
12: abcdefgh303860
13: abcdefgh3039036

(der Fairness halber hab ich die höchsten 8 Ziffern maskiert)

man sieht 10 stellen reichen nicht weil 92+99 das Ergebnis ändern könnten.
aber schon bei 11 stellen würden 342+99 keinen Einfluss mehr haben.

so hoffe ich liege diesmal nicht mehr daneben.

[pudeldestodes]

Gerade wollte ich schreiben, dass ich nach erneutem Nachdenken der Meinung bin, dass mein Ansatz eigentlich falsch ist, als ich deinen Beitrag gelesen habe - aber jetzt ist es zu spät, so dass ich mir morgen nochmal den Kopf über deine Anmerkung zerbrechen werde (nicht, dass das von unbedingt Erfolg gekrönt sein sollte, aber es macht trotzdem Spaß...).