Si je ne m'abuse, les résultats intermédiaires se ramènent à une utilisation de parenthèses, et en somme, une solution possible a forcément la forme d'un arbre binaire, les opérations utilisées ayant à chaque fois deux termes. Même si plusieurs arbres peuvent être équivalent à cause de la commutativité de l'addition et de la multiplication.
Bref, des arbres binaires avec quatre feuilles, il n'y en a pas trente-six, en fait il n'y en a que deux si je ne m'abuse, les autres formes possibles étant équivalentes à celles-ci en échangeant des nombres :
/\ /\
a /\ / \
b /\ / \
c d /\ /\
a b c d
Donc, deux formes d'arbres, 4! répartitions des quatre nombres, et, les arbres ayant 3 nœuds sur lesquels il faut choisir à chaque fois une opération parmi les quatre opérations de base, 43 choix d'opérations. Soit un total de 3072 possibilités. Je me trompe ?
On pourrait envisager d'optimiser le calcul en réutilisant des résultats de sous-arbres. Cela implique d'utiliser une forme de cache, et je ne suis en fait pas certain que ce soit vraiment plus efficace que de calculer sans cache. Un avis ?
# Quelques pensées
Posté par 🚲 Tanguy Ortolo (site web personnel) . En réponse au journal résoudre "trouve 24". Évalué à 5.
Si je ne m'abuse, les résultats intermédiaires se ramènent à une utilisation de parenthèses, et en somme, une solution possible a forcément la forme d'un arbre binaire, les opérations utilisées ayant à chaque fois deux termes. Même si plusieurs arbres peuvent être équivalent à cause de la commutativité de l'addition et de la multiplication.
Bref, des arbres binaires avec quatre feuilles, il n'y en a pas trente-six, en fait il n'y en a que deux si je ne m'abuse, les autres formes possibles étant équivalentes à celles-ci en échangeant des nombres :
Donc, deux formes d'arbres, 4! répartitions des quatre nombres, et, les arbres ayant 3 nœuds sur lesquels il faut choisir à chaque fois une opération parmi les quatre opérations de base, 43 choix d'opérations. Soit un total de 3072 possibilités. Je me trompe ?
On pourrait envisager d'optimiser le calcul en réutilisant des résultats de sous-arbres. Cela implique d'utiliser une forme de cache, et je ne suis en fait pas certain que ce soit vraiment plus efficace que de calculer sans cache. Un avis ?