Différences entre versions de « Js algo td4 »
(Page créée avec « = Introduction = En algorithmique, la recherche dichotomique relève du principe ''diviser pour régner'' qui est ici pris au pied de la lettre puisque l'intervalle de rec... ») |
|||
| Ligne 23 : | Ligne 23 : | ||
* ''0'' si ''a'' == ''b''; | * ''0'' si ''a'' == ''b''; | ||
* une valeur positive si ''a'' > ''b''; | * une valeur positive si ''a'' > ''b''; | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Exercice 2 == | == Exercice 2 == | ||
Version du 29 avril 2014 à 21:02
Introduction
En algorithmique, la recherche dichotomique relève du principe diviser pour régner qui est ici pris au pied de la lettre puisque l'intervalle de recherche est divisé en deux sous-intervalles de même taille.
À chaque étape de l'algorithme, on calcule le milieu m de l'intervalle de recherche et on compare la valeur avec la valeur au milieu du tableau.
![{\displaystyle T[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ef258bdc16ff9a82c515e02a3c076666bd75c7d)
Au départ . Trois situations se présentent :
![{\displaystyle I=[1\,,n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae68bcdac688d1941d91eebfe8f80dcedbc9f0a9)
- : la recherche est terminée.
- : il faut poursuivre la recherche dans la moitié gauche de l'intervalle .
- : il faut poursuivre la recherche dans la moitié droite de l'intervalle .
![{\displaystyle x=T[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/767f21715b738db16e1f839a65c772acacbae04d)
![{\displaystyle x<T[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e15e56a7ab1693b4713466e6f39594a9b4ac0c26)
![{\displaystyle x>T[m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/207865cb8218f7e65803d205d0dca93c7930c678)
Dans les deux derniers cas, la recherche continue avec le même procédé, on divise à nouveau l'intervalle en deux moitiés et ainsi de suite jusqu'à ce que l'intervalle de recherche soit réduit à un seul terme.
L'algorithme est la stricte application de ce principe.
Application
Soit T un tableau de noms:
var T = new Array("Alain","Antoine", "Bernard", "Colin", "Christine","François", "Guy","Gérard", "Léa","Léon","Louis","Nathalie","Serge","Sylvie","Sylvain","Vincent");
Exercice 1
Écrire la fonction compare_char qui prend en paramètre deux caractères a et b et qui renvoie:
- une valeur négative si a < b;
- 0 si a == b;
- une valeur positive si a > b;
Exercice 2
Écrire la fonction get_half qui prend en paramètre le tableau T ainsi que la valeur recherchée, x. Cette fonction renvoie un tableau qui correspond à la moitié du tableau T ou se trouverai la valeur x.
Exercice 3
Écrire la fonction main qui prend en paramètre une chaîne de caractères name et qui utilise les fonctions précédentes pour retourner:
- l'index de la chaîne name;
- la phrase suivante La chaîne n'existe pas.