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

Assembleur Discussion :

[Débutant] Recherche dichotomique récursive


Sujet :

Assembleur

  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    juillet 2006
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : juillet 2006
    Messages : 6
    Points : 2
    Points
    2
    Par défaut [Débutant] Recherche dichotomique récursive
    Salut, je bloque depuis plusieurs jours sur une fonction permettant de faire une recherche dichotomique dans un tableau d'entiers triés. Cette fonction a comme arguments : la valeur à rechercher, l'adresse du tableau en mémoire et la taille du tableau. Quelqu'un pourrait me proposer un code ? Je suis ouvert à toutes les suggestions.

  2. #2
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    septembre 2007
    Messages
    7 256
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2007
    Messages : 7 256
    Points : 23 261
    Points
    23 261
    Par défaut
    Citation Envoyé par kenon69 Voir le message
    kelkun pourrait me proposer un code?je suis ouvert a toutes les suggestions.
    1) Montre-nous ce que tu as déjà produit, on t'aidera ensuite (parce que c'est élémentaire, comme problème).

    2) Quelqu'un (dans ta classe ?) a déjà eu le même problème ici. Fais une recherche.

    3) Ici, c'est le forum Assembleur. Tu es sûr que ton message ne serait pas mieux dans le Forum C ?

    Bon courage.

  3. #3
    Candidat au Club
    Profil pro
    Inscrit en
    juillet 2006
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : juillet 2006
    Messages : 6
    Points : 2
    Points
    2
    Par défaut
    en fait je suis debutant en assembleur et pour le moment je sais juste manipuler les piles, j'aimerais donc savoir comment declarer les tableaux et y mettre des valeurs, de même comment acceder a ces valeurs et a leurs indices.
    merci d'avance

  4. #4
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    septembre 2007
    Messages
    7 256
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2007
    Messages : 7 256
    Points : 23 261
    Points
    23 261
    Par défaut
    Citation Envoyé par kenon69 Voir le message
    en fait je suis debutant en assembleur et pour le moment je sais juste manipuler les piles, j'aimerais donc savoir comment declarer les tableaux et y mettre des valeurs, de même comment acceder a ces valeurs et a leurs indices.
    merci d'avance
    Montre-nous ton code actuel !

    Si tu as besoin de stocker des données constantes dans ton code, utilise db (ou dw, dd, ...) et précise les valeurs que tu veux. Elles seront insérées à l'endroit où tu les as déclarés, donc dans le segment de code ou celui de données.

    Pour les lire, utilises un registre tel que ESI, colle-z-y l'adresse du début de ta liste, et appuie-toi soit sur les facilités des modes d'adressage (indexation, avec EBP, par exemple), soit sur des instructions dédiés comme LODS ou STOS (en considérant bien sûr que tu travailles sur x86).

  5. #5
    Candidat au Club
    Profil pro
    Inscrit en
    juillet 2006
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : juillet 2006
    Messages : 6
    Points : 2
    Points
    2
    Par défaut code actuel
    Je ne sais pas s'il est bon mais j'ai fait le programme principal et il me reste juste la fonction de recherche à écrire; comme vous le constatez, j'ai empilé les éléments du tableau, la taille du tableau et l'élément recherché sur une pile, je ne sais pas si l'approche est bonne.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    .STACK ox200
    .DATA
         tab dw 1,3,4,5,6,7,8    /declaration d'un tableau de 7 elements
    N: LONG(7)              /N=7,c'est le nombre d'elements du tableau
     r: LONG(3)              / r est l'element recherché
    .CODE
             BR(main)            /on saute a main, le programme principal
     
    main:   CMOVE(stack,sp)    /initialisation de sp a la taille de la pile
              CMOVE(N,r2)        /mettre N=7 ds r2
              PUSH(r2)           /mettre le nombre d'elt N de tab sur la pile
              CMOVE(r,r2)        /mettre r=3 ds r2
              PUSH(r2)           /mettre l'element a rechercher sur la pile
              LD(tab,r1)         /mettre le 1er element de tab (tab[0]) ds r1
              PUSH(r1)           /mettre le 1er element du tableau sur la pile
              CMOVE(1,r2)        /mettre 1 ds r2
    repeat:  
              LD(r2,tab,r0)      /mettre ds r0 la valeur contenu a l'adresse tab+r2
              PUSH(r0)           /mettre cette valeur sur la pile
              ADDC(r2,1,r2)      /incrementer le contenu de r2
              CMPLTC(r2,N,r3)    /si r2<N, alors R3=1
              BNE(r3,repeat)     /si r3!=0, se brancher a repeat
     
              BR(recherche)      /aller a la fonction de recherche
              DEALLOCATE(9)      /liberer l'espace occupé par les arguments sur la pile
     
    recherche:
              PUSH(LP)           /on sauvegarde l'adresse de retour sur la pile
              PUSH(BP)           /on sauvegarde le cadre de pile precedent
              MOVE(SP,BP)        /on initialise le cadre de pile courant
    ... c'est là que j'en suis !!

  6. #6
    Candidat au Club
    Profil pro
    Inscrit en
    juillet 2006
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : juillet 2006
    Messages : 6
    Points : 2
    Points
    2
    Par défaut
    Tout compte fait je ne crois pas qu'on doive mettre les éléments du tableau sur la pile mais plutôt l'adresse du tableau, qui est en realité l'adresse du 1er élément du tableau. D'où la modification :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    .STACK ox200
    .DATA
         TAB dw 1,3,4,5,6,7,8    /declaration d'un tableau de 7 elements
         N: LONG(7)              /N=7, c'est le nombre d'elements du tableau
         r: LONG(3)              / r est l'element recherché
    .CODE
             BR(main)            /on saute a main, le programme principal
     
    main:   CMOVE(stack,SP)    /initialisation de sp a la taille de la pile
              CMOVE(N,r2)        /mettre N=7 ds r2
              PUSH(r2)           /mettre le nombre d'elt N de tab sur la pile
              CMOVE(r,r2)        /mettre r=3 ds r2
              PUSH(r2)           /mettre l'element a rechercher sur la pile
              MOV(TAB,r3)        /mettre l'adresse du 1er elt du tableau ds r3
              PUSH(r3)           /mettre cette adresse sur la pile
     
              BR(recherche)      /aller a la fonction de recherche
              DEALLOCATE(3)      /liberer l'espace occupé par les arguments sur la pile
     
    recherche:
              PUSH(LP)           /on sauvegarde l'adresse de retour sur la pile
              PUSH(BP)           /on sauvegarde le cadre de pile precedent
              MOVE(SP,BP)        /on initialise le cadre de pile courant
              ;;;;;

  7. #7
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    septembre 2007
    Messages
    7 256
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2007
    Messages : 7 256
    Points : 23 261
    Points
    23 261
    Par défaut
    Voici une copie du message privé que tu m'as envoyé :

    Citation Envoyé par kenon69
    slt ,
    j'ai un pb j'aimerais pouvoir renvoyé une valeur si l'element recherché ne se trouve pas ds le tableau d'autre part lorskon divise le tableau en 2 et qu'a l'appel suivant de la fonction, les adresses de debut et de fin de la fonction prenne de nouvelles valeurs, quel test doit on effectué sur l'adresse de fin pour savoir que c'est la bonne(pour l'adresse de debut ya pas de problème).

    Merci d'avance
    Donc, comme répondu par MP, pas de style SMS, ni de questions techniques en privé. Merci.

    Pour le reste, je ne vois pas ce qui t'empêche de renvoyer une valeur précise si la valeur recherchée est absente, à part le fait de savoir quand est-ce qu'on a fini de chercher.

    Pour cela, retiens simplement que tu divises la taille de la plage à rechercher par deux à chaque itération. Donc, au dernier coup, cette taille vaut 1, et au coup suivant, 1/2 = 0 si tu restes sur le format entier. Par conséquent, si le résultat de ta division par deux est nul, tu sautes vers la routine de ton choix, tu charges la valeur de ton choix également, signifiant « nombre non trouvé », et tu sors.

    En ce qui concerne « l'adresse de fin de ton tableau », ta fonction ne la gère pas (à première vue), mais elle utilise un pointeur sur ton tableau (soit l'adresse du début), et une taille. Ce sont ces deux derniers paramètres qu'il faut mettre à jour quand tu itères ta fonction.

  8. #8
    Candidat au Club
    Profil pro
    Inscrit en
    juillet 2006
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : juillet 2006
    Messages : 6
    Points : 2
    Points
    2
    Par défaut code
    Voici mon code final, je sais pas si il marche :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    recherche:
     
                         PUSH(LP) |on sauvegarde l'adresse de retour sur la pile
                         PUSH(BP) |on sauvegarde le cadre de pile precedent
                         MOVE(SP,BP) |on initialise le cadre de pile courant
                         PUSH(r1) |sauvegarde du registre r1
                         PUSH(r2) |sauvegarde du registre r2
                         PUSH(r3)
                         PUSH(r4)
                         PUSH(r5)
                         PUSH(r6)
                         PUSH(r7)
                         PUSH(r8) |sauvegarde du registre DI
                         PUSH(r9) |sauvegarde du registre SI
     
                         LD(BP,-12,r1) |chargement de la taille du tableau dans r1
                         LD(BP,-16,r9) |chargement de l'adresse du 1er elt du tableau dans SI
                         LD(BP,-20,r4) |on charge l'element rechercher
                         MULC(r1,4,r1) | Calcul de l'adresse suivant de dernier element du tableau
                         SUB(r1,4,r1)  |
                         ADD(r9,r1,r8) | Placement de cette adresse dans DI
     
     
    bsearch_end :
                         CMPLT(r8,r9,r2) |si DI<SI, r2=1
                         BNE(r2,boucle1) |branchement a boucle1 si r2!=0
     
                        LD(BP,-12,r1) |chargement de la taille du tableau dans r1
                        SHRC(r1,1,r1) |on divise le contenu de r1 par 2
                        MOVE(r1,r7)    |transfert de r1 dans r7
                        MULC(r7,4,r7) |on multiplie par 4
                        ADD(r9,r7,r7) |on obtient l'adresse du milieu du tableau
                        LD(r7,0,r3)   |on charge le contenu du milieu du tableau
                        CMPEQ(r3,r4,r5) | on compare le milieu du tableau a l'element, si r3=r4,alors r5=1
                        BNE(r5,boucle2)
                        CMPLT(r4,r3,r6) |si r4<r3, r6=1
                        BNE(r6,boucle3) |branchement a boucle3 si r6!=0
                        ADDC(r7,4,r7)   | l'element suivant devient le milieu du tableau
                        PUSH(r4) |sauvegarde de l'elt recherché
                        PUSH(r7) |sauvegarde de l'adresse du milieu du tableau qui devient le 1er elt du tableau
                        PUSH(r1) |sauvegarde de la taille du tableau
                        BR(recherche,LP) |nouvel appel de la fonction recherche
                        DEALLOCATE(3)
    boucle1:   
     
     
                         SUB(0,1,r0) |on retourne -1
                         POP(r1)
                         POP(r2)
                         POP(r3)
                         POP(r4)
                         POP(r5)
                         POP(r6)
                         POP(r7)
                         POP(r8)
                         POP(r9)
                         MOVE(BP,SP)
                         POP(BP)
                         POP(LP)
                         JMP(LP,r31)
    boucle2:
                         SUB(r7,r9,r3) |difference entre l'adresse du milieu du tableau et l'adresse du tableau
                         DIVC(r3,4,r3) |on divise par 4
                         MOVE(r3,r0)
                         POP(r1)
                         POP(r2)
                         POP(r3)
                         POP(r4)
                         POP(r5)
                         POP(r6)
                         POP(r7)
                         POP(r8)
                         POP(r9)
                         MOVE(BP,SP)
                         POP(BP)
                         POP(LP)
                         JMP(LP,r31)
     
     
    boucle3:
     
     
                        PUSH(r4) |sauvegarde de l'elt recherché
                        PUSH(r9) |sauvegarde de l'adresse du 1er elt du tableau
                        PUSH(r1) |sauvegarde de la taille du tableau
                        BR(recherche,LP) |nouvel appel de la fonction recherche
                        DEALLOCATE(3)

  9. #9
    Nouveau Candidat au Club
    Femme Profil pro
    etudiante en informatique générale
    Inscrit en
    juin 2021
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Algérie

    Informations professionnelles :
    Activité : etudiante en informatique générale

    Informations forums :
    Inscription : juin 2021
    Messages : 1
    Points : 0
    Points
    0
    Par défaut demande d'aide
    bonjour , j'ai comme interrogation cet exercice :
    int rechDicho(int*tab,int taille , int val, int inf, int sup)

    1ere question : trier le tableau dynamique
    2eme question : recherche dichotomique d'une valeur dans ce tableau trié
    3- utiliser des paramètres par pile .

    de l'aide s'il vous plait ??

  10. #10
    Expert éminent
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    mai 2010
    Messages
    3 022
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : cyber-paléontologue

    Informations forums :
    Inscription : mai 2010
    Messages : 3 022
    Points : 9 426
    Points
    9 426
    Par défaut
    Inutile de faire remonter un topic vieux de 13 ans...
    (et on ne fait pas le devoir des gens non plus ).

  11. #11
    Futur Membre du Club
    Homme Profil pro
    Enseignant
    Inscrit en
    juin 2021
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

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

    Informations forums :
    Inscription : juin 2021
    Messages : 1
    Points : 7
    Points
    7
    Par défaut TRAVAIL
    BONSOIR MelimelAtal , Le devoir est a faire et non pas a faire faire etudiante de la acad b ....

  12. #12
    Expert éminent
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    mai 2010
    Messages
    3 022
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : cyber-paléontologue

    Informations forums :
    Inscription : mai 2010
    Messages : 3 022
    Points : 9 426
    Points
    9 426
    Par défaut
    ah ah toujours amusant de voir ici des profs dénicher leur propre étudiant

Discussions similaires

  1. [Free Pascal] Fonction récursive de recherche dichotomique
    Par fleurose dans le forum Free Pascal
    Réponses: 4
    Dernier message: 13/04/2011, 19h55
  2. Recherche dichotomique
    Par Gryzzly dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 31/12/2005, 11h21
  3. Débutant - Recherche une alternative à TStringGrid
    Par TopDelire dans le forum Débuter
    Réponses: 2
    Dernier message: 27/12/2005, 14h47
  4. [Débutant] Recherche controle ActiveX
    Par jpppaps dans le forum MFC
    Réponses: 2
    Dernier message: 19/10/2005, 17h01
  5. Débutant recherche SGBD ... (mylittlebase ?)
    Par Phil39 dans le forum Débuter
    Réponses: 1
    Dernier message: 10/10/2004, 10h25

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