Discussion :

[Joe_Dupont]

Bonjour,

J'essaie de programmer un algorithme de recherche dichotomique dans une liste d'entiers :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
maliste = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
 
def rech_dichot(liste, borne_inf, borne_sup, x):
 
	borne_interm = (borne_sup + borne_inf)/2;
 
 
	if liste[borne_sup] < x or liste[borne_inf] > x: #si l'entier recherche n'est pas dans la liste
		return False;
	if liste[borne_interm] == x:
		return True;
	else:
 
		if maliste[borne_interm] > x:
			rech_dichot(liste, borne_inf, borne_interm-1, x);
		else:
			if maliste[borne_interm] < x:
				rech_dichot(liste, borne_interm + 1, borne_sup, x);
			else:
				return False;
 
 
nbre_rech = input("Veuillez rentrer l'entier recherche : ");
 
print rech_dichot(maliste, 0, len(maliste)-1, int(nbre_rech));

J'ai utilisé une fonction recursive, je pense avoir optimisé pas mal le code, mais si vous voyez une amélioration possible n'hésitez pas à me le signaler.

Le problème c'est que si je rentre l'entier 2 par ex dans la console, la fonction me renvoie "none" alors que si je rentre l'entier 10 elle me renvoie "True". J'ai bien cherché mais je ne voit pas d'où ça peut venir. Pourriez-vous me mettre sur la voie svp ?

Merci

[VinsS]

Salut,

On suppose que tu ne peux pas faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
print x in maliste

Le problème de ton code c'est que :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
	if liste[borne_interm] == x:
		return True

1.- borne_interm n'est pas un entier dans un très grand nombre de cas ;

2.- le return ne renvoie pas à l'appel initial de la fonction mais à l'appel récursif qui se poursuit jusqu'à épuisement des nombres de la liste.

Dans ta liste, seul le nombre 10 est trouvé tout de suite (borne_intrem == 10) et dans ce cas le return renvoie à l'appel initial.

Tu peux aussi simplifier ta manipulation de liste.

exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
maliste = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
 
def rech_dichot(l, x):
    is_present = False
    if x < l[0] or x > l[-1]:
        return False
 
    while 1:
        mid = int(l[0] + ((l[-1] - l[0]) / 2))
        if x == mid:
            is_present = True
            break
        elif x > mid:
            l = [n for n in l if n >= mid]
        else:
            l = [n for n in l if n <= mid]
        if len(l) < 3:
            is_present =  x in l
            break
        else:
            rech_dichot(l, x)
 
    return is_present
 
 
for i in maliste:
    print "%s in maliste  : %s" % (i, rech_dichot(maliste, i))

Devrait être encore simplifié mais il est tard.

[tyrtamos]

Bonjour,

Il est intéressant d'examiner le code du module bisect.py livré avec Python.

Voir aussi mon tuto comme source d'inspiration: j'ai fait une fonction de recherche par dichotomie qui utilise les mêmes fonctions comp et key que la méthode sort() et la fonction sorted():

http://python.jpvweb.com/mesrecettes...?id=dichotomie

Tyrtamos

[Joe_Dupont]

Je vous remercie beaucoup je vais étudier ça ce soir, je vous tien au courant

[rambc]

Bonjour.

Un petit conseil rapide à Joe_Dupont.

Au lieu du code suivant...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
	if liste[borne_sup] < x or liste[borne_inf] > x: #si l'entier recherche n'est pas dans la liste
		return False;
	if liste[borne_interm] == x:
		return True;
	else:
		...

..., tu devrais utiliser :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
	if liste[borne_inf] <= x <= liste[borne_sup]:
		Tu tries...
	else:
		return False

Personnellement, j'utiliserais même :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
	if liste[borne_inf] <= x <= liste[borne_sup]:
		Tu tries et renvoie True si cela marche et rien sinon.
 
	return False

Autre remarque : les points-virgules en fin de ligne ne servent à rien !