Algorithmique Dichotomie
Dredge3
-
KX Messages postés 19031 Statut Modérateur -
KX Messages postés 19031 Statut Modérateur -
Bonjour,
j'ai un exercice qui est :
Ecrire une fonction qui indique si un entier Val est présent dans une tableau T d'entiers à une dimension de taille N.Utiliser une recherche par dichotomie.(le tableau est bien entendu trié par ordre croissant)
J'ai fait cette Fonction : (je suis quasiment certain qu'elle est bonne, mais je suis sure qu'elle peut être amélioré)
Fonction Rechercher (T, N, Val) : booléen
Paramètres par valeur : T : Tableau [1..N] d'entiers
----------------------------Val, N : Entiers
Variables : Deb, Fin : Entiers
-------------Flag : booléen
Début
-----------Deb <== 1
-----------Fin <== N
-----------Flag <== Faux
---Répéter
---------------N <== (Deb + Fin) div 2
---------------Si T[N] = Val Alors
---------------------Flag <== vrai
---------------Sinon
---------------------Si Val < T[N] Alors
--------------------------Fin <== N
---------------------Sinon
--------------------------Deb <== N
---------------------Finsi
---------------Finsi
---jusqu'à [Deb = (Fin-1)] ou Flag = vrai
---Si Flag = vrai Alors
-------Retourner Flag
---Sinon
-------Si T[Deb] = Val ou T[Deb + 1] = Val Alors
------------Flag <== vrai
-------Finsi
---Finsi
---Retourner Flag
Fin
Pouvez vous me conseiller ?
Merci !
j'ai un exercice qui est :
Ecrire une fonction qui indique si un entier Val est présent dans une tableau T d'entiers à une dimension de taille N.Utiliser une recherche par dichotomie.(le tableau est bien entendu trié par ordre croissant)
J'ai fait cette Fonction : (je suis quasiment certain qu'elle est bonne, mais je suis sure qu'elle peut être amélioré)
Fonction Rechercher (T, N, Val) : booléen
Paramètres par valeur : T : Tableau [1..N] d'entiers
----------------------------Val, N : Entiers
Variables : Deb, Fin : Entiers
-------------Flag : booléen
Début
-----------Deb <== 1
-----------Fin <== N
-----------Flag <== Faux
---Répéter
---------------N <== (Deb + Fin) div 2
---------------Si T[N] = Val Alors
---------------------Flag <== vrai
---------------Sinon
---------------------Si Val < T[N] Alors
--------------------------Fin <== N
---------------------Sinon
--------------------------Deb <== N
---------------------Finsi
---------------Finsi
---jusqu'à [Deb = (Fin-1)] ou Flag = vrai
---Si Flag = vrai Alors
-------Retourner Flag
---Sinon
-------Si T[Deb] = Val ou T[Deb + 1] = Val Alors
------------Flag <== vrai
-------Finsi
---Finsi
---Retourner Flag
Fin
Pouvez vous me conseiller ?
Merci !
2 réponses
-
Je n'ai pas regardé en détail vu que tu es sûr que ta fonction est bonne, mais une amélioration est de penser récursif, ça simplifie le code (et l'esprit) :
C'est à dire appeler la fonction dans elle même :
Fonction Rechercher(T, N, Val) : Booléen Retourner Rechercher_Recursif(T,Val,1,N) Fin Fonction Rechercher_Recursif(T,Val,Deb,Fin) : Booléen Si (Deb >= Fin) Alors Retourner (Val = T[Start]) Sinon Milieu <== (Deb+Fin)/2 Si (Val = T[Milieu]) Alors Retourner Vrai Sinon Si (Val < T[Milieu]) Alors Retourner Rechercher_Recursif(T,Val,Deb,Milieu-1) Sinon Retouner Rechercher_Recursif(T,Val,Milieu+1,Fin) FinSi FinSi FinLa confiance n'exclut pas le contrôle -
Bah justement j'aimerais éviter la récursivité (vu que je sais comment faire).
Tu peux regarder vite fait l'algorithme si tu as le temps ?
(Car je ne suis même pas sure qu'il soit correct)
