IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

DFS ? Trouver l'input pour A < A


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2020
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 21
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2020
    Messages : 2
    Points : 1
    Points
    1
    Par défaut 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.

    Nom : Capture d’écran 2020-11-26 à 14.42.18.png
Affichages : 317
Taille : 43,9 Ko

    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

  2. #2
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 160
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 74
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 160
    Points : 2 224
    Points
    2 224
    Billets dans le blog
    9
    Par défaut DFS ? Trouver l'input pour A < A
    Bonjour,

    Citation Envoyé par volrod01 Voir le message
    ... 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 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 Voir le message
    ... 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).


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2020
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 21
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2020
    Messages : 2
    Points : 1
    Points
    1
    Par défaut
    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...

Discussions similaires

  1. [ODBC/ADO]Où trouver des tutoriaux pour VC++ ?
    Par tyarcaouen dans le forum Décisions SGBD
    Réponses: 1
    Dernier message: 06/03/2006, 12h43
  2. [Traitement d'image] Où trouver des images pour illustrer mon site ?
    Par langela94 dans le forum Webdesign & Ergonomie
    Réponses: 4
    Dernier message: 24/01/2006, 18h44
  3. Où trouver un environnement pour faire du PROLOG ?
    Par cladsam dans le forum Prolog
    Réponses: 4
    Dernier message: 04/05/2005, 18h12
  4. Ou trouver des tut pour Dx9 en c#?
    Par sen dans le forum DirectX
    Réponses: 3
    Dernier message: 24/02/2004, 15h44
  5. [Kylix] Trouver des composants pour Kylix 3
    Par busy999 dans le forum EDI
    Réponses: 2
    Dernier message: 17/02/2003, 15h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo