Discussion :

[CompuTux]

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!

[pseudocode]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.