[Débutant] Recherche dichotomique récursive

**kenon69** · 09/10/2008, 22h07

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.

**Obsidian** · 09/10/2008, 22h39

Envoyé par kenon69

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.

**kenon69** · 09/10/2008, 23h45

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

**Obsidian** · 10/10/2008, 01h42

Envoyé par kenon69

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).

**kenon69** · 10/10/2008, 15h41

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 !!

**kenon69** · 10/10/2008, 15h50

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
          ;;;;;

**Obsidian** · 13/10/2008, 18h42

Voici une copie du message privé que tu m'as envoyé :

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.

**kenon69** · 13/10/2008, 23h51

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)

[Débutant] Recherche dichotomique récursive

Assembleur

Discussions similaires

Partager

Partager