dichotomie :( Fermé

Question

Bonjour, 
en accédant à wikipédia pour comprendre la dichotomie, j'ai trouvé l'algorythme dichotomie avec des noms de variables en chinois
qd j'ai lu l'exeple de pierre, j'ai compris le principe, mais qd j'ai lu l'aldo, je ne l'ai pas compris, vu que les nominations sont symboliques à décoder, pouvez vous svp me simplifier l'algo en nommant les variables avec leur nom complet, je veux dire nommer "rang de variable" au lieu de var ou mil :p
voilà l'exemple
//déclarations
 début, fin, val, mil : Entiers
 t : Tableau [0..100] d'entiers classé
 trouvé : Booléen
 
//initialisation
 début ? 0 
 fin ? 100
 trouvé ? faux
 Saisir val

//Boucle de recherche
  Répéter
   mil ? partie entière( début + ((fin-début) / 2) )
   Si t[mil] = val alors
     trouvé ? vrai
   Sinon
     Si val > t[mil] Alors
       début ? mil+1
       
     Sinon
       fin ? mil-1
       
     FinSi
    FinSi
   // La condition début inférieur ou égal à fin permet d'éviter de faire
   // une boucle infinie si 'val' n'existe pas dans le tableau.
   Tant que trouvé = faux ET début ? fin
//Affichage du résultat
Si trouvé Alors
     Afficher "La valeur ", val , " est au rang ", mil
  Sinon
     Afficher "La valeur ", val , " n'est pas dans le tableau"
FinSi

merci pour votre collaboration


Configuration: windows 7
firefox

meskasousoubiba · Answer

2ème partie de ma question notre tutor nous a donné un programme en C pour la dichotomie, que je n'est pas compris aussi à cause de la complexité des noms des variables et l'abscence d'expressions humaines pour les saisies entre guillemets, je parle des messages qui vont s'afficher lors de l'exécution, vous serez bien aimables si vous m'aider à simplifier les noms des variables et ajouter des phrases complètes qui s'affichent lors de l'exécution du programme voila son texte: #include #include int RechercheDichotomique(int *T, int N, int idx0, int idxN) { int i, j, n; i = idx0; j = idxN; n = (j + i)/2; printf("(i,j,n)=(%d,%d,%d) ",i,j,n); while(i <= j) { if(N <= T[n]) j = n - 1; else i = n + 1; n = (j + i)/2; printf("(i,j,n)=(%d,%d,%d) ",i,j,n); } }} merci

meskasousoubiba · Answer

bonjour et bonne année à, tous les ccriens :)
j'attends votre aide

meskasousoubiba · Answer

bonjour et bonne année à, tous les ccriens :)
j'attends votre aide

metarefsalem · Answer

L'algorithme de recherche appelé Dichotomie s'applique toujours à des vecteurs triés, le principe consiste à considerer une certaine plage de recherche [Inferieur..Superieur] sur le vecteur T, plage que l'on reduit à chaque itération. Au depart, la plage de recherche est tout le vecteur T, à une iteration donnée on a une plage [Inferieur..Superieur] et son milieu est ; Milieu = (inferieur + superieur) div 2. On a donc les portions : [Inferieur..Milieu - 1], [Milieu], [Milieu + 1..Superieur]. Valeur est une variable entière à rechercher Si T[Milieu] = Valeur, L'element recherché est trouvé. Si T[Milieu] < Valeur, Valeur n'appartient pas à l'intervalle [Inferieur..Milieu] Alors la plage de recherche sera [Milieu + 1..Superieur]. Si T[Milieu] > Valeur, Valeur n'appartient pas à l'intevalle [Milieu..Superieur] Alors la plage de recherche sera [Inferieur..Milieu - 1]. On implemente l'algorithme avec une variable Logique Trouve ou Found. Const N = 100 // Constante entiere variables T : Vecteur[0..N] d'entiers ordonnés I Valeur Inferieur Superieur Milieu Entiers Trouve Logique // Vrai/Faux Deut de Programme Pour I := 0 à N Faire // remplissage du Vecteur T Lire T[I] // Les valeurs sont supposées entrées dans l'ordre Fin Pour Ecrire "Entrez la Valeur à chercher" Lire Valeur Trouve := Faux Inferieur := 0; Superieur := N Milieu := (Inferieur + Superieur) div 2 Tant Que (Inferieur <= Superieur) ET NON Trouve FAIRE SI T[Milieu] = Valeur ALORS Trouve := Vrai Fin SI // Element trouvé, arret de la recherche SINON SI T[Milieu] < Valeur ALORS Inferieur = Milieu + 1 Milieu := (Inferieur + Superieur) div 2 Fin SINON SI SINON Superieur = Milieu - 1 // T[Milieu] > Valeur Milieu := (Inferieur + Superieur) div 2 Fin SINON Fin TANT QUE Si Trouve Alors // recherche positive Ecrire T[Milieu], " Position : ", Milieu) SINON Ecrire('Cet element n'existe pas') Fin Programme Testé sous console Delphi

Dichotomie :(

4 réponses

Discussions similaires