Recherche dichotomique
Bonjour,
J' ai corrigé un exercice mais je ne sais pas si c'est correct ou bien il y a des fautes.
l'exercice est le suivant :
Ecrire une fonction qui permet de réaliser une recherche dichotomique sur une matrice. Les éléments de la matrice sont organisés de la manière suivante :
Ma correction :
Svp, si ma proposition est fausse, aidez moi à corriger cet exercice . Merci d'avance
J' ai corrigé un exercice mais je ne sais pas si c'est correct ou bien il y a des fautes.
l'exercice est le suivant :
Ecrire une fonction qui permet de réaliser une recherche dichotomique sur une matrice. Les éléments de la matrice sont organisés de la manière suivante :
- Les lignes de ce tableau sont tous trié par ordre croissant.
- le maximum de chaque ligne est inférieur au minimum de la ligne suivante.
Ma correction :
Fontion RechDicho ( M: Matrice; L, c: entier; n: entier): booleen
var
minL , maxL, min, max, m, ml : entier
Début,
minL<-- 1
maxL <-- L
Tantque ( minL<= maxL) faire
mL <-- (minL + maxL)Div 2 // calculer l'indice de la ligne de milieu
Si ((x>= T[ mL, 1]) Et (x<=T[mL, c] )) alors
min <-- 1
max <-- c
Tantque (min <= max ) faire
m <-- (min +max) div 2 // calculer l'indice du milieu dans la ligne "m"
Si ( M[mL, m] = x ) alors
RechDicho <-- vrai
Sinon
Si ( M [mL, m] < x ) alors // effectuer la recherche dans la 2ème moitié de la ligne
min <-- m + 1
sinon // si x < M[ mL, m] faire la recherche dans la 1er moitié de la ligne
max <-- m-1
finsi
finsi
finTq
RechDicho <-- Faux
Sinon
si ( x < T[ mL, 1]) alors
maxL <-- mL - 1
Sinon
minL <-- mL + 1
Finsi
FinTq
RechDicho <-- Faux
Fin
Svp, si ma proposition est fausse, aidez moi à corriger cet exercice . Merci d'avance
2 réponses
-
ModérateurBonjour,
C'est très compliqué tout ça... en particulier l'imbrication de deux boucles TantQue me laisse à penser que c'est faux ou tout du moins que ce n'est pas une recherche par dichotomie.
A priori la solution vient en deux temps : recherche de la bonne ligne, puis recherche de la bonne case, mais pas les deux en même temps.
Remarque : ça devrait être plus simple avec une fonction récursive.-
-
-
-
-
Contributeur@AnnaMets tes deux boucles l'une après l'autre, puis éloigne toi, respire, et réfléchis.
-
-
ContributeurQuelques suggestions pour commencer : ajouter des commentaires qui décrivent ta logique, soigner l'indentation, décrire à quoi servent tes variables, déclarer x et T.
Pour le reste, je ne vois pas d'erreur.-
-
-
Contributeur@yg_beLe plus simple, c'est de suivre la suggestion de KX, et de faire un premier TantQue qui cherche la ligne où pourrait se trouver la valeur. Et un second TantQue qui cherche dans cette ligne.
-
-