Discussion :

[unix27]

Bonjour, je cherche un algorithme optimal qui puisse faire la somme d’un ensemble de nombres réels ( donnés en entré )je m’explique par exemple j’ai un tableau de 12 réels comme ceci :

Code :

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

T[12]={1.1,2.2,3.9…}

Et je souhaite faire toutes les combinaisons possibles CAD
Combinaison1=T[1]+T[2]+T[3]+…
Combinaison2=T[2]+T[1]+T[3]+…
Combinaison3=T[3]+T[2]+T[1]+…
Combinaison n=….


Et on faisant la somme si cette dernière est supérieure à 6 alors s’arrêter et mettre les éléments restant dans la même ligne sinon continuer à faire les sommes … le but de l’algorithme est d’afficher la combinaison dont les éléments sont égaux ou se rapproche du nombre 6, donc pour continuer l’exemple ci-dessus ça donnera :
Combinaison1=(1.1+2 .2) puisque 3,3 <6 donc faire (3,3+3,9)…
Combinaison2=(2 .2+1.1) puisque 3,3 <6 donc faire (3,3+3,9)…
Combinaison3=(3.9+2.2) puisque 6,1 >6 conserver le 3.9 et 2.3 et faire la somme de 1,1+…

j'ai déjà ouvert le sujet et j'ai cru que le problème est résolu mais l'algorithme implémenté marche juste avec 4 ou 8 éléments réel dans le tableau par contre avec 12 ou 16... ça prend 2h ou même plus...

[ToTo13]

Code :

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

T[12]={1.1,2.2,3.9…}

Et je souhaite faire toutes les combinaisons possibles CAD
Combinaison1=T[1]+T[2]+T[3]+…
Combinaison2=T[2]+T[1]+T[3]+…
Combinaison3=T[3]+T[2]+T[1]+…
Combinaison n=….

L'addition étant commutative, ce que tu as marqué là est exactement la même chose. Mais c'est pas le problème.

Si tu veux tester TOUTES les combinaisons, il te faut faire une récursivité, plus précisément ici, il te faut en faire 12, chacune démarrant avec un élément différent en tête de l'arbre.
Si tu fais ta recherche brute, c'est effectivement super long.
Il te faut donc couper rapidement des branches de l'arbre de recherche, comme le fait tout simple : si somme > 6 alors arrêter la recherche dans cette branche.

Si tu veux toutes les solutions approchantes, la recherche exhaustive est obligatoire.
Si tu ne veux que certaines des combinaisons, tu peux tenter une recherche Tabou.

[ZenZiTone]

Si tu veux tester TOUTES les combinaisons, il te faut faire une récursivité

Le temps de traitement n'est-il pas accentué en utilisant la récursivité?

[dourouc05]

Le temps de traitement n'est-il pas accentué en utilisant la récursivité?

Si elle est faite de manière intelligente avec un bon compilateur, il n'y a aucune raison que l'approche récursive soit plus lente qu'une approche impérative (voir, par exemple, l'annotation @tialrec de Scala, http://www.scala-lang.org/api/curren...tation.tailrec, qui indique clairement le code qui ne peut pas être réécrit sous la forme d'une boucle, largement plus efficace qu'une série d'appels récursifs). Le temps de traitement ne devrait pas être la première préoccupation sur la manière d'implémenter un algorithme : il vaut mieux avoir rapidement un code qui fonctionne mais qui peut être optimisé (premature optimization is root of all evil​).

[ZenZiTone]

Le temps de traitement ne devrait pas être la première préoccupation sur la manière d'implémenter un algorithme : il vaut mieux avoir rapidement un code qui fonctionne mais qui peut être optimisé (premature optimization is root of all evil​).

Oui, je disais ça dans le sens ou unix27 cherchait à optimiser le temps ^^

Merci pour le lien