Project Euler31: Comprendre la solution de programme

Question

J'essaye de comprendre une solution pour Projet Euler # 31 J'ai trouvé dans les forums.

Le problème est que nous recevons des pièces avec les valeurs suivantes:

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

Nous sommes chargés de générer toutes les façons possibles d'atteindre 200. Par exemple, 10 * 10 + 100 = 200 seraient un moyen possible.

1. Question 2: Comment fonctionne le code ci-dessous! Il a l'air très élégant, simple et direct par rapport à mon approche, et fonctionne plus vite.

Alors que je parcourais les forums, j'ai trouvé cette solution:

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]

La première ligne n'est que la liste des valeurs de pièce. La deuxième ligne crée un tableau avec un 1 suivi de 200 0. Mais les quatre lignes suivantes m'ont confus. Je pense que cela augmente le nombre de façons possibles dans le tableau, donc Case_num [200] donnera la dernière entrée de la liste, mais je n'ai aucune idée de comment cela fonctionne.

Answer 1

C'est une très belle solution comme vous l'avez dit. Le code s'appuie sur lui-même par chaque itération de 1-200 à chaque dénomination de pièces.

Le tableau Case_num se compose initialement de [1, 0, 0, 0, 0, 0 ... 0, 0, 0

Ce que ces chiffres (à part le 1 initial) signifient le nombre de façons de construire au total donné (représenté par l'indice du nombre) en utilisant les pièces de P_List que vous avez itérées jusqu'à présent.

La première pièce de P_List est 1. Donc, si 1 peut s'intégrer à l'intérieur de l'index, vous prenez la valeur dans l'index précédent et l'ajoutez à votre index actuel. Cela fonctionne parce que s'il existe 5 façons connues pour atteindre 25 et que vous venez de trouver des pièces de taille 1, il y aura également 5 façons d'atteindre 26. [Chacune des 5 façons précédentes pour atteindre 25] + une pièce 1 .

Donc, après avoir itéré avec 1, vous vous retrouverez avec [1, 1, 1, 1, 1 ... 1, 1

Maintenant, vous montez dans des pièces. Cette fois, vous utilisez une pièce de 2. Permet de parcourir le processus 1 de plus. Si 2 est inférieur à l'index, vous ajoutez le nombre de façons d'accéder à l'index précédent à votre index actuel.

Par exemple, 2 ne correspond pas à Index 1, mais s'inscrit dans l'index 2. Vous venez donc de créer une nouvelle façon d'atteindre 2 à partir de 0 afin de prendre toutes les façons dont vous pouvez atteindre 0 et les ajouter à votre index actuel. Sur l'index 27, 2 s'inscrit dans l'index afin que vous preniez le nombre de façons d'atteindre 25 et les ajouter à 27 parce que maintenant vous avez (toutes ces façons d'atteindre 25 + une pièce 2) + (toutes les façons Vous deviez atteindre 27 avant de savoir que vous aviez des pièces de taille 2).

Donc, après avoir itérant avec 2, vous vous retrouverez avec [1, 1, 2, 2, 3, 3, 4, 4 ...

Si vous avez encore des problèmes, il peut être utile d'essayer de parcourir tout le programme (peut-être à un total réduit comme 50 au lieu de 200).