Je suis de nouveau sur un exercice d'implémentation de fonction récursive. Je n'ai pas encore soumis de code, car je ne sais même pas à quoi la solution peut ressembler. Je ne souhaite pas que l'on me donne une réponse toute faite. Merci à qui saurait me dire en français comment raisonner pour trouver la solution. (A priori cela me paraît insoluble comme problème)
Voici l'énoncé:
On vous donne un nombre de départ N ainsi qu'un nombre d'arrivée M, et le but du jeu est d'appliquer une séquence d'opérations à partir de N afin d'obtenir la valeur M.
Il y 4 opérations possibles :
ajouter A,
retirer B,
multiplier par C,
diviser par D, à condition que le résultat soit entier,
où A, B, C et D sont des nombres entiers donnés en entrée. Notez que tous les résultats intermédiaires des calculs doivent être compris dans l'intervalle [0,100 000].
Déterminez s'il existe une séquence d'opérations permettant de passer du nombre de départ à celui d'arrivée.
Limites de temps et de mémoire (Python)
Temps : 2 s sur une machine à 1 GHz.
Mémoire : 2 000 ko.
Contraintes
0 <= A, B, C, D <= 1000, où A,B,C,D sont les constantes utilisées pour les opérations.
0 <= N, M <= 100 000, où N est le nombre de départ et M est le nombre d'arrivée.
Entrée
La première ligne contient quatres entiers séparés par des espaces : A, B, C et D.
La seconde ligne contient deux entiers séparés par un espace : N et M.
Sortie
Affichez 1 s'il est possible de passer de N à M, et 0 si non.
Ok. Merci. Tu me fais réaliser que mon problème se situe plus au niveau de l'implémentation de la récursivité: il est évident que je ne vais pas stocker les résultats intermédiaires dans une liste; je dois donc rappeler ma fonction récursivement sur chacun d'eux dès leur obtention; mais alors comment faire pour éviter les boucles infinies, par exemple: addition - atteinte du seuil - soustraction - addition - atteinte du seuil - soustraction ... ? (à chaque appel, la fonction applique TOUTES les opérations au résultat qui lui est fourni)
De ce que j'ai compris de @mps, tu appliques les 04 operations(avec la variable coorespondante) a ta variable N, pas successivement mais chaque operation de son cote tu auras donc 04 resultats a la fin de cette premiere "Execution", puis tu refais la meme chose pour chacune de ces 04 variables tu auras maintenant 16 variables, ainsi de suite.
Dans l'énoncé de l'exercice les resultats de calculs intermediaires ne doivent pas depasser 100 000. Tu sais donc que si tu depasses cette valeur tu ne continues plus avec ce resultat. Tu t'arretes donc lorsque qu'un resultat ne respecte plus cette contrainte ou alors abouti a M.
for resultat in (depart+constantes[0], depart-constantes[1], depart*constantes[2], depart//constantes[3]): if seqenceOperations(resultat,arrivee,constantes): return True return False
-
Comment afficher True ou False en entier?
>>> int(True) 1 >>> int(False) 0
- edit: Je me suis rammassé dans la nature ... ce n'est pas un BFS ... Normalement, un arbre a une profondeur finie. Ici elle peut être infinie. Je me suis arrangé pour ne traiter que les valeurs que je n'avais pas traitées. On dit que les valeurs intermédiaires doivent être dans [0, 100000] donc 100001 valeurs.
J'ai modifié mon code car les set prenaient trop de place et sont plus lents qu'une liste de booléens. Voici un code qui fonctionne en BFS avec un set (modifié) pour exclure les valeurs déjà traitées.
Avec de la chance, si on multiplie par 4 la longueur à chaque génération, on s'en tire avec 9 récursions. - def seq(L, S, a, C): for e in L: if e == a: return True
for e in L: S[e] = False LL = [] for e in L: LL.extend([c for c in(e+C[0], e-C[1], e*C[2], e//C[3]) if 0 <= c <= 100000 and S[c]]) if len(LL) == 0: return False return seq(LL, S, a, C) C = list(map(int, input().split())) d, a = map(int, input().split())
S = [True] * 100001 print(int(seq([d], S, a, C)))
- Edité par PierrotLeFou 15 juillet 2022 à 5:36:13
Le Tout est souvent plus grand que la somme de ses parties.
A l'étape N, on applique A,B,C,D aux résultats de l'étape N - 1. Ce qui produit les résultats de l'étape N et éventuellement entrer dans l'étape N+1.
from operator import mul, add, sub, floordiv
OPS = add, sub, mul, floordiv
MAX_LEVEL = 10
def op_sequence(depart, target, values, level=0):
operations = tuple( zip(OPS, values) )
def do_it(results, level=0):
#print(level, results)
if level > MAX_LEVEL:
return False
nr = []
for r in results:
for op, v in operations:
z = op(r, v)
if 0 <= z <= 1000000:
if z == target:
return True
nr.append(z)
return do_it(nr, level=level+1) if len(nr) else False
return do_it([depart])
A,B,C,D = 10, 4, 2, 3
depart,arrivee = 21, 32
print(op_sequence(depart, arrivee, (A, B, C, D)))
Après on peut optimiser avec des sets comme l'a fait PierrotLeFou.
def op_sequence(depart, target, values, level=0):
operations = tuple( zip(OPS, values) )
def do_it(results, visited, level=0):
# print(level, results)
if level > MAX_LEVEL:
return False
nr = set()
for r in results:
for op, v in operations:
z = op(r, v)
if 0 <= z <= 1000000:
if z == target:
return True
if z not in visited:
nr.add(z)
visited.add(z)
return do_it(nr, visited, level=level+1) if len(nr) else False
return do_it(set([depart]), set([depart]))
On élague l'arbre en évitant de refaire les calculs qu'on a déjà fait (visited) ou en faisant plusieurs fois le même calcul (results).
J'ai remplacé mon set par un tableau de booléens car ça prend moins de place pour 100001 valeurs. >>> from sys import getsizeof >>> getsizeof([True]*100001) 800064 >>> getsizeof({i for i in range(100001)}) 4194520 >>> J'ai également supposé que c'était nettement plus rapide avec le tableau de booléens. Mais j'ai atteint le nombre maximum de récursions avec l'exemple suivant: 10 40 300 700 10 12019 J'ai augmenté le nombre de récursions à 50000 et ça passe ...
edit:
J'ai testé le temps de ce dernier exemple sur un ordi à 4 GHz et ça prend 0.258 secondes.
re-edit:
J'ai calculé le nombre de récursions. Ça donne 1202 récursions.
Et la valeur est 1, donc il trouve une solution (je ne l'ai pas affichée ...)
- En principe, on multiplie par 4 le nombre d'éléments d'un niveau à l'autre: 1 4 16 64 256 1024 4096 16384 65536 262144 Si on élimine les valeurs déjà visitées, il en reste moins. Mais combien? Si on augmente d'un tout petit nombre le nombre d'éléments visités à chaque niveau, cela pourrait prendre plusieurs niveau avant de tout visiter ou trouver la solution.
- Edité par PierrotLeFou 17 juillet 2022 à 1:36:24
Le Tout est souvent plus grand que la somme de ses parties.
On est dans un cas ou la récursivité ne sert plus à rien (pas besoin de revenir en arrière) et ou il est facile(?) de faire une simple boucle:
def op_sequence4(depart, target, values, level=0):
operations = tuple( zip(OPS, values) )
def do_it(results, visited):
iter_count = 0
while True:
#print (iter_count, results)
iter_count += 1
## nr = set()
## for r in results:
## for op, v in operations:
## z = op(r, v)
## if 0 <= z <= 1000000:
## if z == target:
## return True
## nr.add(z)
g = (op(r, v) for op, v in operations for r in results)
nr = { z for z in g if 0 <= z <= 1000000 and not z in visited }
if target in nr:
return True
#nr -= visited
visited.update(nr)
results = nr
if not len(nr):
return False
return do_it(set([depart]), set([depart]))
@mps: Tu as tout à fait raison. Pas besoin de fonction non plus:
J'en ai profité pour ramener les variables a, b, c, d pour illustrer l'énoncé de base.
Le temps d'exécution pour mon mauvais exemple passe à 0.178 secondes. - a, b, c, d = map(int, input().split()) depart, arrivee = map(int, input().split()) S = [True] * 100001 L = [depart]
while len(L): r = arrivee in L if r: break for e in L: S[e] = False L = [i for e in L for i in (e+a, e-b, e*c, e//d) if 0 <= i <= 100000 and S[i]] print(int(r))
- Edité par PierrotLeFou 18 juillet 2022 à 2:25:29
Le Tout est souvent plus grand que la somme de ses parties.
Pierrot, ton code passe 5/17 tests. Pour un des 12 restants il est trop lent et pour tous les autres il dépasse la limite de mémoire.
Voici le mien moins élégant mais qui passe:
constantes = list(map(int,input().split()))
depart,arrivee = map(int,input().split())
a_voir = [True]*100001
premiere_liste = [depart]
deuxieme_liste = []
suivant = True
fin = True if depart == arrivee else False
while suivant and not fin:
for nombre in premiere_liste:
if not fin:
somme = nombre+constantes[0]
difference = nombre-constantes[1]
produit = nombre*constantes[2]
if constantes[3] and nombre % constantes[3] == 0:
quotient = nombre//constantes[3]
else: quotient = nombre
if arrivee in (somme,difference,produit,quotient): fin = True
else:
if 0 <= somme <= 100000 and a_voir[somme]:
a_voir[somme] = False; deuxieme_liste += [somme]
if 0 <= difference <= 100000 and a_voir[difference]:
a_voir[difference] = False; deuxieme_liste += [difference]
if 0 <= produit <= 100000 and a_voir[produit]:
a_voir[produit] = False; deuxieme_liste += [produit]
if 0 <= quotient <= 100000 and a_voir[quotient]:
a_voir[quotient] = False; deuxieme_liste += [quotient]
if not deuxieme_liste: suivant = False
else: premiere_liste = deuxieme_liste; deuxieme_liste = []
print(1 if fin else 0)
Je comprend un peu. J'ai toujours ma liste S des visités qui fait environ 800 Kb Il se peut que ma première version de la liste L soit déjà assez grande et que j'en génère une autre aussi grande, ce qui ferait que je dépasse les 2 Mb Et cela prend du temps (peut-être inutilement) Pour la vitesse, je génère tout d'un coup alors que tu testes à mesure que tu as les informations. Tu ne génère rien inutilement comme je fais.
Tu mets ta liste des visités à jour plus rapidement que je le fais. Donc, ta liste de sortie peutt être plus courte.
Quand tu trouves arrivee, tu mets fin égal à True et tu testes à chaque tour de boucle intérieure si fin == True pour sauter le reste.
Tu pourrais mettre fin à True et faire un break pour ne plus parcourir la boucle intérieure. Il n'est dit nulle part si le quatrième nombre (d) peut être 0 ou pas. Si c'était le cas, j'aurais eu une erreur de division par zéro (ZeroDivisionError). Pourquoi testes-tu si le reste de la division est 0? > • diviser par D, à condition que le résultat soit entier nombre // d ne suffit pas?
-
J'ai fait le petit test suivant:
Et le append est un peu plus rapide que de faire un += d'une autre petite liste
from time import perf_counter n=10000000 begin=perf_counter() L=[] for i in range(n): L+=[i] print(round(perf_counter()-begin, 3), "secondes") begin=perf_counter() L=[] for i in range(n): L.append(i) print(round(perf_counter()-begin, 3), "secondes")
-
edit: Tu dois savoir que j'aime le code compressé? Je suis un one-liner invétéré. J'ai repris ton code. Est-ce qu'il fonctionne? (sauf peut-être pour le quotient) - a, b, c, d = map(int, input().split()) depart, arrivee = map(int, input().split()) a_voir = [True] * 100001 premiere_liste = [depart] fin = depart == arrivee
while premiere_liste and not fin: deuxieme_liste = [] for nombre in premiere_liste: somme, difference, produit, quotient = nombre+a, nombre-b, nombre*c, nombre//d if arrivee in (somme, difference, produit, quotient): fin = True; break for resultat in (somme, difference, produit, quotient): if 0 <= resultat <= 100000 and a_voir[resultat]: a_voir[resultat] = False; deuxieme_liste.append(resultat) premiere_liste = deuxieme_liste print(int(fin))
- Edité par PierrotLeFou 19 juillet 2022 à 4:42:42
Le Tout est souvent plus grand que la somme de ses parties.
Cela ne pose pas de problème d'écrire un division par d avant de tester si d est différent de 0? (quelle différence avec les indices de listes qu'il faut tester avant de pointer pour ne pas avoir l'erreur out of range?)
Edit: j'ai testé, tout est bon.
Edit2: mais, je ne comprends pas pourquoi, cette façon d'écrire ralentit un peu l'exécution du programme.
Je pense que ce qui ralentit le plus est ma dernière boucle pour inactiver et ajouter dans la seconde liste. C'est sans doute plus rapide avec 4 if successifs.
Le Tout est souvent plus grand que la somme de ses parties.
J'ai refait le test avec mon mauvais exemple. Avec la boucle, le temps est de 0.019 seconde Avec les 4 if, le temps est de 0.016 seconde Soit environ 15% d'amélioration. Mais les deux sont environ 10 fois plus rapides que ma version avec compréhension.
Le Tout est souvent plus grand que la somme de ses parties.
sequence d'operations
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.