1 équation à 8 inconnues !

[antoninelghozi]

Bonjour,

Je voudrais trouver toutes les solutions de l'équation suivante :

T1*a+T2*b+T3*c+T4*d+T5*e+T6*f+ T7*g+T8*h=T

Avec T1...T8 et T des réels positifs et a...h des booléens.

Comment procéder rapidement ?
Merciiii
-----

[gg0]

Bonjour.

Quelle est l'inconnue ? Dans la suite, je vais supposer que ce sont les Ti qui sont des inconnues (vu ton titre).
Que veut dire "des booléens" ? si ça veut dire qu'ils valent soit 0 soit 1, il suffit de regarder si l'un d'entre eux vaut 1. par exemple, si a=1, tu prends ce que tu veux comme valeurs de T2, T3, ..T8, puis T1= T-(T2*b+T3*c+T4*d+T5*e+T6*f+ T7*g+T8*h). Si a est nul, mais c non nul, tu fais la même chose avec T3.
Si par contre a est "vrai" ou "faux", il faut dire ce que ça signifie.

Cordialement.

[antoninelghozi]

Avec T1...T8 et T des réels positifs

Ils sont connus. Les inconnus sont a...h

[antoninelghozi]

Par booléens j'entendais 0 ou 1.

[A voir en vidéo sur Futura]

[gg0]

Alors, sans conditions particulières sur les Ti, et T, il n'y a pas de solution.
Une fois éliminés les booléens nuls, s'il y a une solution c'est que T est la somme des Ti qui restent.
par exemple 2a+3b+5c+2d+3e+2f+5g+20h = 3,5 (ou =100) n'a pas de solution.

Tu es sûr que tu n'as pas oublié quelque chose ?

[antoninelghozi]

Une fois éliminés les booléens nuls

Oui mais comment ?

Le problème n'est pas commun et je ne suis pas clair. Le truc c'est que je voudrais avoir une méthode pour résoudre ce genre de souci mais avec plus de Ti par exemple. Je suppose que ça se fait uniquement numériquement en essayant toutes les possibilités ?

[gg0]

"Oui mais comment ?" ???? Tu ne sais pas que si un facteur est nul, le produit est nul et qu'un terme nul dans une somme ne sert à rien ???
Tu pourrais réfléchir à ce que c'est qu'une solution, sans attendre qu'on t'explique tout y compris les évidences.

Il y a des cas évidents où il n'y a pas de solutions (mon 3,5, par exemple).
A priori, il te faut envisager tous les sous-ensembles de {T1, T2, ... T8} et leurs sommes. Si l'une d'elles vaut T, tu as trouvé une solution.

[antoninelghozi]

Si si je le sais... Et je n'attends pas qu'on m'explique tout, je demande des pistes !

Ce que j'aimerais c'est une méthode analytique. Car oui, si un coeff est nul, le terme associé est nul sauf que ça fait un paquet de possibilités à tester, c'est ça mon souci. Y a t il une alternative qui te vient à l'esprit pour éviter de tout tester ou alors une méthode/outil pour tout tester rapidement ?

[gg0]

A priori non.

D'où l'intérêt de repérer les cas où il n'y a pas de solutions (genre les Ti entiers, pas T, ou le Ti petits et T grand.
C'est pour cela que je te demandais si tu n'as rien oublié. Avec 8 variables, il y a 255 sommes à tester, avec n variables, il y en a 2^n -1. Sans compter la difficulté de prendre toues les parties possibles sans en oublier.
On peut mettre en place des méthodes récurrentes pour programmer, du genre :
on a 2 cas : a=0 et on a le même problème avec une variable de moins; ou a=0 et on a le même problème avec une variable de moins et T remplacé par T-T1. On a alors 7 niveaux de récurrence.
Mais ce n'est pas un calcul.

[antoninelghozi]

Ok c'est bien ce que je craignais. Je pensais pouvoir exploiter mathématiquement le fait que les inconnues sont booléennes. Je vais partir sur une méthode de test cas par cas. Galère :/
Merci !

[SULREN]

Bonjour,
Je ne sais pas s'il existe une méthode analytique de résolution de ce problème, mais la méthode "force brute" donnera forcément le résultat.
Il suffit d'écrire un programme qui testera toutes les combinaisons possibles des booléens. Si les Ti sont très nombreux (des centaines) ce programme sera peut être fastidieux à écrire, mais son temps d'exécution ne sera pas long.

Certes.... ce n'est pas glorieux comme approche!

[Resartus]

Bonjour,
La méthode "brutale" consiste à calculer les 2^n-1 sommes possibles et à comparer au résultat cherché. Cela monte en effet très vite avec le nombre n
Il existe une méthode plus efficace (mais qui demande un peu de plus de programmation) qui est ce qu'on appelle l'algorithme gourmand.
Il faut commencer par ranger les facteurs du plus grand au plus petit. Ensuite on commence par prendre le plus grand, le soustraire au résultat cherché, et continuer à soustraire les termes un après l'autre, jusqu'à ce que soit on trouve zero (et c'est gagné), soit le résultat devient négatif. Si c'est le cas on revient en arrière, on élimine l'avant dernier terme utilisé, et on recommence à soustraire les termes plus petits. Quand ce redevient négatif, on élimine l'avant avant dernier, etc. On arrête sur un échec quand la somme de tous les termes plus petits non encore inclus (qu'on a pu calculer au préalable) devient inférieure au résultat.
Cela permet d'économiser pas mal de temps quand les facteurs ont des ordres de grandeur très différents.

Je crois me souvenir qu'on trouve cet algorithme dans la bible de la programmation "the art of computer programming" de Donald Knuth (disponible en ligne)

[Sethy]

Je pense que le ratio des Tx/Ty a son importance. Imaginons que celui-ci soit à chaque fois le même, cela revient simplement à faire un changement de base.

En base 10, c'est évident (dans 14025 on voit tout de suite le booléen à zéro). Dans les autres bases, c'est moins évident mais le principe est le même.

Je me trompe où c'est lié à la recherche des nombres premiers ?

[Resartus]

Rebonjour

Le problème est une des variantes du problème du sac à dos.

Mais, contrairement à ce que j'avais écrit de mémoire dans ma réponse précédente, quand les multiplicateurs sont booléens (c'est ce qu'on appelle un Knapsack 0-1), l'algorithme glouton n'est pas adapté. Une méthode exacte utilisable dans ce cas est la méthode de programmation dynamique, mais avec un risque, selon les valeurs des facteurs de départ, d'être plus lente que la force brute...
L'article wikipedia en donne les principes généraux

https://fr.wikipedia.org/wiki/Probl%...sac_%C3%A0_dos.

[gg0]

Sethy,

je n'ai rien compris à ce que tu racontes à part la première phrase (et encore, je ne sais pas pourquoi tu dis ça.). La phrase "dans 14025 on voit tout de suite le booléen à zéro" est particulièrement incompréhensible, il n'y a pas de booléens !!
Peux-tu t'expliquer ?

Cordialement.

[Sethy]

Bonjour,

Je voudrais trouver toutes les solutions de l'équation suivante :

T1*a+T2*b+T3*c+T4*d+T5*e+T6*f+ T7*g+T8*h=T

Avec T1...T8 et T des réels positifs et a...h des booléens.

Comment procéder rapidement ?
Merciiii

Bonjour gg0,

J'édite, effectivement tu as raison.

Ca ne marche que s'il s'agit des puissances de 2. J'avais d'abord pensé à cela et j'ai trop vite généralisé.

Sethy