Dichotomie :(
Fermé
meskasousoubiba
Messages postés
1208
Date d'inscription
vendredi 15 avril 2011
Statut
Membre
Dernière intervention
23 avril 2014
-
2 janv. 2012 à 06:29
Profil bloqué - 4 janv. 2012 à 00:09
Profil bloqué - 4 janv. 2012 à 00:09
A voir également:
- Dichotomie :(
- Dichotomie programme python - Forum Python
- Méthode de la dichotomie en C - Forum C
4 réponses
meskasousoubiba
Messages postés
1208
Date d'inscription
vendredi 15 avril 2011
Statut
Membre
Dernière intervention
23 avril 2014
28
2 janv. 2012 à 06:35
2 janv. 2012 à 06:35
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
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
meskasousoubiba
Messages postés
1208
Date d'inscription
vendredi 15 avril 2011
Statut
Membre
Dernière intervention
23 avril 2014
28
2 janv. 2012 à 11:29
2 janv. 2012 à 11:29
bonjour et bonne année à, tous les ccriens :)
j'attends votre aide
j'attends votre aide
meskasousoubiba
Messages postés
1208
Date d'inscription
vendredi 15 avril 2011
Statut
Membre
Dernière intervention
23 avril 2014
28
3 janv. 2012 à 15:05
3 janv. 2012 à 15:05
bonjour et bonne année à, tous les ccriens :)
j'attends votre aide
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
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
