Algorithmique Dichotomie
Fermé
Dredge3
-
28 nov. 2012 à 20:01
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 - 28 nov. 2012 à 21:20
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 - 28 nov. 2012 à 21:20
2 réponses
KX
Messages postés
16668
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mars 2023
3 004
Modifié par KX le 28/11/2012 à 20:27
Modifié par KX le 28/11/2012 à 20:27
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
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)
Tu peux regarder vite fait l'algorithme si tu as le temps ?
(Car je ne suis même pas sure qu'il soit correct)
KX
Messages postés
16668
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mars 2023
3 004
28 nov. 2012 à 21:20
28 nov. 2012 à 21:20
Je viens de faire une implémentation (vite fait), il semble que le résultat soit correct, sauf si N=1 ou N=2 dans ce cas la boucle tourne à l'infini...