Python Aufgabe

Hallo, ich versuche mich gerade an ProjectEulerś Aufgabe 145 um Python zu lernen:

es geht darum die Anzahl aller positiven Ganzzahlen zu finden für die gilt:
Zahl + Zahl(umgedreht) besteht nur aus ungeraden Ziffern:

Ich habe ein kleines skript geschrieben:

count = 0

def reverseString(s):
    l = list(s)
    l.reverse()
    return "".join(l)

def isOdd(i):
    l = list(i)
    for j in l:
        j = int(j)
        if j != 1 and j != 3 and j != 5 and j != 7 and j != 9 :
            return False
    return True

for i in range(1, 1000000000):
    print i
    if not i% 10 == 0:
        summe = i + long(reverseString(str(i)))
        if isOdd(str(summe)):
            count += 1
print count

wenn ich es bis 1000 laufen lasse, bekomme ich ohne Probleme das richtige Ergebnis (120) aber bei 1000000000 als Grenze tut sich einfach gar nichts

IDE: Eric

woran liegt das?

Christoph

Von 1000 auf eine Milliarde hochzugehen ist ein ziemlich großer Sprung. Hast du mal gemessen, wie lange dein Programm bei 10000, bei 100000 oder bei 1000000 braucht? Wenn es bei 1000000 zum Beispiel schon eine halbe Minute braucht, dann ist klar, dass es bei 1000000000 mindestens 1000 Mal so lange brauchen wird.

edit: Statt range(1, 1000000000) wäre xrange(1, 1000000000) deutlich speichersparender.

hmm mir ist das durchaus bewusst, dass es lange dauern kann:

aber bei 10^8 bekomme ich noch meine ausgaben

in der schleife hab ich ja deswegen das print i...
daran sollte ich doch erkennen können ob er was tut, oder?

Ich erhalte ab 10^9 aber nichts mehr, kein einziges lebenszeichen...

borg

Christoph hat dir doch schon gesagt was das Problem ist:

>>> range(1, 1000000000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
MemoryError

range(1, 1000000000) erzeugt eine liste mit 10^9 32 bit Werten, das ist einfach zuviel. Mit xrange statt range funktioniert dein Programm problemlos.

ok das war gut so^^

aber mal anders rangegangen:

wie könnte ich das programm verbessern?

müssen die vielen typumwandlungen sein oder geht es vielleicht einfacher?

nevermore

z.B. in der Funktion isOdd:

1. Brauchst du deine Zahl nicht in eine Liste umzuwandeln. Teile durch 10 und schaue dir den Rest an. Damit erhältst du jeweils die letzte Ziffer.

2. Anstatt auf 1,3,5,7,9 zu überprüfen, kannst du auch durch 2 teilen und schauen, ob ein Rest übrig bleibt.

Stichwort: Modulo %

EDIT: Und das Umdrehen der Zahl kannst du auch manuell machen mit nem int-Wert. Schneide z.B. immer die letzte Ziffer ab und addiere sie dann wieder in der entsprechenden 10-er Potenz dazu...

Grüße

borg

shisha schrieb:

wie könnte ich das programm verbessern?

Du kannst das Problem mathematisch analytisch lösen, es gibt ne geschlossene Formel für alle n.

na ^^
ich mach alles ohne zu denken, mir gehts vor allem darum pythin ein wenig kennen zu lernen.

Aber danke für den tipp vielleicht schau ichs mir ja nochmal unter den gescihtspunken an ^^