Problème algorithme dichotomique

Résolu/Fermé

a.b - Modifié le 25 janv. 2021 à 19:55
jordane45 Messages postés 38145 Date d'inscription mercredi 22 octobre 2003 Statut Modérateur Dernière intervention 25 avril 2024 - 25 janv. 2021 à 20:40

Bonjour,

J'essaye d'implémenter ce code mais je n'arrive pas à comprendre pourquoi. L'aide serait le bienvenue.


let tab = [4,3,2,5,2,4];
function findM(tab) {
    return Math.floor(tab.length / 2)
}

let m = 0;
let milieu = findM(tab)

function search(tab,x,m) {
    if(x < tab[m]) {
        leftTab = tab.slice(0,m)
        ml = findM(leftTab)
        search(leftTab,x,ml)
    } else {
        rightTab = tab.slice(m,tab.length)
        mr = findM(rightTab)
        search(rightTab,x,mr)
    }
}

console.log(search(tab,2,milieu))

Voilà à l'exécution :


alfa@MacBook-Pro-de-Alpha algo_niv2 % node ./exoalgo1.js
/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:114
        rightTab = tab.slice(m-1,tab.length-1)
                       ^

RangeError: Maximum call stack size exceeded
    at Array.slice (<anonymous>)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:114:24)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
alfa@MacBook-Pro-de-Alpha algo_niv2 %

Je vous remercie d'avance.

Configuration: Macintosh / Chrome 84.0.4147.105

A voir également:

Problème algorithme dichotomique
Logiciel algorithme gratuit - Télécharger - Édition & Programmation
Code ascii algorithme - Guide
Ecrire un algorithme qui calcule le produit de deux nombres - Forum Programmation
Remplir une matrice algorithme - Forum Pascal
Ecrire un algorithme qui permet de resoudre ax²+bx+c=0 - Forum Programmation

1 réponse

Réponse 1 / 1

jordane45 Messages postés 38145 Date d'inscription mercredi 22 octobre 2003 Statut Modérateur Dernière intervention 25 avril 2024 4 650
25 janv. 2021 à 20:40

Bonjour,

Pour faire une recherche par dichotomie.. il faudrait déjà que ton tableau soit trié et ne contienne pas de valeurs en doublons.
En plus, dans ton code actuel, tu ne sorts jamais... même si tu trouves le bon résultat...
Donc, ben.. tu fais une boucle infinie

Essaye ça

    let tab = [1,2,3,4,5,6,7,8];
    function findM(tbl) {
      return Math.floor(tbl.length / 2)
    }

    var m = 0;
    var milieu = findM(tab);

    function search(tbl,x,m) {
    console.log(tbl,x,m);
      let tm = typeof(tbl[m])!='undefined' ? tbl[m] : null;
      if(!tm) return false;
      if(tm == x){
        console.log("Valeur trouvée à l'indice ",m);
        return true;
      }else if(x < tm) {
          let leftTab = tbl.slice(0,m);
          let ml = findM(leftTab);
          search(leftTab,x,ml);
      } else {
          let rightTab = tbl.slice(m,tbl.length);
          let mr = findM(rightTab);
          search(rightTab,x,mr);
      }
    }
    
    console.log(search(tab,2,milieu));

Discussions similaires

algorithme résoudre ax²+bx+c=0

Générer toutes combinaisons possibles Euromillions dans Excel

solution de la recherche dichotomique en C

Exercice simple d'algorithmique

Apprentissage de Algorithme et programmation sur excel

Discussions similaires

Newsletters