Dichotomie :(
meskasousoubiba
Messages postés
1207
Date d'inscription
Statut
Membre
Dernière intervention
-
Profil bloqué -
Profil bloqué -
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
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
4 réponses
-
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<stdio.h>
#include<stdlib.h>
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)\n",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)\n",i,j,n);
}
}}
merci -
bonjour et bonne année à, tous les ccriens :)
j'attends votre aide -
bonjour et bonne année à, tous les ccriens :)
j'attends votre aide -
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
