Trouver la priorité

[fatal_error]

hello,

suite à http://www.maths-forum.com/equation-concours-ifsi-154352.php
je vous soumets un ptit challenge/occupation

à partir d'une expression non parenthèsée, retrouver l'endroit ou il faut mettre les parenthèses sachant que l'on connait déjà le résultat attendu.

ex:
cos 3*pi*5=-5 => cos(3*pi)*5
8/1+3*3^2=36 => (8/(1+3)*3)^2

[ampholyte]

Bonjour,

Petit challenge sympa, je sais pas si j'aurais le temps de m'y consacrer mais je vais suivre le fil =).

A première vue, à part le brute-force, je ne vois pas trop d'autres solutions. As-tu déjà quelques pistes ?

[fatal_error]

salut Ampholyte,

nan j'ai pas d'autres pistes, je pense (mais je demande à être surpris) que c'est délicat d'optimiser ca (style croissance de fonctions...), du coup, à part des optimisations algorithmiques style prod dynamique ou mémoisation...ca m'a l'air pas évident d'éviter la brute force

[Ben314]

Salut,
Je sais pas si c'est forcément lié (et je me rappelle plus non plus du résultat...) mais il me semble me rappeller qu'un problème classique de dénombrement est celui du "parenthésage" : si on a une loi * non associative, combien de façons y-a-t-il de calculer a1*a2*a3*...*an.

Par exemple, pour n=4, on peut faire
a1*(a2*(a3*a4))
(a1*a2)*(a3*a4)
a1*((a2*a3)*a4)
(a1*(a2*a3))*a4
((a1*a2)*a3)*a4
Soit 5 possibilités (si j'en ai pas raté...)

[fatal_error]

hello,

En tout cas, on peut s'en sortir avec la recursive suivante:

Code: Tout sélectionner

/*
  arr: array of chars
  returns: array of ctx
  ctx is a string with parenthesis representing formula
*/
function addParenthesis(arr)
  ctxList= []; //array of ctx
  for i=0: length(arr) //index of opening parenthesis
    for j=i+2: length(arr)  //index of closing parenthesis
      leftArray = arr(0, i);//we keep leftArray untouched
      subContext = arr(i, j);
      rightContext = arr(j, length(arr));
      if length(subContext)>1
        subContextList = addParenthesis(subContext);
        //for all elem of subContextList, add parenthesis around elem
        subContextList = subContextList.map(x=>'('+x+')')
      else
        subContextList = [subContext]; //if only one element, no need to add parenthesis
      end
      if length(subContext)>1
        rightContextList = addParenthesis(rightContext);
        //no need to add parenthesis because recursive call
      else
        rightContextList = [rightContext]
      end
      allList = cartesianProduct(subContextList, rightContextList);
      forEach allList as toConcatenate
        ctxList.push(leftArray+toConcatenate);
      end
    end
  end
  return ctxList
end



ya pe moyen de voir si on peut transposer ca sous forme mathématique récursive et voir si on peut exprimer le terme général...

evidemment de cette façon, il reste à évaluer l'expression à chaque fois,..., ce qui est pas très optimal..