Algo recherche dichotomique
Fermé
miya26
-
5 déc. 2007 à 23:57
kamelbouzgou Messages postés 33 Date d'inscription vendredi 8 mai 2009 Statut Membre Dernière intervention 21 mai 2009 - 9 mai 2009 à 23:09
kamelbouzgou Messages postés 33 Date d'inscription vendredi 8 mai 2009 Statut Membre Dernière intervention 21 mai 2009 - 9 mai 2009 à 23:09
A voir également:
- Algo recherche dichotomique
- Recherche musique - Guide
- Google recherche par image - Guide
- Recherche automatique des chaînes ne fonctionne pas - Guide
- Recherche adresse - Guide
- Rechercher ou entrer l'adresse 4 - recherche google ✓ - Forum Windows
4 réponses
kamelbouzgou
Messages postés
33
Date d'inscription
vendredi 8 mai 2009
Statut
Membre
Dernière intervention
21 mai 2009
7
9 mai 2009 à 23:09
9 mai 2009 à 23:09
bonjour
algo recherche
t[i] tableau de 0.. n entier
a,b:entier
debut
a:=t[0]
b:=t[n]
m:=(a+b)/2
repeter
si x>m alors
a:=m
sinon b:=m
jusqu'a x=m
afficher ('le nombre rechercher x=',m)
algo recherche
t[i] tableau de 0.. n entier
a,b:entier
debut
a:=t[0]
b:=t[n]
m:=(a+b)/2
repeter
si x>m alors
a:=m
sinon b:=m
jusqu'a x=m
afficher ('le nombre rechercher x=',m)
slt jespere ke Pierre propose à Paul le jeu suivant: « choisis en secret un nombre compris entre 0 et 100; je vais essayer de le deviner le plus rapidement possible, mais tu ne dois répondre à mes questions que par oui ou par non ». Paul choisit 65 et attend les questions de Pierre:
est-ce que le nombre est plus grand que 50? (100 divisé par 2)
oui
est-ce que le nombre est plus grand que 75? ((50 + 100) / 2)
non
est-ce que le nombre est plus grand que 63? ((50 + 75 + 1) / 2)
oui
Pierre réitère ses questions jusqu'à trouver 65. Par cette méthode itérative, Pierre est sûr de trouver beaucoup plus rapidement le nombre qu'en posant des questions du type « est-ce que le nombre est égal à 30? ».
Algorithme [modifier]
//déclarations
début, fin, val, mil : Entier
t : Tableau [0..100] d'entier
trouvé : Booléen
//initialisation
début <- 0
fin <- 100
trouvé <- faux
//Question
Répéter
Afficher "Valeur recherchée ? (entre 0 et 100)"
Saisir val
Jusqu'à début<=val et val<=fin
//Boucle de recherche
Répéter
mil <- début + ((fin-début) / 2)
Si t[mil] = val alors
trouvé <- vrai
Sinon
Si val > t[mil] Alors
début <- mil + 1
Si t[début] = val Alors
mil <- début
trouvé <- Vrai
FinSi
Sinon
fin <- mil – 1
Si t[fin] = val Alors
mil <- fin
trouvé <- vrai
FinSi
FinSi
FinSi
Jusqu’à trouvé ou ( début >= fin )
//Affichage du résultat
Afficher "La valeur est ", val
ceci taidera.
est-ce que le nombre est plus grand que 50? (100 divisé par 2)
oui
est-ce que le nombre est plus grand que 75? ((50 + 100) / 2)
non
est-ce que le nombre est plus grand que 63? ((50 + 75 + 1) / 2)
oui
Pierre réitère ses questions jusqu'à trouver 65. Par cette méthode itérative, Pierre est sûr de trouver beaucoup plus rapidement le nombre qu'en posant des questions du type « est-ce que le nombre est égal à 30? ».
Algorithme [modifier]
//déclarations
début, fin, val, mil : Entier
t : Tableau [0..100] d'entier
trouvé : Booléen
//initialisation
début <- 0
fin <- 100
trouvé <- faux
//Question
Répéter
Afficher "Valeur recherchée ? (entre 0 et 100)"
Saisir val
Jusqu'à début<=val et val<=fin
//Boucle de recherche
Répéter
mil <- début + ((fin-début) / 2)
Si t[mil] = val alors
trouvé <- vrai
Sinon
Si val > t[mil] Alors
début <- mil + 1
Si t[début] = val Alors
mil <- début
trouvé <- Vrai
FinSi
Sinon
fin <- mil – 1
Si t[fin] = val Alors
mil <- fin
trouvé <- vrai
FinSi
FinSi
FinSi
Jusqu’à trouvé ou ( début >= fin )
//Affichage du résultat
Afficher "La valeur est ", val
ceci taidera.
_Agnes
Messages postés
2224
Date d'inscription
samedi 10 juin 2006
Statut
Modérateur
Dernière intervention
2 décembre 2022
55
5 déc. 2007 à 23:59
5 déc. 2007 à 23:59
Bonsoir
Avec un "s'il vous plaît, merci" c'eût été mieux !
++
Avec un "s'il vous plaît, merci" c'eût été mieux !
++
# //Librairies
# #include...
#
# //Variables globales
# typedef struct
# { char nom_ville[32];
# char nom[32];
# char tel[11];
# }Tindex;
#
# Tindex idx[Max];
# int j;
#
# /* Trie Bubble Sort - Création d'un Index trié
# en fonction des numéros de téléphones */
#
# void tri_tel_index()
# {int k;
# Tindex temp[Max];
# for(k=Max-1;k!=0;k--)
# { for(j=0;j<k;j++)
# { if((strcmp(idx[j].tel,idx[j+1].tel))>0)
# { temp[0]=idx[j];
# idx[j]=idx[j+1];
# idx[j+1]=temp[0];
# }
# }
# }
# j=0;
# }
#
# //Prog. principal
# void main() {
# ...
# }
#
# Algo Général de la Recherche Dichotomique
#
# Procedure recherche_dichotomique(par val ent elt, par val ent N, par val ent T[])
# Debut
# |
# | var inf, sup, m;
# | inf <- 1;
# | sup <- N;
# | m <- (inf+sup) div 2;
# | /* en C++ m = (int)((inf+sup)/2) */
# |
# | /* Ici l'astuce : la borne supérieure ou inférieure est modifiée,
# | le tableau n'est plus parcouru dans son ensemble */
# |
# |
# | Tant que (T[m] != elt et inf < sup) faire
# | |
# | | Si (elt < T[m]) alors
# | | |
# | | | sup <- m - 1;
# | | |
# | | | Sinon inf <- m + 1;
# | | |
# | | Fin Si
# | |
# | | m <- (inf + sup) div 2;
# | |
# | Fin Tque
# |
# | Si (T[m] = elt)
# | |
# | | Afficher("L'element se trouve à l'indice m")
# | |
# | | Sinon Afficher ("L' élément n'existe pas ")
# | |
# | Fin Si
# |
# Fin
# #include...
#
# //Variables globales
# typedef struct
# { char nom_ville[32];
# char nom[32];
# char tel[11];
# }Tindex;
#
# Tindex idx[Max];
# int j;
#
# /* Trie Bubble Sort - Création d'un Index trié
# en fonction des numéros de téléphones */
#
# void tri_tel_index()
# {int k;
# Tindex temp[Max];
# for(k=Max-1;k!=0;k--)
# { for(j=0;j<k;j++)
# { if((strcmp(idx[j].tel,idx[j+1].tel))>0)
# { temp[0]=idx[j];
# idx[j]=idx[j+1];
# idx[j+1]=temp[0];
# }
# }
# }
# j=0;
# }
#
# //Prog. principal
# void main() {
# ...
# }
#
# Algo Général de la Recherche Dichotomique
#
# Procedure recherche_dichotomique(par val ent elt, par val ent N, par val ent T[])
# Debut
# |
# | var inf, sup, m;
# | inf <- 1;
# | sup <- N;
# | m <- (inf+sup) div 2;
# | /* en C++ m = (int)((inf+sup)/2) */
# |
# | /* Ici l'astuce : la borne supérieure ou inférieure est modifiée,
# | le tableau n'est plus parcouru dans son ensemble */
# |
# |
# | Tant que (T[m] != elt et inf < sup) faire
# | |
# | | Si (elt < T[m]) alors
# | | |
# | | | sup <- m - 1;
# | | |
# | | | Sinon inf <- m + 1;
# | | |
# | | Fin Si
# | |
# | | m <- (inf + sup) div 2;
# | |
# | Fin Tque
# |
# | Si (T[m] = elt)
# | |
# | | Afficher("L'element se trouve à l'indice m")
# | |
# | | Sinon Afficher ("L' élément n'existe pas ")
# | |
# | Fin Si
# |
# Fin
