Différences entre versions de « Js algo td4 »

De The Linux Craftsman
Aller à la navigation Aller à la recherche
 
(12 versions intermédiaires par le même utilisateur non affichées)
Ligne 13 : Ligne 13 :
 
L'algorithme est la stricte application de ce principe.
 
L'algorithme est la stricte application de ce principe.
  
= Application =
+
= Pseudo-code =
 
Soit T un tableau de noms:
 
Soit T un tableau de noms:
 
<source lang="javascript">
 
<source lang="javascript">
var T = new Array("Alain","Antoine", "Bernard", "Colin", "Christine","François", "Guy","Gérard", "Léa","Léon","Louis","Nathalie","Serge","Sylvie","Sylvain","Vincent");
+
var T = new Array("Alain", "Antoine", "Bernard", "Christine", "Colin", "François", "Gérard", "Guy", "Léa", "Léon", "Louis", "Nathalie", "Serge", "Sylvain", "Sylvie", "Vincent");
 
</source>
 
</source>
 
== Exercice 1 ==
 
== Exercice 1 ==
Ligne 23 : Ligne 23 :
 
* ''0'' si ''a'' == ''b'';
 
* ''0'' si ''a'' == ''b'';
 
* une valeur positive si ''a'' > ''b'';
 
* une valeur positive si ''a'' > ''b'';
<div class="toccolours mw-collapsible mw-collapsed" style="width:700px;visibility:hidden">
+
<div class="toccolours mw-collapsible mw-collapsed" style="width:700px">
 +
<big>Solution</big>
 +
<source lang="text" style="border:1px solid black;font-size:130%" class="mw-collapsible-content">
 +
