Recherche dichotomique

Anna -  
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   -
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 :
  • 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

KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Bonjour,

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.
1
Anna
 
on n'a pas encore vu la notion de récursivité dans notre cours. svp comment puis je la corriger
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Commence déjà par désimbriquer tes boucles et faire la recherche en deux temps comme je l'ai indiqué précédemment.

L'algo des deux boucles devrait être quasiment identique à part que la première boucle recherche une ligne et que la deuxième recherche une colonne.
0
Anna
 
Merci, je vais essayer.
0
Anna
 
Si je dés-imbrique, j'arrive pas à établir une liaison entre les 2 boucles.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584 > Anna
 
Mets tes deux boucles l'une après l'autre, puis éloigne toi, respire, et réfléchis.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   Ambassadeur 1 584
 
Quelques 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.
0
Anna
 
Merci, mais j'ai déjà écris les remarques,
oui j'ai oublié de déclarer x et T, mais à part ça quelles sont les fautes.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
Il y a deux erreurs similaires, je pense : dès que tu changes la valeur de "RechDicho", tu dois arrêter ton algorithme. Sinon, ton algorithme va boucler et/ou changer la réponse et puis boucler.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584 > yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention  
 
Le 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.
0
Anna
 
Je vais essayer encore merci.
0