Différences entre versions de « Js algo td4 »

De The Linux Craftsman
Aller à la navigation Aller à la recherche
Ligne 116 : Ligne 116 :
 
* la phrase suivante ''La chaîne n'existe pas''.
 
* la phrase suivante ''La chaîne n'existe pas''.
  
 
Pour tester le type d'une variable, vous pouvez utiliser le mot clé ''instanceof''.
 
 
Par exemple:
 
 
<pre>
 
var T = new Array();
 
 
if(T instanceof Array){
 
  console.log("Je suis un tableau");
 
}
 
</pre>
 
 
Affichera ''Je suis un tableau''.
 
 
= Application en JavaScript =
 
= Application en JavaScript =
 
== Exercice 1 ==
 
== Exercice 1 ==

Version du 9 mai 2014 à 10:50

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.

Au départ . Trois situations se présentent :

  1.  : la recherche est terminée.
  2.  : il faut poursuivre la recherche dans la moitié gauche de l'intervalle .
  3.  : il faut poursuivre la recherche dans la moitié droite de l'intervalle .

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.

Pseudo-code

Soit T un tableau de noms:

var T = new Array("Alain", "Antoine", "Bernard", "Christine", "Colin", "François", "Gérard", "Guy", "Léa", "Léon", "Louis", "Nathalie", "Serge", "Sylvain", "Sylvie", "Vincent");

Exercice 1

Écrire la fonction compare_char qui prend en paramètres 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;

Solution

function compare_char(a, b) {
   if (a < b) {
      return -1;
   } else if (a > b) {
      return 1;
   }
   return 0;
}

Exercice 2

Écrire la fonction compare_string qui prend en paramètres deux chaînes de caractères x et y et qui renvoie:

  • une valeur négative si x < y;
  • 0 si x == y;
  • une valeur positive si x > y;

Cette fonction doit comparer chacune des lettres des deux chaînes tant qu'il y a égalité !

Pour cela, vous pouvez vous aider de la fonction String.charAt(num) dont voici la documentation:

Syntax

string.charAt(num)

The charAt() method returns the character located at the indexed, num, position passed. This indexing is done from left to right starting with the 0 (zero) position.
If the num passed is not a valid index in the string, -1 is returned.

Solution

function compare_string(a, b) {
   var i = 0;
   while(i < a.length && i < b.length){
      var charA = a.charAt(i);
      var charB = b.charAt(i);
      var compare = compare_char(charA, charB);
      if(compare != 0){
         return  compare;
      }
      i++;
   }
   return 0;
}

Exercice 3

Écrire la fonction get_value qui prend en paramètres le tableau T ainsi qu'une chaîne de caractères, x. Cette fonction, qui utilise la recherche par dichotomie, renvoie un tableau qui correspond à la moitié du tableau T où se trouverait la valeur x, ou bien, la l'index de la valeur recherchée.

Solution

function get_half(T, x) {
	var half = Math.round(T.length / 2);
	console.log(half);
	var half_value = T[half];
	var compare = compare_string(x, half_value);
	var tab_start;
	var tab_end;
	var j = 0;
	if (compare == 0) {
		console.log("TROUVE : "+half);
		return half;
	} else {
		if (compare < 0) {
			console.log("MOITIE INFERIEUR");
			tab_start = 0;
			tab_end = half;
		} else {
			console.log("MOITIE SUPERIEUR");
			tab_start = half;
			tab_end = T.lenght;
		}
		var resultat = new Array();
		for (var i = tab_start; i < tab_end; i++) {
			resultat[j] = T[i];
			j++;
		}
		return resultat;
	}
}

Exercice 4

É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.

Application en JavaScript

Exercice 1

Écrire la fonction compare_char.

Solution

function compare_char(a, b) {
   if (a < b) {
      return -1;
   } else if (a > b) {
      return 1;
   }
   return 0;
}

Exercice 2

Écrire la fonction compare_string.

Solution

function compare_string(a, b) {
   var i = 0;
   while(i < a.length && i < b.length){
      var charA = a.charAt(i);
      var charB = b.charAt(i);
      var compare = compare_char(charA, charB);
      if(compare != 0){
         return  compare;
      }
      i++;
   }
   return 0;
}

Exercice 3

Écrire la fonction get_value.

Solution

function get_half(T, x) {
	var half = Math.round(T.length / 2);
	console.log(half);
	var half_value = T[half];
	var compare = compare_string(x, half_value);
	var tab_start;
	var tab_end;
	var j = 0;
	if (compare == 0) {
		console.log("TROUVE : "+half);
		return half;
	} else {
		if (compare < 0) {
			console.log("MOITIE INFERIEUR");
			tab_start = 0;
			tab_end = half;
		} else {
			console.log("MOITIE SUPERIEUR");
			tab_start = half;
			tab_end = T.lenght;
		}
		var resultat = new Array();
		for (var i = tab_start; i < tab_end; i++) {
			resultat[j] = T[i];
			j++;
		}
		return resultat;
	}
}

Exercice 4

Écrire la fonction main.