FONCTION compare_char(a, b)
 +
  SI a < b
 +
      RETOURNE -1;
 +
  SINON SI a > b {
 +
      RETOURNE 1;
 +
  FIN SI
 +
  RETOURNE 0;
 +
FIN FONCTION
 +
</source>
 +
</div>
 +
 
 +
== 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é !
 +
 
 +
<div class="toccolours mw-collapsible mw-collapsed" style="width:700px">
 +
<big>Solution</big>
 +
<source lang="text" style="border:1px solid black;font-size:130%" class="mw-collapsible-content">
 +
FONCTION compare_string(a, b)
 +
  VAR
 +
      i : entier
 +
      compare : entier
 +
 
 +
  i <- 0;
 +
 
 +
  TANT QUE i < len(a) ET i < len(b) FAIRE
 +
      compare <- compare_char(a[i], b[i]);
 +
      SI compare != 0
 +
        RETOURNE  compare;
 +
      FIN SI
 +
      i++;
 +
  FIN TANT QUE
 +
  RETOURNE 0;
 +
FIN FONCTION
 +
</source>
 +
</div>
 +
 
 +
== 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, l'index de la valeur recherchée.
 +
 
 +
<div class="toccolours mw-collapsible mw-collapsed" style="width:700px">
 +
<big>Solution</big>
 +
<source lang="text" style="border:1px solid black;font-size:130%" class="mw-collapsible-content">
 +
FONCTION get_half(T, x) {
 +
  VAR
 +
      half : entier
 +
      compare : entier
 +
      j : entier
 +
      i : entier
 +
      tab_start : entier
 +
      tab_end : entier
 +
      resultat : tableau
 +
 
 +
  half <- arrondi(len(t) / 2);
 +
  compare <- compare_string(T[half],x)
 +
  j <- 0
 +
  SI compare = 0 ALORS
 +
      RETOURNE half
 +
  SINON
 +
      SI compare < 0 ALORS
 +
        tab_start <- 0
 +
        tab_end <- half
 +
      SINON
 +
        tab_start <- half
 +
        tab_end <- len(T)
 +
      FIN SI
 +
      POUR i = tab_start JUSQU'A i < tab_end {PAR PAS DE 1}
 +
        resultat[i] = T[i]
 +
      FIN POUR
 +
      RETOURNE resultat
 +
  FIN SI
 +
FIN FONCTION
 +
</source>
 +
</div>
 +
 
 +
== 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''.
 +
<div class="toccolours mw-collapsible mw-collapsed" style="width:700px">
 
<big>Solution</big>
 
<big>Solution</big>
 
<source lang="javascript" style="border:1px solid black;font-size:130%" class="mw-collapsible-content">
 
<source lang="javascript" style="border:1px solid black;font-size:130%" class="mw-collapsible-content">
Ligne 38 : Ligne 128 :
  
 
== Exercice 2 ==
 
== Exercice 2 ==
Écrire la fonction ''compare_string'' qui prend en paramètres deux chaînes de caractères ''x'' et ''y'' et qui renvoie:
+
Écrire la fonction ''compare_string''.
* 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:
 
Pour cela, vous pouvez vous aider de la fonction ''String.charAt(num)'' dont voici la documentation:
Ligne 54 : Ligne 139 :
 
If the num passed is not a valid index in the string, -1 is returned.
 
If the num passed is not a valid index in the string, -1 is returned.
 
</pre>
 
</pre>
<div class="toccolours mw-collapsible mw-collapsed" style="width:700px;visibility:hidden">
+
 
 +
<div class="toccolours mw-collapsible mw-collapsed" style="width:700px">
 
<big>Solution</big>
 
<big>Solution</big>
 
<source lang="javascript" style="border:1px solid black;font-size:130%" class="mw-collapsible-content">
 
<source lang="javascript" style="border:1px solid black;font-size:130%" class="mw-collapsible-content">
Ligne 74 : Ligne 160 :
  
 
== Exercice 3 ==
 
== 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.
+
Écrire la fonction ''get_value''.
 
+
<div class="toccolours mw-collapsible mw-collapsed" style="width:700px">
<div class="toccolours mw-collapsible mw-collapsed" style="width:700px;visibility:hidden">
 
 
<big>Solution</big>
 
<big>Solution</big>
 
<source lang="javascript" style="border:1px solid black;font-size:130%" class="mw-collapsible-content">
 
<source lang="javascript" style="border:1px solid black;font-size:130%" class="mw-collapsible-content">
 
function get_half(T, x) {
 
function get_half(T, x) {
 
var half = Math.round(T.length / 2);
 
var half = Math.round(T.length / 2);
console.log(half);
 
 
var half_value = T[half];
 
var half_value = T[half];
 
var compare = compare_string(x, half_value);
 
var compare = compare_string(x, half_value);
 
var tab_start;
 
var tab_start;
 
var tab_end;
 
var tab_end;
var j = 0;
 
 
if (compare == 0) {
 
if (compare == 0) {
console.log("TROUVE : "+half);
 
 
return half;
 
return half;
 
} else {
 
} else {
 
if (compare < 0) {
 
if (compare < 0) {
console.log("MOITIE INFERIEUR");
 
 
tab_start = 0;
 
tab_start = 0;
 
tab_end = half;
 
tab_end = half;
 
} else {
 
} else {
console.log("MOITIE SUPERIEUR");
 
 
tab_start = half;
 
tab_start = half;
 
tab_end = T.lenght;
 
tab_end = T.lenght;
Ligne 102 : Ligne 182 :
 
var resultat = new Array();
 
var resultat = new Array();
 
for (var i = tab_start; i < tab_end; i++) {
 
for (var i = tab_start; i < tab_end; i++) {
resultat[j] = T[i];
+
resultat[i] = T[i];
j++;
 
 
}
 
}
 
return resultat;
 
return resultat;
Ligne 112 : Ligne 191 :
  
 
== Exercice 4 ==
 
== 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:
+
Écrire la fonction main.
* l'index de la chaîne ''name'';
 
* la phrase suivante ''La chaîne n'existe pas''.
 
 
 
  
 
Pour tester le type d'une variable, vous pouvez utiliser le mot clé ''instanceof''.  
 
Pour tester le type d'une variable, vous pouvez utiliser le mot clé ''instanceof''.  

Version actuelle datée du 20 mai 2014 à 21:16

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

FONCTION compare_char(a, b)
   SI a < b 
      RETOURNE -1;
   SINON SI a > b {
      RETOURNE 1;
   FIN SI
   RETOURNE 0;
FIN FONCTION

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é !

Solution

FONCTION compare_string(a, b)
   VAR
      i : entier
      compare : entier

   i <- 0;

   TANT QUE i < len(a) ET i < len(b) FAIRE
      compare <- compare_char(a[i], b[i]);
      SI compare != 0
         RETOURNE  compare;
      FIN SI
      i++;
   FIN TANT QUE
   RETOURNE 0;
FIN FONCTION

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, l'index de la valeur recherchée.

Solution

FONCTION get_half(T, x) {
   VAR
      half : entier
      compare : entier
      j : entier
      i : entier
      tab_start : entier
      tab_end : entier
      resultat : tableau 

   half <- arrondi(len(t) / 2);
   compare <- compare_string(T[half],x)
   j <- 0
   SI compare = 0 ALORS
      RETOURNE half
   SINON
      SI compare < 0 ALORS
         tab_start <- 0
         tab_end <- half
      SINON
         tab_start <- half
         tab_end <- len(T)
      FIN SI
      POUR i = tab_start JUSQU'A i < tab_end {PAR PAS DE 1}
         resultat[i] = T[i]
      FIN POUR
      RETOURNE resultat
   FIN SI
FIN FONCTION

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.

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.

Solution

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

Exercice 4

Écrire la fonction main.

Pour tester le type d'une variable, vous pouvez utiliser le mot clé instanceof.

Par exemple:

var T = new Array();

if(T instanceof Array){
   console.log("Je suis un tableau");
}

Affichera Je suis un tableau.