Aide pour un algo récursif
Posted: 16 Feb 2014, 23:03Bonsoir,
Je suis en galère avec un algorithme récursif destiné à la résolution d'un problème de Project Euler.
Je ne veux pas vraiment que vous me donniez une solution mais que vous me disiez si vous voyez ce qui ne va pas...
Voici le code Python (pour ceux qui ne le maîtrisent pas, ça se lit presque comme du pseudo-code).
Les """ servent à encadrer des commentaires
Le but est de trouver le nombre d'ensembles constitués de nombres premiers dont les chiffres sont les chiffres de 1 à 9 écrits une et une seule fois chacun.
Ce programme ne renvoie malheureusement pas le bon résultat... mais je ne sais pas pourquoi.
Si vous comprenez ce code et que vous voyez pourquoi ça ne marche pas... merci de me le dire !
PS : Pour ceux qui voudraient essayer l'algorithme chez eux, c'est du Python 3.
Pour info, le calcul de "primedigits" au départ prend 540Mo de RAM environ et un peu moins de 4 minutes.
Ensuite, la recherche récursive ne prend que 3 minutes environ.
Je suis en galère avec un algorithme récursif destiné à la résolution d'un problème de Project Euler.
Je ne veux pas vraiment que vous me donniez une solution mais que vous me disiez si vous voyez ce qui ne va pas...
Voici le code Python (pour ceux qui ne le maîtrisent pas, ça se lit presque comme du pseudo-code).
Les """ servent à encadrer des commentaires
Le but est de trouver le nombre d'ensembles constitués de nombres premiers dont les chiffres sont les chiffres de 1 à 9 écrits une et une seule fois chacun.
- Code: Select all
def pb118()
"""On calcule une liste de True et False, servant d'oracle pour savoir si un entier est premier."""
isprime = eratho(10 ** 8)
"""Avec cet oracle, on fait une liste des nombres premiers qui ne contiennent pas le chiffre 0.
On les enregistre sous forme de chaînes de caractères."""
primes = [str(i) for i in range(10 ** 8) if isprime[i] and '0' not in str(i)]
"""Ensuite, on fait une liste des ensembles des chiffres composant les nombres premiers
qui ne contiennent aucun chiffre répété. C'est de cette liste qu'on se servira dans la fonction récursive."""
primedigits = [{int(j) for j in a} for a in primes if all(u not in a[k + 1:] for k, u in enumerate(a))]
"""res contiendra le résultat cherché. On utilise une liste car cela évite d'avoir à la déclarer globale..."""
res = [0]
def search(currentdigits, nextindex):
"""Cherche récursivement des nombres premiers à rajouter au panier et fait le compte
des paniers trouvés."""
l = len(currentdigits)
if l == 9:
"""Dans ce cas, on a forcément : currentdigits = {1, 2, 3, 4, 5, 6, 7, 8, 9}"""
res[0] += 1
else:
for i, newDigits in enumerate(primedigits[nextindex:]):
if len(newDigits) + l > 9:
"""Inutile de poursuivre si les nombres premiers suivants ont trop de chiffres."""
break
if currentdigits.isdisjoint(newDigits):
"""On rajoute les nouveaux chiffres et on continue à chercher récursivement à partir
du rang suivant dans la liste des premiers."""
search(currentdigits | newDigits, i + 1)
"""On commence à chercher à partir d'un ensemble vide, et à partir de l'indice 0."""
search(set(), 0)
return(res[0])
Ce programme ne renvoie malheureusement pas le bon résultat... mais je ne sais pas pourquoi.
Si vous comprenez ce code et que vous voyez pourquoi ça ne marche pas... merci de me le dire !
PS : Pour ceux qui voudraient essayer l'algorithme chez eux, c'est du Python 3.
Pour info, le calcul de "primedigits" au départ prend 540Mo de RAM environ et un peu moins de 4 minutes.
Ensuite, la recherche récursive ne prend que 3 minutes environ.
.
.