projecteuler.net Problem 5

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.
Antworten
Benutzeravatar
Klip
User
Beiträge: 98
Registriert: Donnerstag 10. August 2006, 20:39

Hallo zusammen,

vielleicht kennen einige von euch die Seite projecteuler.net. Dort werden Matheprobleme aufgelistet, die man durch ein selbst geschriebenes Programm lösen soll.

Ich hänge im Moment am fünften Problem, welches wie folgt lautet:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
Dazu habe ich diesen Code geschrieben, der jedoch keine Zahl findet, auf die alle Kriterien passen. Da muss irgendwo ein Logikfehler sein, aber ich sehe ihn einfach nicht! Hat da wer einen Tipp?

Code: Alles auswählen

#!/usr/bin/env python

number = range(20,9000000)
divisor = range(1,21)
successful = 0

for i in number:
	successful = 0
	for x in divisor:
		if i % x == 0:
			successful += 1
		elif i % x != 0:
			break
		if successful == 20:
			print i
			quit()
Gedacht habe ich mir das folgendermaßen:
number ist eine Liste, die alle potentiell gesuchten Zahlenn durchgeht. divisor enthält die Zahlen, durch die number geteilt werden soll.
In einer doppelten for-Schleife gehe ich beide Listen durch und prüfe, ob die Zahl number durch divisor ohne Rest teilbar ist. Wenn ja, zähle ich die Variable successful einen Wert nach oben. Erreicht dieser Wert 20, ist number durch alle 20 Divisoren teilbar und somit die gesuchte Zahl.
Bei jedem neuen Wert für number wird successful wieder zurück auf null gesetzt.

Aber wie gesagt, es tut sich nichts. Wenn ich die Bandbreite von number höher schraube, rechnet mein PC nicht mehr sondern hängt sich auf. Ich glaube aber auch nicht, dass die Zahl so groß ist.

Hat jemand eine Idee?
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Doch, die Zahl ist sogar noch größer. Das kann man mit einem Taschenrechner einfach und v.a. schnell ausrechnen. Dein Code ist prinzipiell richtig, aber sehr umständlich. Ich würde ihn etwas pythonischer so formulieren:

Code: Alles auswählen

number = range(...)
divisor = range(...)
for i in number:
    for x in divisor:
        if i % x != 0:
            break
    else:
        print i
        break
Ist aber natürlich sehr langsam. Wie gesagt: Taschenrechner und logisches Denken sind schneller.
MfG
HWK
Benutzeravatar
Klip
User
Beiträge: 98
Registriert: Donnerstag 10. August 2006, 20:39

Oh ich wusste gar nicht, dass das mit der Einrückung auch so funktionieren kann. Wieder was gelernt.

Danke! Dein Code ist tatsächlich weniger umständlich :)

Mein Problem ist, dass ich in Mathe ziemlich schlecht bin. Ich glaube,, mit logischem denken und einem Taschenrechner komme ich nicht sonderlich weit.

Aber wenn es möglich ist, hmm... ich muss mich da nochmal mit beschäftigen.

Vielen Dank jedenfalls schonmal für den Tipp! Ich dachte, ich habe irgendeinen Fehler im Code und war schon ganz verzweifelt.
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

hier z.B. mal eine Version mit konstantem Speicherverbrauch:
http://paste.pocoo.org/show/84052/
Benutzeravatar
Klip
User
Beiträge: 98
Registriert: Donnerstag 10. August 2006, 20:39

Danke audax,

leider verstehe ich einen großen Teil deines Codes nicht =/

Ich habe es jetzt unelegant gelöst. Mein PC hat etwa 3 Minuten gebraucht um an das Ergebnis zu kommen, aber immerhin hat es geklappt.

Code: Alles auswählen

#!/usr/bin/env python

number = 2520
divisor = range(1,21)
success = 0

while success != 20:
	success = 0
	for x in divisor:
		if number % x == 0:
			success += 1
		else:
			break
	number += 1
print number
Ich habe mal was im Netz gestöbert und bin dabei über lcm gestolpert, damit würde es bedeutend schneller gehen denke ich.
Benutzeravatar
Trundle
User
Beiträge: 591
Registriert: Dienstag 3. Juli 2007, 16:45

Klip hat geschrieben:Ich habe mal was im Netz gestöbert und bin dabei über lcm gestolpert, damit würde es bedeutend schneller gehen denke ich.
In der Tat.
"Der Dumme erwartet viel. Der Denkende sagt wenig." ("Herr Keuner" -- Bertolt Brecht)
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Ausserdem: Für Euler gilt dasselbe wie für die python challenge ... doch bitte keine Lösungen online posten ;) Das nimmt den Leuten doch den Spass am tüfteln.

Und wenn du große Listen brauchst, was hier nicht der fall ist, aber es nicht direkt als Liste benötigst, dann nimm die Generator_variante von `range' : `xrange'
BlackJack

Wenn man `lcm` nicht selbst implementieren möchte, dann bietet das `gmpy`-Modul eine entsprechende Funktion.

Oder man nimmt gleich Haskell, da gehört's zum Lieferumfang. :-)

Code: Alles auswählen

foldl lcm 1 [1..20]
Antworten