1 pièce(s) jointe(s)
DFS ? Trouver l'input pour A < A
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.
Pièce jointe 585089
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 :)
DFS ? Trouver l'input pour A < A
Bonjour,
Citation:
Envoyé par
volrod01
... 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:
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 T0 = <A0, B0, C0>
On peut par exemple poser:
M1 = Min(A0, B0, C0) , M3 = Max(A0, B0, C0) , M2 = A0 + B0 + C0 - M1 - M3 (valeur intermédiaire);
on voit alors que six cas se présentent pour le triplet de départ (T0), à partir desquels il est facile de déterminer le nombre minimal (n) d'étapes à l'issue desquelles la condition favorable An > An-1 est réalisée pour la première fois (à condition que les 3 termes ne soient pas tous égaux !):
T0 = <M1, M2, M3> , <M1, M3, M2>, <M2, M3, M1>, <M2, M1, M3>, <M3, M1,M2>, <M3, M2, M1> .
Citation:
Envoyé par
volrod01
... 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).
