Recherche dichotomique

Fermé
Anna - 15 déc. 2016 à 21:10
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 - 16 déc. 2016 à 07:04
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 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
15 déc. 2016 à 21:29
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
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 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 019
15 déc. 2016 à 21:48
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