Special Pythagorean Triplet (Project Euler Problem 9)

[HarteWare]

Hallöchen zusammen,

edit: Es "funktioniert" jetzt. Wenn jemand tipps hat, wie es auch geht, ohne mehrere Minuten darauf zu warten, nur her damit.
Bin leider nicht ganz so fit, um selber auf solche Optimierungen zu kommen.

edit2: ok, stimmt ja, nach Lösen des Problems kann man die Lösungen der Anderen sehen. Mist... mal wieder zu früh gepostet und einen Thread umsonst erstellt, entschuldigt....

ich bräuchte mal wieder etwas Hilfe. Ich versuche jene Aufgabenstellung zu lösen:

Code: Alles auswählen

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a*a + b*b = c*c

For example, 3*3 + 4*4 = 9 + 16 = 25 = 5*5.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Mein dafür entwickeltes Programm produziert kein Resultat, also wird wohl irgendwo ein Fehler sein. (Sprich: alles bleibt auf den default Werten 0)

Ich habe versucht alle Bedingungen in der Aufgabe umzusetzten, aber wie gesagt, irgendwo ist ein Denkfehler oder Sonstiges.

Vielleicht kann mal jemand für mich drüber schauen:

Code: Alles auswählen

def is_pyth_triplet(a, b, c):
    if not (a < b and b < c):
        return False
    return a*a + b*b == c*c

def main():
    result = 0
    a = 0
    b = 0
    c = 0
    for i in range(1000):
        for j in range(1000):
            for k in range(1000):
                if is_pyth_triplet(i, j, k) and a + b + c == 1000: # muss heißen i + j + k == 1000
                        a = i
                        b = j
                        c = k
                        result = a * b * c

    print("Result:", a, '*', b, '*', c, '=', result)

if __name__ == "__main__":
    main()

Ich bin mir im Übrigen darüber im Klaren, dass der Code nicht der schönste ist und dass rein technisch gesehen der Ansatz nicht der Beste ist,
aber etwas anderes als Bruteforce fällt mir grad nicht ein. Wenn der Ansatz dann mal passt, kann ich auch mit Sachen wie all()/ any() etc. das ganze "schöner machen" oder "verbessern".
Wenn jemand in die Richtung 'Mathematischer Ansatz' Tipps hat, wäre ich auch recht dankbar.

LG
HarteWare

[BlackJack]

@HarteWare: Warum hantierst Du da mit `i`, `j`, und `k` *und* `a`, `b`, und `c`? Dieser zweite Satz an Namen macht irgendwie keinen Sinn für mich.

Statt zu prüfen ob a < b < c gilt, könntest Du auch gezielt nur solche Zahlen aufzählen.

Da es laut Aufgabenstellung nur einen Treffer geben kann, braucht man wenn man *den* gefunden hat, nicht noch die ganzen restlichen Zahlen-Tripel durchprobieren.

[HarteWare]

Also dann in etwa so? Das zweite Set war halt, damit ich die einzelnen Zahlen "speichern" kann und später ausgeben.
Ich habs jetzt mal anders versucht, weiß nicht ob diese Lösung (mit exit(1)) so gut ist (mein Gefühl sagt eher nicht).
P.S.: Das "geziehlt nur solche Zahlen aufzählen" hab ich mir abgeschaut, da wär ich nie drauf gekommen^^

Code: Alles auswählen

def main():
    for a in range(1, 1000):
        for b in range(a + 1, 1000):  # b > a
            c = 1000 - a - b   # a + b + c = 1000
            if a*a + b*b == c*c:   # and c > b ?
                print("Result:", a, '*', b, '*', c, '=', a * b * c)
                exit(1)

if __name__ == '__main__':
    main()

Ich frage mich aber, ob ich nicht noch prüfen müsste (rein theoretisch) ob c dann auch größer als b ist. Also es funktioniert zwar so, aber das könnte ja auch nur Zufall sein.

Eine Sache ist klar - das Programm läuft vermutlich 20 mal so schnell. Wenn nicht mehr. Also vielen Dank erstmal.

[EyDu]

Dein Ansatz stimmt so nicht, das c wird in vielen Fällen negativ.

Das Auschließen der Zahlen solltest du besser auch konsequent durchziehen. Als erstes sollte dir auffallen, dass a gar nicht den Wert 999 erreichen darf, da es dann für b und c keine gültige Belegung mehr gibt. Mal ganz davon abgesehen, dass a < b < c gelten soll.

Dann solltest du noch bedenken, dass sich auch für b Einschränkungen aus dem Wert von a ergeben. b soll größer sein als a und die Summe aus a und b muss < 1000 sein.

Deine Lösung mit exit ist in der Tat keine gute Lösung, gleich aus Gründen. Ein einfaches return tut es hier nämlich auch. Außerdem deutet der Wert des Parameters für exit an, dass ein Fehler im Programm aufgetreten ist.

[HarteWare]

Hi,

vielen Dank für deine Rückmeldung. Ich habe versucht gemäß deiner Hinweise meinen Algorithmus anzupassen.
Ich habe nun eine Testausgabe mit der Grenze 10 erstellt, damit diese Bedingungen überprüft werden können:
(0|-1) < a < b < c und a + b + c <= 10
Soweit ich erkennen kann, erreicht der Code das.

Code: Alles auswählen

def main():
    for a in range(10):  # ob 0 oder nicht ist ja "umstritten"
        for b in range(a + 1, 10):
            for c in range(b + 1, 10 - a - b + 1):
                print(a, '+', b, '+', c, '=', a + b + c)

Code: Alles auswählen

