[PYTHON] Essayez de faire face à la somme partielle
Bonsoir. Ça fait longtemps (* ´ω ｀)
Ce défi provient d'un tableau contenant des éléments arbitraires Sélectionnez des éléments au hasard et ajoutez-les ensemble. Mais il ne s'agit pas seulement d'additionner Il doit être additionné pour atteindre la valeur cible.
Par exemple, choisissez une combinaison dans le tableau pour que le total soit de 20 !! C'est quelque chose comme ça.
Un peu (; ´ ･ ω ･)
Cela semble être un contenu assez célèbre et basique, J'ai personnellement eu du mal (rires)
Tout à coup, Je vais mettre le code.
Partial_sum.py
def solve(Nlist, target, i=0, sum=0):
if i == len(Nlist):
return sum == target
if (solve(Nlist, target, i + 1, sum)):
return True
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
return False
Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))
C'est plus simple que vous ne le pensez, mais c'est compliqué. Par exemple, Au début, je ne regarderai qu'ici.
Partial_sum.py
#Commencez d'ici!!
Nlist = [1,3,5,12,7]
target = 11
# ↓[1,3,4...] ↓ 11
print(solve(Nlist, target))
Lancez Nlist et ciblez dans la résolution. En tant qu'image, un tableau contenant des éléments et une valeur totale cible Jetez le tout et dites bonjour !! Jetons un coup d'œil à l'intérieur de résoudre.
Partial_sum.py
#i est une image de votre emplacement actuel.
#sum est la somme des nombres actuels.
#Vous êtes à 0,La valeur totale est également 0
def solve(Nlist, target, i=0, sum=0):
#Nlist est de 5 de longueur, initialement je==Puisqu'il est 0, passe!!
if i == len(Nlist):
return sum == target
#cette?!Il y a aussi résoudre dans l'instruction if. Je ne sais pas!!
#Arrêtons de lire(Lol)
if (solve(Nlist, target, i + 1, sum)):
Je ne sais pas, je veux le jeter (rires).
Non, fuyez. .. La réponse est que si vous avez une récursivité dans votre instruction if, Terminez le processus récursif et dérivez vrai ou faux. Cela détermine s'il est inclus ou non dans l'instruction if. Hmm, stupide (rires)
Voulez-vous partir pour le moment? De résoudre (Nliste, cible, i + 1, somme) dans si Pour une aventure pour découvrir ce qui nous attend.
Allons-y dans l'ordre (`) ノ
i=0.py
def solve(Nlist, target, i=0, sum=0):
#pass!
if i == len(Nlist):
return sum == target
#Le traitement récursif se poursuit jusqu'à ce que l'instruction conditionnelle de l'instruction if soit True ou False.
if (solve(Nlist, target, i + 1, sum)):
return True
i=1.py
#solve(Nlist,target,1(=0+1),0)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=1, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#C'est aussi un processus récursif. Allons-y sans crainte!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=2.py
#solve(Nlist,target,2(=1+1),0)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=2, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#C'est aussi un processus récursif. Allons-y sans crainte!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=3.py
#solve(Nlist,target,3(=2+1),0)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=3, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#C'est aussi un processus récursif. Allons-y sans crainte!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=4.py
#solve(Nlist,target,4(=3+1),0)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=4, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#C'est aussi un processus récursif. Allons-y sans crainte!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=5.py
#solve(Nlist,target,5(=4+1),0)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=5, sum=0):
#i == len(Nlist) ==Enfin en 5, je l'ai mis dans l'instruction if au début.
if i == len(Nlist):
#Mais malheureusement somme(0) != target(11)。False
return sum == target
Je vois, je suis allé à i = 5, mais il s'est avéré être faux. Que se passe-t-il ensuite? .. Pour le moment, le résultat de i = 5 était Faux, donc Revenons à la couche précédente, i = 4.
i=4.py
def solve(Nlist, target, i=4, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#L'instruction conditionnelle dans if minutes était Flase. Autrement dit, la déclaration if ici est passée!!
#Passons à la prochaine instruction if!!
if (solve(Nlist, target, i + 1, sum)):
return True
#Ici je=4 alors remplaçons
# (solve(Nlist, target, 4 + 1, sum + Nlist[4]))
# (solve(Nlist, target, 5 , 0 + 7 ) //Nlist = [1,3,5,12,7]
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
Oui, passez à l'instruction if suivante. Vérifions à nouveau quand i = 5 avec une nouvelle instruction conditionnelle.
i=5.py
#solve(Nlist,target,5,7)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=5, sum=7):
#i == len(Nlist) == 5 ,Mettez-le dans l'instruction if.
if i == len(Nlist):
#Mais malheureusement somme(7) != target(11)。False
return sum == target
Je pense que le chiffre jusqu'à présent ressemblera à celui ci-dessous.
Une bonne personne peut faire ça avec sa tête,
Je ne pouvais pas le faire moi-même, alors je l'ai écrit sur papier et je l'ai organisé.
Pour en revenir à l'histoire, il semble que rien ne pourrait être fait tant que i = 4.
Rapportons maintenant ce résultat à i = 3.
i=3.py
#solve(Nlist,target,3(=2+1),0)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=3, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#Faux alors passe!!
#La somme n'a jamais été 11 du traitement précédent
if (solve(Nlist, target, i + 1, sum)):
return True
# (solve(Nlist, target, 3 + 1, sum + Nlist[3])): //Nlist = [1,3,5,12,7]
# (solve(Nlist, target, 4 , 0 + 12 )):
#Remplacez les conditions ci-dessous et entrez un nouveau si!!
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
i=4.py
#solve(Nlist,target,4(=3+1),12)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=4, sum=12):
#pass!!
if i == len(Nlist):
return sum == target
#C'est un processus récursif. Allons-y sans crainte!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=5.py
#solve(Nlist,target,5(=4+1),12)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=5, sum=12):
#i == len(Nlist) == 5 ,Mettez-le dans l'instruction if.
if i == len(Nlist):
#Mais malheureusement somme(12) != target(11)。False
return sum == target
C'était faux, je reviendrai sur un rapport.
i=4.py
#solve(Nlist,target,4(=3+1),12)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=4, sum=12):
#pass!!
if i == len(Nlist):
return sum == target
#Faux avec Pass!
if (solve(Nlist, target, i + 1, sum)):
return True
#Next↓
if (solve(Nlist, target, i + 1, sum + Nlist[i]))://Nlist = [1,3,5,12,7]
return True
i=5.py
#solve(Nlist,target,5(=4+1),12 + 7)Je suis entré dans le processus récursif.
def solve(Nlist, target, i=5, sum=19):
#i == len(Nlist) == 5 ,Mettez-le dans l'instruction if.
if i == len(Nlist):
#Mais malheureusement somme(19) != target(11)。False
return sum == target
Faisons une figure.
Je veux voir la structure en bois (rires)
C'est une tâche longue, mais ce n'est pas grave si vous gardez à l'esprit les points suivants.
** 1. Continuez à courir après l'instruction conditionnelle (récursive) de l'instruction if jusqu'à ce que vous voyiez True, False 2. Lorsque Vrai ou Faux est vu, revenez à la couche précédente et suivez fidèlement l'opération selon la description dans résoudre **
Je l'ai écrit avec brio, mais je ne le savais pas du tout, alors Pour voir ce qui change J'ai mixé pirnt comme suit.
Partial_sum.py
def solve(Nlist, target, i=0, sum=0):
print(f"i:{i},sum:{sum}") #Afficher la valeur actuelle pour plus de clarté pendant le traitement récursif
if i == len(Nlist):
#Pour le traitement récursif, mettez l'instruction conditionnelle lorsque vous arrivez à la couche inférieure au début.
#Alors, imprimez le commentaire que vous connaissez lorsque vous entrez cette instruction if est la couche inférieure
print(f"Result:i={i},sum={sum}")
print() #Sauts de ligne pour se séparer du processus suivant
return sum == target
if (solve(Nlist, target, i + 1, sum)):
return True
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
return False
Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))
Voyons le résultat de l'exécution !!
Résultat d'exécution.py
i:0,sum:0
i:1,sum:0
i:2,sum:0
i:3,sum:0
i:4,sum:0
i:5,sum:0
Result:i=5,sum=0
#↑ Comparez avec la figure ci-dessus. je,Le changement de somme ne correspond-il pas au chiffre?
#Result:i=5,sum=Renvoie False car la somme n'est pas 11 comme elle dit 0
#Je après le retour=Je serai de retour à 4 heures.
#Après le retour, passez à l'instruction IF suivante.
#Par conséquent, l'affichage suivant est i ci-dessous=Il devient pirnt au moment de 5.
#Si vous ne comprenez pas, veuillez retourner à la page ci-dessus.
i:5,sum:7
Result:i=5,sum=7
#↑sum(=7) !=Puisqu'il est 11, c'est faux.
#Donc, je=Les deux instructions if à 4 sont toutes les deux fausses.
#Ensuite, je=Il revient à l'instruction if au moment de 3, mais le traitement est le même que ci-dessus.
i:4,sum:12
i:5,sum:12
Result:i=5,sum=12
i:5,sum:19
Result:i=5,sum=19
i:3,sum:5
i:4,sum:5
i:5,sum:5
Result:i=5,sum=5
i:5,sum:12
Result:i=5,sum=12
i:4,sum:17
i:5,sum:17
Result:i=5,sum=17
i:5,sum:24
Result:i=5,sum=24
i:2,sum:3
i:3,sum:3
i:4,sum:3
i:5,sum:3
Result:i=5,sum=3
i:5,sum:10
Result:i=5,sum=10
i:4,sum:15
i:5,sum:15
Result:i=5,sum=15
i:5,sum:22
Result:i=5,sum=22
i:3,sum:8
i:4,sum:8
i:5,sum:8
Result:i=5,sum=8
i:5,sum:15
Result:i=5,sum=15
i:4,sum:20
i:5,sum:20
Result:i=5,sum=20
i:5,sum:27
Result:i=5,sum=27
i:1,sum:1
i:2,sum:1
i:3,sum:1
i:4,sum:1
i:5,sum:1
Result:i=5,sum=1
i:5,sum:8
Result:i=5,sum=8
i:4,sum:13
i:5,sum:13
Result:i=5,sum=13
i:5,sum:20
Result:i=5,sum=20
i:3,sum:6
i:4,sum:6
i:5,sum:6
Result:i=5,sum=6
i:5,sum:13
Result:i=5,sum=13
i:4,sum:18
i:5,sum:18
Result:i=5,sum=18
i:5,sum:25
Result:i=5,sum=25
i:2,sum:4
i:3,sum:4
i:4,sum:4
i:5,sum:4
Result:i=5,sum=4
i:5,sum:11
Result:i=5,sum=11
True
Comme mentionné ci-dessus, après avoir atteint la limite où la transition n'est pas possible La méthode de répétition du processus de retour d'une étape et d'opération à la limite est appelée ** recherche de priorité de profondeur **. Le matériel dit qu'il est relativement facile d'écrire, Non, c'est génial pour les débutants !! (ﾟ Д ﾟ)
Il semble que l'avenir soit encore long (* ´ω ｀)
Recommended Posts