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 !
A voir également:
- Algorithmique Dichotomie
- Videosurveillance algorithmique - Accueil - Protection
- Problème codage python méthode par dichotomie - Forum Python
- Exercice en Algorithmique (Boucles) ✓ - Forum Algorithmes / Méthodes
- Trouver un nombre entre 0 et 10 par dichotomie ✓ - Forum Python
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 :
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