0 + 1 + 2 = 3
0 + 1 + 3 = 4
0 + 1 + 4 = 5
0 + 1 + 5 = 6
0 + 1 + 6 = 7
0 + 1 + 7 = 8
0 + 1 + 8 = 9
0 + 1 + 9 = 10
0 + 2 + 3 = 5
0 + 2 + 4 = 6
0 + 2 + 5 = 7
0 + 2 + 6 = 8
0 + 2 + 7 = 9
0 + 2 + 8 = 10
0 + 3 + 4 = 7
0 + 3 + 5 = 8
0 + 3 + 6 = 9
0 + 3 + 7 = 10
0 + 4 + 5 = 9
0 + 4 + 6 = 10
1 + 2 + 3 = 6
1 + 2 + 4 = 7
1 + 2 + 5 = 8
1 + 2 + 6 = 9
1 + 2 + 7 = 10
1 + 3 + 4 = 8
1 + 3 + 5 = 9
1 + 3 + 6 = 10
1 + 4 + 5 = 10
2 + 3 + 4 = 9
2 + 3 + 5 = 10

Damit würde sich folgendes Programm zur Lösung des Problems ergeben:

Code: Alles auswählen

def main():
    for a in range(1000):  # ob 0 oder nicht ist ja "umstritten"
        for b in range(a + 1, 1000):
            for c in range(b + 1, 1000 - a - b + 1):
                if a*a + b*b == c*c and a + b + c == 1000:
                    print("Result:", a, '*', b, '*', c, '=', a * b * c)
                    return

if __name__ == '__main__':
    main()

Der Durchlauf erbringt die gewünschte Ausgabe

Code: Alles auswählen

Result: 200 * 375 * 425 = 31875000

Wobei wir ja inzwischen wissen, dass dies nicht viel über die Korrektheit des Programms auszusagen hat.

Sollte ich nun irgendwelche Aspekte in den genannten Verbesserungsvorschlägen nicht umgesetzt haben, dann tut das mir leid, ich mache es nicht mit Absicht, sondern hab wohlmöglich einfach
jene Information nicht extrahieren können. In dem Fall wäre es nett, wenn man mich nochmals konkret darauf hinweisen würde.

LG

[BlackJack]

Ha, ich wusste doch das ich das schon mal gelöst hatte — hier ist eine Lösung in C die auf einem C64 keine drei Minuten braucht: http://www.python-forum.de/viewtopic.ph ... 03#p243103

[EyDu]

Nun hast du ein wenig zu viel umgebaut. Die dritte Schleife, über die Werte von c, ist zu viel. Oben hast du das c ja auch schon aus a und b berechnet. Ansonsten kannst du die oberen Grenzen von a und b noch anpassen:

Code: Alles auswählen

for a in range(333):
    for b in range(a+1, (100-a-1)/2+1):
        c = 1000 - a - b

Damit gelten dann auch autoamtisch a < b < c und a+b+c=100.

[HarteWare]

Die Bedingung für b, damit c immer größer als b ist, versteh ich noch nicht ganz, aber ich werds mir heut Nachmittag mal nochmal genau anschauen^^

Soweit schonmal vielen Dank, ich glaub man kann jetzt eine im Vergleich zum Anfang deutlich schnellere und bessere Lösung bauen, und wenn jemand in Zukunft Probleme mit der Aufgabe hat,
wird der/diejenige hier bestimmt fündig.

[Sirius3]

@EyDu: nur zur Vollständigkeit, die 100 müßten 1000 sein.

[EyDu]

@Sirius3: Ja, da hast du natürlich Recht.

[HarteWare]

Also ich muss sagen, dass

Code: Alles auswählen

for b in range(a+1, (1000-a-1)/2+1):

mich noch etwas verwirrt, z.B. weshalb man von 1000 neben a auch noch 1 abzieht (wird wohl irgendwas damit zu tun haben, dass die passende Zahl rauskommt, weil b der Anteil für b muss ja kleiner sein als der für c) und dass man dann zum Ganzen 1 addiert, vermutlich weil range eben ein [a;b) Intervall ist. Außerdem können bei dem Ausdruck ja Dezimalzahlen als Ergebnis kommen. Ich frage mich, ob da ´for´ etwas wie range(200, 400.5) ganz speziell handhabt, z.B. die Nachkommastellen einfach ignoriert. Dann hab ich mich aber auch gefragt, wieso nicht einfach gleich floor division, also // nutzen.

Hab grad bemerkt, dass ich es in der Form nichtmal ausführen kann, TypeError wegen 'float' ...

Also ich habe es jetzt so, wenn ich alles richtig verstanden habe, kann ich den Test a+b+c==1000 mit der neuen Schleife jetzt auch weglassen.

Code: Alles auswählen

def main():
    for a in range(333):
        for b in range(a + 1, (1000-a-1) // 2 + 1):  # Hier hab ich // statt / verwendet
            c = 1000 - a - b
            if a*a + b*b == c*c:
                print("Result:", a, '*', b, '*', c, '=', a * b * c)
                return

if __name__ == '__main__':
    main()

Output stimmt schonmal, und auch scheinbar recht effizient. Jedenfalls nochmals Danke an alle, die so toll geholfen haben.

LG

[EyDu]

z.B. weshalb man von 1000 neben a auch noch 1 abzieht

1000 - a - 1 = 1000 - (a + 1)

Hab grad bemerkt, dass ich es in der Form nichtmal ausführen kann, TypeError wegen 'float' ...

Das hängt von der Python-Version ab. Ich verwende Python 2.7, da ist das automatisch eine ganzzahlige Division. Wenn du Python 3.x verwendest, dann musst das, wie du es gemacht hast, angepasst werden.

Also ich habe es jetzt so, wenn ich alles richtig verstanden habe, kann ich den Test a+b+c==1000 mit der neuen Schleife jetzt auch weglassen.

Richtig.