Version imprimable
Bonjour,
J'ai un problème en cours que je n'arrive pas à résoudre. J'ai une expression arithmétique préfixé (c'est à dire que 3x+9 -> +*3x9) qui doit être représenté sous la forme d'un arbre :
+
/ \
* 9
/ \
3 x
Le problème est que je dois calculer la dérivé à partir de cette arbre pour obtenir un autre arbre représentant cette dérivé et je n'arrive pas du tout à trouver la marche à suivre. Si quelqu'un pourrai m'aider, ça ne serait pas de refus !!!
Merci d'avance.
En gros, tu dois faire du calcul formel sur ton arbre?
Pour ça, je pense qu'il faut fragmenter ton expression et reconnaître des motifs.
En gros, au niveau supérieur, tu as forcément une addition, dont tu dois séparer les termes: De a+b+c+d, tu dois obtenir quatre arbres correspondant à a, b, c et d.
Ensuite, reconnaître des motifs dans ces arbres: typiquement, a.x, a.x^n, etc.
Si l'expression est sous forme préfixe, on peut facilement construire un arbre en la lisant de gauche à droite.
Et une fois que vous avez l'arbre, il suffit de le dériver récursivement, chaque type de noeud se dérivant à sa façon :
- deriver( A + B ) -> deriver( A ) + dériver( B )
- deriver( A * X ) -> deriver( A ) * B + A * deriver( B )
- deriver( X ) -> 1
- deriver( constante ) -> 0
- etc.
On peut éventuellement rajouter une passe de simplification :
- 0 * A -> 0
- 0 + A -> A
- etc.
je pense qu'il faut que tu commences par implémenter un algorithme qui te permettent de lire n'importe quelle de ces expressions.
Dans la formule données, après ton dernier opérateur tu as directement les deux symboles à lui assembler, puis tu remontes récursivement par niveau (à gauche le nouvel opérateur, à droite le nouveau symbole et ainsi de suite).
Ensuite construire dérivée ne devrait pas poser trop de problème comme te l'expliques remy72, l'arbre non plus, à toi d'organiser tes données dans un modèle cohérent (tableaux, strucures, liste chainées etc.)