Discussion :

[volrod01]

Bonjour,

Je suis actuellement confronter à un problème assez "complexe".
J'ai essayé en vain de répondre à se problème que je dois ensuite intégrer à du nodejs.

Voici le problème :

J'ai 3 valeurs qui sont A,B,C.

J'échange A contre B puis B contre C puis enfin C contre A.
A -> B -> C -> A
Ceci est un échange triangulaire.

La seule contrainte est que quand j'échange C contre A, la valeur de A dois être supérieur celle de A au debut (ma sortie dois être plus grande que mon entrée).


À prendre en compte :

- Pour savoir si A de sorti est positif je dois "simuler" tout le reste de l'échange jusqu'à tomber sur la bonne valeur du A d'entrée (qui fera que le A de sorti > A d'entrée)...

On m'as parlé vaguement d'algorithme de DFS, Bellman-Ford, SPFA...
J'ai aussi cette formule sous la main mais j'avoue que je ni comprends pas grand chose.



Si quelqu'un ici à des connaissances en algorithme j'aimerais vraiment, vraiment, qu'il puisse m'expliquer selon lui qu'elle serais la façon la plus performante de résoudre se type de problème et via qu'elle algorithme.


Merci d'avance pour votre temps ! Dans l'espoir d'une réponse

[wiwaxia]

Bonjour,

... J'ai 3 valeurs qui sont A,B,C.

J'échange A contre B puis B contre C puis enfin C contre A.
A -> B -> C -> A
Ceci est un échange triangulaire.

La seule contrainte est que quand j'échange C contre A, la valeur de A dois être supérieur celle de A au debut (ma sortie dois être plus grande que mon entrée)...

Il s'agit effectivement d'une suite périodique de triplets, de période égale à trois, et dont la codification exige l'intervention d'une quatrième variable, destinée à mémoriser la valeur de la première.
La relation de récurrence repose sur les 4 instructions élémentaires:

Code :

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

D:= A; A:= B; B:= C; C:= D;

ou si l'on veut: A ---> D ; B ---> A ; C ---> B ; D ---> C ;
elle génère la suite: <A, B, C> ---> <B, C, A> ---> <C, A, B> ---> <A, B, C> ---> ...

Que la nouvelle valeur de (A) soit supérieure à celle de l'ancienne dépend de l'ordre des valeurs présentes dans le triplet initial T₀ = <A₀, B₀, C₀>
On peut par exemple poser:

M1 = Min(A₀, B₀, C₀) , M3 = Max(A₀, B₀, C₀) , M2 = A₀ + B₀ + C₀ - M1 - M3 (valeur intermédiaire);

on voit alors que six cas se présentent pour le triplet de départ (T₀), à partir desquels il est facile de déterminer le nombre minimal (n) d'étapes à l'issue desquelles la condition favorable A_n > A_n-1 est réalisée pour la première fois (à condition que les 3 termes ne soient pas tous égaux !):
T₀ = <M1, M2, M3> , <M1, M3, M2>, <M2, M3, M1>, <M2, M1, M3>, <M3, M1,M2>, <M3, M2, M1> .

... Pour savoir si A de sorti est positif je dois "simuler" tout le reste de l'échange jusqu'à tomber sur la bonne valeur du A d'entrée (qui fera que le A de sorti > A d'entrée) ...

Le signe éventuel de (A) n'entre pas en compte: il peut d'agir de triplets d'entier naturels, ou relatifs, ou de réels de signe quelconque.

La suite peut être envisagée pour tout ensemble d'objets, pour chacun desquels il est possible d'établir une comparaison; (X < Y) ou (X > Y).

[volrod01]

Bonjour,

Merci du temps que vous m'accordez !

Je ne pense pas avoir compris le raisonnement...

Est-ce qu'il serait possible pour vous de me faire un ou deux petits exemple sous forme de calculs et non de formule pour que je puisse comprendre la formule, s'il vous plait...


Merci d'avance...