Recherche dichotomique
Anna
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
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 :
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
A voir également:
- Recherche dichotomique en c
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Rechercher ou entrer l'adresse mm - recherche google - Guide
- Recherche photo - Guide
- Je recherche une chanson - Guide
- Rechercher ou entrer l'adresse 4 - recherche google ✓ - Forum Windows
2 réponses
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.
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.
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.
Pour le reste, je ne vois pas d'erreur.
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.