Projekt Euler31: Programmlösung verstehen

Question

Ich versuche eine Lösung zu verstehen Projekt Euler #31 Ich habe in den Foren gefunden.

Das Problem ist, dass wir Münzen mit den folgenden Werten erhalten:

coins=[1,2,5,10,20,50,100,200]

Wir sind beauftragt, alle möglichen Möglichkeiten zu generieren, 200 zu erreichen. Beispielsweise wäre 10*10+100 = 200 ein möglicher Weg.

1. Frage 2: Wie funktioniert der folgende Code! Es sieht im Vergleich zu meinem Ansatz sehr elegant, einfach und unkompliziert aus und läuft schneller.

Als ich in den Foren stöberte, fand ich diese Lösung:

p_list = [1, 2, 5, 10, 20, 50, 100, 200]
case_num = [1] + [0] * 200
for i in p_list:
    for j in range(1, 201):
        if i <= j:
            case_num[j] += case_num[j-i]
print case_num[200]

Die erste Zeile ist nur die Liste der Münzwerte. Die zweite Zeile erstellt ein Array mit einer 1, gefolgt von 200 0. Aber die nächsten vier Zeilen haben mich verwirrt. Ich denke, es erhöht die Anzahl der möglichen Wege im Array, also wird Case_num [200] den letzten Eintrag in der Liste angeben, aber ich habe keine Ahnung, wie es funktioniert.

Answer 1

Dies ist eine sehr schöne Lösung, wie Sie sagten. Der Code baut durch jede Iteration von 1-200 mit jeder Münz-Konfession auf sich auf.

Das CASE_NUM -Array besteht zunächst aus [1, 0, 0, 0, 0, 0 ... 0, 0, 0

Was diese Zahlen (abgesehen von der ersten 1) bedeuten, wie viele Möglichkeiten Sie auf die angegebene Gesamtsumme (dargestellt durch den Index der Zahl) unter Verwendung der Münzen in P_LIST aufbauen können, mit der Sie bisher iteriert haben.

Die erste Münze in P_LIST ist 1. Wenn 1 also in den Index passen kann, nehmen Sie den Wert im vorherigen Index ein und fügen ihn zu Ihrem aktuellen Index hinzu. Dies funktioniert, denn wenn es 5 bekannt gibt, um 25 zu erreichen, und Sie gerade Münzen der Größe 1 gefunden haben, gibt es auch 5 Möglichkeiten, um zu 26 zu gelangen. .

Nachdem Sie also mit 1 durchgesetzt wurden, erhalten Sie [1, 1, 1, 1, 1 ... 1, 1

Jetzt bewegen Sie sich in Münzen. Dieses Mal verwenden Sie eine Münze von 2. Wenn 2 weniger als der Index ist, fügen Sie die Anzahl der Möglichkeiten hinzu, um Ihren aktuellen Index zum vorherigen Index zu erreichen.

Zum Beispiel 2 passt nicht in den Index 1, passt jedoch in Index 2 ein. Auf Index 27 sind 2 Anpassungen in den Index, sodass Sie die Anzahl der Möglichkeiten aufnehmen, wie Sie 25 erreichen können, und sie zu 27 hinzufügen, da Sie jetzt (all diese Möglichkeiten, um 25 + ein 2 Münze zu erreichen) + (alle Wege Sie mussten zu 27 kommen, bevor Sie wussten, dass Sie Münzen der Größe 2 hatten).

Nachdem Sie also mit 2 durchgesehen haben, erhalten Sie [1, 1, 2, 2, 3, 3, 4, 4 ...

Wenn Sie immer noch Probleme haben, kann es sich lohnen, das gesamte Programm zu durchlaufen (möglicherweise bei einer reduzierten Gesamtzahl von 50 statt 200).