Le problème inverse de l'analyseur syntaxique

Bonjour,

J'aimerais programmer le problème inverse de l'analyseur syntaxique :

Il s'agit pour moi d'étudier le problème suivant :

On s’autorise les opérations arithmétiques usuelles {+,-,*,/} et l'objectif est de construire le maximum de nombre entiers positifs à l'aide de ces opérations et de n fois le nombre n.

Par exemple :

Si n=1 : on a 1 = 1 donc une seule formule, l'identité.

Si n=2 : on a 4 formules : 0=2-2, 1=2/2, 4=2+2=2*2

Si n= 3 : on a 16 formules "linéaires" obtenues en créant un arbre binaire...

Bref si n=k : on a 4^(k-1) formules "linéaires"...


J'aimerais pouvoir automatiser l'écriture de ces formules, les évaluer, et les trier.

Je suis pas très doué en algorithmique, si quelqu'un pouvait m'aider, je lui en serais très reconnaissant.

Merci d'avance!

La méthode la plus simple c'est d'imbriquer des boucles pour parcourir toutes les configurations possibles:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

TABLEAU operations[] = { add(), sub(), mul(), div() }   ' cas N=2 POUR CHAQUE f1 DANS operations valeur = f1(2,2) FIN POUR   ' cas N=3 POUR CHAQUE f1 DANS operations POUR CHAQUE f2 DANS operations valeur = f1(3, f2(3,3) ) FIN POUR FIN POUR   ' cas N=4 POUR CHAQUE f1 DANS operations POUR CHAQUE f2 DANS operations POUR CHAQUE f3 DANS operations valeur = f1(4, f2(4, f3(4,4) ) ) FIN POUR FIN POUR FIN POUR

---

Le problème de cette approche c'est qu'il faut écrire un code spécifique pour chaque valeur de N.

Pour avoir une solution générique, on peut utiliser des appels récursifs. On peut aussi utiliser un itérateur.