Tableau a trier + Dichotomie avec algobox

[Ouate]

Bonjour, je suis en formation développeur web/web mobile

Nous avons à rendre le sujet suivant : avec Algobox

12: Tableau trié + Dichotomie

En utilisant le travail déjà réalisé pour les deux derniers exercices, écrire un programme qui demande à l’utilisateur de rentrer un tableau de valeur. Ecrire en suite une fonction qui renvoie ce Tableau trié.Demander à l’utilisateur de rentrer une valeur pour X, puis utiliser la méthode dichotomique pour rechercher si cette valeur de X appartient au Tableau, auquel cas renvoyer la position (numéro du rang) de X dans ce tableau.

Juste avant cet exercice, nous avons réalisés le tableau trié et la dichotomie. Nous sommes en difficultés d'associés les deux.

Merci de m'avoir lu, au plaisir de lire vos réponses

[pascal16]

la dichotomie porte sur les indices du tableau, pas sur x directement.

s'il a 40 éléments :
on vérifie pour le premier et le dernier car x peut être en dehors des valeurs du tableau
ensuite on compare à l'élément numéro 20
si x est plus petit,on recoupe les indices jusqu'à 20 en 2 donc 10.
...

[Ouate]

Merci beaucoup Pascal16 pour votre réponse

Nous avons très peu étudié l'algorithme et nous avons à rendre un TP avec cet exercice. Je vous avoue que je suis larguée ... Doit on associés le tableau a bulle + la dichotomie ?

[pascal16]

en gros :

si tableau vide, quitter
Tableau T=trier tableau
entrer x
borne_min = 1er élément de T
borne_max = dernier élément de T
si x<T(borne_min) ou x > T(borne max), afficher "en dehors du tbeau"
sinon

indice A= 0 (ou 1 si ton tableau commence à 1)
indice B= indice max tu tableau.
tant que indice A=/=indice B
indice= partie entière( (indiceA+indiceB)/2)
si T(indice) < X indice A=indice sinon indice B=indice

afficher indice A+1

NB : on peut améliorer les conditions (indiceB-indice A <=1) mais ça devrait converger

[Ouate]

Merci Pascal16
Je vais essayer de reproduire sur algobox. Je vous tiens informé ce soir (c'est la moindre des choses)

Je vous souhaite une agréable journée

[Ouate]

FONCTIONS_UTILISEES
VARIABLES
Tab EST_DU_TYPE LISTE
min EST_DU_TYPE NOMBRE
max EST_DU_TYPE NOMBRE
Temp EST_DU_TYPE NOMBRE
i EST_DU_TYPE NOMBRE
j EST_DU_TYPE NOMBRE
precision EST_DU_TYPE NOMBRE
m EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
precision PREND_LA_VALEUR 0.0001
LIRE i
LIRE j
TANT_QUE (j-i>precision) FAIRE
DEBUT_TANT_QUE
m PREND_LA_VALEUR (i+j)/2
SI (F1(m)*F1(b)>0) ALORS
DEBUT_SI
j PREND_LA_VALEUR m
FIN_SI
SINON
DEBUT_SINON
i PREND_LA_VALEUR m
FIN_SINON
FIN_TANT_QUE
min PREND_LA_VALEUR 1
LIRE max
POUR i ALLANT_DE min A max
DEBUT_POUR
LIRE Tab[i]
FIN_POUR
POUR j ALLANT_DE min A max
DEBUT_POUR
POUR i ALLANT_DE j+1 A max
DEBUT_POUR
SI (Tab[i]<Tab[j]) ALORS
DEBUT_SI
Temp PREND_LA_VALEUR Tab[i]
Tab[i] PREND_LA_VALEUR Tab[j]
Tab[j] PREND_LA_VALEUR Temp
FIN_SI
FIN_POUR
FIN_POUR
POUR i ALLANT_DE min A max
DEBUT_POUR
AFFICHER Tab[i]
AFFICHER " "
FIN_POUR
FIN_ALGORITHME

Voici mon code sous algobox
En vous souhaitant une agréable soirée

[fatal_error]

Le code est pas trop lisible sans indentation (utilises les balises [ code][/code] prevues a cet effet. Mise a part je vois deux boucles for imbriquees donc je pense que tu n'as pas appliqué la dichotomie.

Par aileurs tu dais un produit f(a)f(b) que tu compares a zero, comme si tu cherchais un zero, sauf que là tu cherches pas zero

[pascal16]

là, c'est la partie tri que tu présentes

[Ouate]

Je vous remercie de vos réponses, vous êtes adorable de vos explications.
J'ai très peu de base en algo ce qui est compliqué à rendre un tp correct
Oui j'aurais pu indenter pour faciliter la lecture, je m'en excuse de vous mettre en tas ce code.
Je vais envoyer ce code sachant qu'il n'est pas correct et avoir plus d'explications la semaine prochaine.

Je vous souhaite une agréable journée

[fatal_error]

considère deux fonctions:

• bubbleSort(arr) qui tri le tableau en entrée in-place (modifie le tableau même)
• dichot(arr, v)->idx qui prend un tableau en paramètre, et retourne l'index du tableau où la valeur v a été trouvé (-1 si non trouvé)

Le programme se décompose ainsi:

Code: Tout sélectionner

arr = demander valeurs à l'utilisateur
bubbleSort(arr)
//arr est maintenant trié
v = demander une valeur à trouver
idx = dichot(arr, v)
afficher(idx)


Voici un exemple en javascript
https://jsfiddle.net/6jcv70pf/

Code: Tout sélectionner


//copié collé https://www.geeksforgeeks.org/bubble-sort/
function bubbleSort(arr) {
  const n = arr.length
  for (let i = 0; i < n - 1; ++i) {
    for (let j = 0; j < n - i - 1; ++j) {
      if (arr[j] > arr[j + 1]) {
        const t = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = t
      }
    }
  }
}

//copié collé aussi! https://en.wikipedia.org/wiki/Binary_search_algorithm (function binary_search(A, n, T):)
function dichot (A, T) {
  let L = 0
  let R = A.length - 1
  while (L <= R) {
    const m = Math.floor((L + R) / 2)
    if (A[m] < T) {
      L = m + 1
    } else if (A[m] > T) {
      R = m - 1
    } else {
      return m
    }
  }
  return -1
}
//on teste quelques cas
var arr = [1,2,3,5,6,1,4]
bubbleSort(arr)
console.log('arr: ', arr.join(' '))
console.log('7? doit retourner -1 -> ', dichot(arr, 7))

// on retourne bien l'index de la valeur
var arr = [1,2,5,6,1,4]
bubbleSort(arr)
console.log('arr: ', arr.join(' '))
console.log('5? doit retourner 4 -> ', dichot(arr, 5))

// on trouve en cas de début de tableau
var arr = [1,2,3,5,6,1,4]
bubbleSort(arr)
console.log('arr: ', arr.join(' '))
console.log('1? doit retourner 0 ou 1 -> ', dichot(arr, 1))

// on trouve en cas de fin de tableau
var arr = [1,2,3,5,7,1,4]
bubbleSort(arr)
console.log('arr: ', arr.join(' '))
console.log('7? doit retourner 6 -> ', dichot(arr, 7))


[pascal16]

pour ceux qui aiment les algos de tri :

https://www.youtube.com/watch?v=kPRA0W1kECg&t=129s

[Ouate]

Je vous remercie de vos réponses, je vais étudier de plus près.
J'étudie les algo sur algobox après nous allons faire du javascript je referais certainement rappel sur ce forum.

Merci pour l'entraide.