Project Euler Nr. 13

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
pudeldestodes
User
Beiträge: 65
Registriert: Samstag 9. Juni 2007, 23:45

Montag 29. März 2010, 00:01

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/
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Montag 29. März 2010, 00:48

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
User
Beiträge: 92
Registriert: Samstag 20. Februar 2010, 12:46

Montag 29. März 2010, 01:25

pudeldestodes hat geschrieben: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

Montag 29. März 2010, 06:50

@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.
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Montag 29. März 2010, 11:33

LanX hat geschrieben: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
User
Beiträge: 92
Registriert: Samstag 20. Februar 2010, 12:46

Montag 29. März 2010, 12:24

BlackJack hat geschrieben:@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

Montag 29. März 2010, 12:39

@LanX: Na bei Projekt Euler darf man schon davon ausgehen das nicht sowas triviales wie die rechten 10 Ziffern gefragt sind. :roll:
LanX
User
Beiträge: 92
Registriert: Samstag 20. Februar 2010, 12:46

Montag 29. März 2010, 13:34

BlackJack hat geschrieben:@LanX: Na bei Projekt Euler darf man schon davon ausgehen das nicht sowas triviales wie die rechten 10 Ziffern gefragt sind. :roll:
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
User
Beiträge: 92
Registriert: Samstag 20. Februar 2010, 12:46

Montag 29. März 2010, 13:39

LanX hat geschrieben: 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!
Benutzeravatar
mkesper
User
Beiträge: 919
Registriert: Montag 20. November 2006, 15:48
Wohnort: formerly known as mkallas
Kontaktdaten:

Montag 29. März 2010, 13:58

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

Montag 29. März 2010, 15:13

@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
User
Beiträge: 92
Registriert: Samstag 20. Februar 2010, 12:46

Montag 29. März 2010, 21:34

BlackJack hat geschrieben:@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

Montag 29. März 2010, 22:17

@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
User
Beiträge: 92
Registriert: Samstag 20. Februar 2010, 12:46

Montag 29. März 2010, 22:25

BlackJack hat geschrieben:Wer da nachfragt ist in der Regel einfach nur ein Klugscheisser
Zugegeben Mathematiker sind penibel, manche auch nervige Klugscheisser ... :D

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

Anyway dass ist schon recht offtopic!
pudeldestodes
User
Beiträge: 65
Registriert: Samstag 9. Juni 2007, 23:45

Montag 29. März 2010, 23:53

LanX hat geschrieben: 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.
BlackJack hat geschrieben:@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.
Antworten