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

Discussion: Problème du cavalier

  1. #1
    Nouveau membre du Club Avatar de bj303931
    Femme Profil pro
    Étudiant
    Inscrit en
    février 2016
    Messages
    75
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : février 2016
    Messages : 75
    Points : 27
    Points
    27

    Par défaut Problème du cavalier

    Mon prof d'algo m'a donné un SUPER problème qu'évidemment je n'arrive pas à résoudre...

    Voici ce super truc :
    Trouver un algorithme tel que la cavalier du jeu d'échec passe sur toutes les cases.

    N.B: Lol
    Pour info les déplacements possibles par un cavalier : Nom : CavalierDeplacement.png
Affichages : 238
Taille : 230,4 Ko

    Donc me voilà dedans. Voici l'algo que j'ai pondu:


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    Tant que la file est non vide*:
    
    	Pour i dans l’ensemble des positions*:
    
    		déplacer le cavalier
    		Si la case n’est pas dans la file*: tester la position suivante
    Donc le cavalier tourne dans ses positions. Mais si la case à déjà été chevauchée (XD) on va au suivant.

    J'aimerais avoir vos avis merci.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 173
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 173
    Points : 4 544
    Points
    4 544

    Par défaut

    s
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    Tant que la file est non vide*:
    
    	Pour i dans l’ensemble des positions*:
    
    		déplacer le cavalier
    		Si la case n’est pas dans la file*: tester la position suivante
    Tu as donc une file.
    Soit cette file est vide au début du traitement, et dans ce cas, le programme s'arrête immédiatement.
    Soit cette file est non-vide, et comme il n'y a aucune instruction qui modifie cette file, le programme va boucler indéfiniment.

    Tu es très loin, très très loin de la solution.
    Ton programme doit pouvoir gérer des cas comme ça : le cavalier a le choix entre le mouvement A1 A1 A3 ... , explorons le mouvement A1. Au 2ème mouvement, on n'a pas le choix, seule option = B1... explorons B1. Zut plus de mouvement possible. Revenons en arrière. Et donc il faut considérer le mouvement A2 au lieu de A1.

    Le mot clé pour t'aider, c'est :parcours d'arbre.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Invité
    Invité(e)

    Par défaut

    hello,

    J'aimerais avoir vos avis merci.
    l'idée est correcte.

    il faut etre plus précis en revanche:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    pour la position actuelle
        pour chaque case de destination possible du cheval (pas seulement "la suivante")
            si case visitée
                rien faire...
            sinon
                marquer case actuelle comme visitée
                visiter(case)
                demarquer case actuelle comme visitée
            finsi
    il reste à définir la condition d'arret, ainsi que "backtracker" l'information que l'arret a été satisfait (ou qu'il n'y a pas de solutions??)

  4. #4
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 743
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 743
    Points : 4 430
    Points
    4 430

    Par défaut

    salut

    tu peut travailler par symétrie avec un cavalier

    nous savons que celui ci se déplace de deux case sur un axe est d'une case sur l'autre ce qui pourrait nous faire penser a cercle de défense
    nous savons qu'un cercle a 4 quadrants avec ces deux information tu n'as besoin de connaitre que deux déplacements
    le reste étant des symétrie, il te faut donc connaitre disons le déplacement selon l'axe des x et celui des y

    si nous comptons bien le cheval ne peut donc avoir que 8 déplacements possible 4 horizontales et 4 verticales



    mes deux cents
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  5. #5
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 743
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 743
    Points : 4 430
    Points
    4 430

    Par défaut

    salut

    tu peut pour simplifier ta recherche de parcourt noter les case
    par exemple par le nombre de possibilité de saut

    exemple pour un echiquier de 8 par 8


    2 3 4 4 4 4 3 2
    3 4 6 6 6 6 4 3
    4 6 8 8 8 8 6 4
    4 6 8 8 8 8 6 4
    4 6 8 8 8 8 6 4
    4 6 8 8 8 8 6 4
    3 4 6 6 6 6 4 3
    2 3 4 4 4 4 3 2

    a chaque saut tu décrément de 1 les cases "a proximité" de la case selectionné
    et tu met la case sélectionné a zéro ensuite tu cherche la case "a proximité"
    ayant le moins de possibilité sauf évidement les case a zéro puisque qu'elles sont
    déjà utilisé
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  6. #6
    Membre éprouvé
    Profil pro
    Inscrit en
    avril 2004
    Messages
    722
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations forums :
    Inscription : avril 2004
    Messages : 722
    Points : 1 050
    Points
    1 050

    Par défaut

    Intéressante application de la récursivité.Nom : cav.JPG
Affichages : 132
Taille : 58,3 Ko
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

Discussions similaires

  1. [Jeu d'échecs] Problème du cavalier
    Par Arbraz dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 06/11/2015, 16h32
  2. [Jeu d'échecs] Problème du cavalier
    Par Arbraz dans le forum Programmation multimédia/Jeux
    Réponses: 0
    Dernier message: 05/11/2015, 09h59
  3. [Python 2.X] Problème du cavalier : Amélioration d'un code récursif
    Par Zeoldest dans le forum Calcul scientifique
    Réponses: 2
    Dernier message: 20/07/2015, 13h53
  4. Backtracking probléme du cavalier
    Par buddhazero dans le forum Débuter
    Réponses: 4
    Dernier message: 28/04/2008, 00h08

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