On dispose d'une liste de nombres, triée dans l'ordre croissant.
L'objectif est de rechercher si un nombre x est présent dans cette liste (et de retourner un indice correspondant).
Donnez une fonction récursive d'une telle recherche.
Le nombre d'appels à votre fonction est-il, dans le cas le plus défavorable, une fonction affine de la taille
de la liste ?
Si oui, cherchez encore !
On utilise un indicateur entier qui marquera une position dans la liste, en commençant par la position 0.
Cas de base : lorsque l'indicateur dépasse l'indice maximal dans la liste, l'élément est absent. Lorsque l'élément d'indice indicateur est l'élément cherché, on peut répondre immédiatement également (élément trouvé à l'indice 'valeur de indicateur').
Dans les autres cas (L[indicateur] est distinct de l'élément cherché) : on lance une recherche dans la liste en incrémentant d'une unité la valeur de l'indicateur.
Comme l'indicateur augmente d'une unité à chaque étape :
Dans tous les cas, l' algorithme terminera.
Dans le cas le plus défavorable (l'élément cherché est en fin de liste), on aura n appels de la fonction. Nous chercherons donc ci-après, conformément à la demande de l'énoncé, une solution plus rapide.
def recherche(liste, element, indice=0) :
""" recherche l'élément element dans liste.
Retourne -1 si non trouvé, retourne un indice
d'une occurrence de element dans liste si trouvé."""
if indice>=len(liste) : return -1
if liste[indice]==element :
return indice
else :
return recherche(liste, element, indice+1)
L=[2,4,9,15,41]
print( recherche(L,43) )
Le défaut majeur de la procédure précédente est qu'elle n'exploite pas le fait que la liste de départ soit déjà triée.
On met ici en oeuvre le principe de dichotomie (binary search).
On dispose de deux indices mini et maxi et à tout moment on cherche entre ces deux indices. On testera plus précisément L[ (mini+maxi)//2].
def recherche(liste, element) :
def search(mini, maxi) :
if mini>maxi : return -1
m=(mini+maxi)//2
if liste[m]==element : return m
elif liste[m]<element : return search(m+1,maxi)
else : return search(mini,m-1)
return search(0, len(liste)-1)
L=[2,4,9,15,41]
print( recherche(L,16) )
Une anagramme d'un mot est un mot s'écrivant avec les mêmes lettres que le mot initial.
Exemples :
Ici, nous ne demandons pas que les mots envisagés soient des mots du dictionnaire.
Ainsi 'abc' et 'bca' sont deux anagrammes.
Écrire une fonction récursive :
Si le mot n'a qu'une seule lettre, la liste de ses anagrammes ne contient qu'un seul élément : le mot lui-même.
Regardons le cas d'un mot de trois lettres 'abc'. On peut définir la liste de ses anagrammes en fonction de
la liste des anagrammes du mot 'bc'.
La liste des anagrammes de 'bc' est ['bc', 'cb'].
Pour constituer la liste des anagrammes de 'abc', il suffit de placer la lettre 'a' dans toutes les positions possibles des anagrammes
de 'bc'. On obtient la liste ['abc', 'bac', 'bca', 'acb', 'cab', 'cba'].
De la même façon, on obtiendra la liste de toutes les anagrammes du mot 'dabc' en glissant la lettre 'd' dans toutes les positions possibles de toutes les anagrammes de 'abc'.
On tient donc là une définition de la liste des anagrammes d'un mot de longueur n en fonction de la liste des anagrammes d'un mot de longueur n-1. Comme nous savons traiter de façon directe le cas d'un mot de longueur 1, nous tenons notre définition récursive.
def listeAnagramme(mot) :
# cas de base :
if len(mot)==1 : return [mot]
# les autres cas :
liste=[]
for anagr in listeAnagramme(mot[1:]) :
for k in range(len(mot)) :
liste.append(anagr[:k]+mot[0]+anagr[k:])
return liste
print(listeAnagramme('abc'))
Cette notion d'anagramme n'est pas anecdotique. Il s'agit, dans un cadre plus général, de la notion de permutation.
Le problème des tours de Hanoï est un problème très connu. Vous trouverez de nombreuses références sur le web à ce sujet. Par exemple : sur wikipedia.
Dans le jeu des tours de Hanoï, on dispose de trois piquets : le piquet de départ, le piquet objectif et un piquet intermédiaire.
Au départ, n disques de rayons différents sont empilés sur le piquet de départ. Le disque de plus grand rayon est le disque le plus bas, le disque de plus petit rayon est le disque le plus haut.
Tout disque est posé sur un disque de plus grand rayon que lui. Et ceci devra être conservé lors des déplacements de disque : interdiction absolue de poser à un moment donné un disque sur un disque de rayon plus petit.
L'objectif est de déplacer les disques du piquet de départ vers le piquet objectif. On ne peut déplacer qu'un seul disque à la fois, la règle énoncée ci-dessus sur les rayons est à respecter et on peut bien entendu utiliser le piquet intermédiaire.
Donner une programmation récursive. Les affichages seront constitués de messages indiquant les déplacements à faire.
Le nombre n de disques sera un paramètre de la fonction. Les disques seront numérotés de 1 à n, le numéro d'un disque pourra être considéré comme son rayon.
Combien de déplacements de disques utilisez-vous dans votre procédure ? Est-il possible de faire mieux (c'est à dire de déplacer la tour de disques d'un anneau à l'autre en utilisant moins de déplacements de disques) ?
En utilisant le module timeit, évaluer le temps nécessaire aux déplacements des disques sur votre machine dans le cas d'une quinzaine de disques. En déduire une estimation du temps de déplacement des disques dans le cas d'une tour de 64 disques.
Il est clair que l'on sait résoudre le problème s'il n'y a qu'un seul anneau.
Si l'on sait déplacer n-1 anneaux d'un piquet à un autre, alors on sait déplacer n anneaux :
Traduction en langage python :
def hanoi(n,a='départ',b='intermédiaire',c='objectif',z=1):
""" a piquet de départ.
b piquet intermédiaire.
c piquet d'arrivée.
n nombre d'anneaux à déplacer.
z anneau déplacé."""
if n==1:
print("Déplacer l'anneau {} du piquet {} vers le piquet {}.".format(z,a,c))
else:
hanoi(n-1,a,c,b)
hanoi( 1,a,b,c, n)
hanoi(n-1,b,a,c)
n=3
hanoi(n)
On obtient :
Déplacer l'anneau 1 du piquet départ vers le piquet objectif. Déplacer l'anneau 2 du piquet départ vers le piquet intermédiaire. Déplacer l'anneau 1 du piquet objectif vers le piquet intermédiaire. Déplacer l'anneau 3 du piquet départ vers le piquet objectif. Déplacer l'anneau 1 du piquet intermédiaire vers le piquet départ. Déplacer l'anneau 2 du piquet intermédiaire vers le piquet objectif. Déplacer l'anneau 1 du piquet départ vers le piquet objectif.
Notons \( T_n \) le nombre de déplacements de disques lors d'un appel à la fonction hanoi(n) (en toute rigueur, il faut se convaincre que les valeurs des autres paramètres n'influencent pas le nombre de déplacements de disques).
Pour exécuter hanoi(n), on fait appel à hanoi(1) une fois et à hanoi(n-1) à deux reprises. hanoi(1) ne demande qu'un seul déplacement de disque (c'est le cas de base). Nous en déduisons la relation : \[ T_{n} = 2\times T_{n-1} + 1 \]
En posant \( v_n = T_n +1 \), nous obtenons une suite \((v_n)\) géométrique de raison 2 : on vérifie en effet facilement que \( v_n = 2v_{n-1} \). Nous avons donc \( v_n = 2^n\times v_0 \), c'est à dire \( v_n = 2^n \).
Finalement : \[ T_n = 2^n -1 \]
Notons \( s_n \) le nombre minimal de déplacements de disques qu'il est possible de réaliser.
Nous savons déjà que : \( s_n \leqslant 2^n-1 \).
Avec n disques, pour déplacer le plus grand disque de l'anneau de départ vers l'anneau but, il faut avoir déplacer tous
les autres anneaux vers l'anneau intermédiaire, c'est à dire avoir exécuté au moins \( s_{n-1} \)
mouvements de disques. On déplace ensuite le grand disque de l'anneau de départ vers l'anneau but : on a
donc fait, à ce moment, au moins \( s_{n-1} +1 \)
mouvements de disques. On doit ensuite déplacer les n-1 plus petits disques vers l'anneau but, c'est à dire
exécuter à nouveau au moins \( s_{n-1} \) mouvements de disques.
Au total, pour déplacer n disques,
il est nécessaire de faire au moins \( 2 s_{n-1} +1 \) mouvements de disques.
Nous avons donc : \( s_n \geqslant 2s_{n-1} +1 \).
Et il est facile, à partir de cette inégalité, de démontrer par récurrence que l'on a
\( s_n \geqslant 2^n-1 \).
\( 2^n -1 \) est donc le nombre minimal de déplacements de disques pour déplacer la tour.
Vous pourrez lire également cet article.
Avec le programme suivant, on "mesure" le temps utilisé par la machine sur laquelle on exécute pour déplacer 15 disques, le déplacement complet étant répété une centaine de fois.
On a supprimé les affichages (qui augmenteraient ici considérablement les temps d'exécution) pour les remplacer par une "action vide" (pass).
from timeit import timeit
def hanoi(n,a='départ',b='intermédiaire',c='objectif',z=1):
""" a piquet de départ.
b piquet intermédiaire.
c piquet d'arrivée.
n nombre d'anneaux à déplacer.
z anneau déplacé."""
if n==1:
pass
#print("Déplacer l'anneau {} du piquet {} vers le piquet {}.".format(z,a,c))
else:
hanoi(n-1,a,c,b)
hanoi( 1,a,b,c, n)
hanoi(n-1,b,a,c)
a=timeit(stmt='hanoi(15)',setup="from __main__ import hanoi",number=100)
print("Avec 15 : ", a)
On conjecture que le temps d'exécution est à peu près proportionnel au nombre de déplacements de disques.
Pour 20 disques par exemple, on multiplie par environ \( 2^5 = 32 \) le nombre de déplacements par rapport au cas de 15 disques. Le temps d'exécution devrait donc être à peu près multiplié par 32 si notre conjecture est correcte.
Cherchons à tester expérimentalement cette hypothèse.
from timeit import timeit
def hanoi(n,a='départ',b='intermédiaire',c='objectif',z=1):
""" a piquet de départ.
b piquet intermédiaire.
c piquet d'arrivée.
n nombre d'anneaux à déplacer.
z anneau déplacé."""
if n==1:
pass
#print("Déplacer l'anneau {} du piquet {} vers le piquet {}.".format(z,a,c))
else:
hanoi(n-1,a,c,b)
hanoi( 1,a,b,c, n)
hanoi(n-1,b,a,c)
a=timeit(stmt='hanoi(15)',setup="from __main__ import hanoi",number=100)
print("Avec 15 : ", a)
b=timeit(stmt='hanoi(20)',setup="from __main__ import hanoi",number=100)
print(" a*2^5 :", a*2**5)
print("Avec 20 : ", b)
Une expérimentation sur ma machine m'a donné ceci :
Avec 15 : 1.431151767999836 a*2^5 : 45.79685657599475 Avec 20 : 45.39163709599961
La plausibilité de la conjecture est renforcée...
Estimons alors le temps pour 64 disques. Le temps nécessaire pour 20 disques doit être multiplié par environ \( 2^{44} \).
Pour 20 disques, le temps d'exécution est d'environ 0,45 secondes. \[ \frac{0.45 \times 2^{44}}{60\times 60\times 24 \times 365} \approx 251030 \]
Plus de 250 000 ans pour exécuter les déplacements avec 64 disques !
Sur un échiquier n sur n, une dame peut prendre les pions se trouvant sur sa ligne, sur sa colonne, sur ses diagonales.
La question : peut-on placer n dames sur un échiquier n*n de façon à ce qu'aucune ne puisse être prise par une autre ?
Programmer la recherche des solutions.
Raisonnons sur un échiquier 8*8.
Plaçons déjà la reine de la colonne 1. Elle peut être placée sur n'importe quelle ligne. Notons ['1', '2', '3', '4', '5', '6', '7', '8'] la liste des lignes sur lesquelles elle peut être placée.
Cherchons maintenant à placer une reine en colonne 2. Pour chaque emplacement possible de la reine de la colonne 1, on dresse la liste des emplacements possibles pour la reine de la colonne 2.
Par exemple pour l'emplacement reine colonne 1 en ligne 1, la reine de la colonne 2 peut occuper toute ligne sauf les lignes 1 et 2.
| R | non |
| non | |
| ok | |
| ok | |
| ok | |
| ok | |
| ok | |
| ok |
Dans la liste des 'solutions' pour deux reines, nous aurons donc déjà '13', '14', '15', '16', '17', '18'.
Lorsque la reine de la colonne 1 est en ligne 2, la reine de la colonne 2 peut se placer partout sauf sur les lignes 1, 2 ou 3.
| non | |
| R | non |
| non | |
| ok | |
| ok | |
| ok | |
| ok | |
| ok |
A la liste des solutions pour deux reines, on peut donc ajouter '24', '25', '26', '27', '28'.
On poursuit ainsi pour chacune des positions possibles de la reine 1. On obtient la liste complète suivante : ['13', '14', '15', '16', '17', '18', '24', '25', '26', '27', '28', '31', '35', '36', '37', '38', '41', '42', '46', '47', '48', '51', '52', '53', '57', '58', '61', '62', '63', '64', '68', '71', '72', '73', '74', '75', '81', '82', '83', '84', '85', '86'].
Ayant obtenu la liste complète des solutions possibles pour les deux premières reines, comment construire la liste pour les trois premières reines ?
Pour chacune des solutions pour les deux premières, on teste chacune des lignes pour la reine de la colonne 3 et on ne retient
que les positions telles que cette reine colonne 3 ne soit pas en prise avec les deux premières reines.
On obtient la liste suivante :
['135', '136', '137', '138', '142', '146', '147', '148', '152', '157', '158',
'162', '164', '168', '172', '174', '175', '182', '184', '185', '186', '241',
'246', '247', '248', '251', '253', '257', '258', '261', '263', '268', '271',
'273', '275', '281', '283', '285', '286', '314', '316', '317', '318', '352',
'357', '358', '362', '364', '368', '372', '374', '382', '384', '386', '413',
'415', '417', '418', '425', '427', '428', '461', '463', '468', '471', '473',
'475', '481', '483', '485', '514', '516', '518', '524', '526', '528', '531', '536',
'538', '571', '572', '574', '581', '582', '584', '586', '613', '615', '617', '625',
'627', '631', '635', '637', '641', '642', '647', '681', '682', '683', '685', '713',
'714', '716', '718', '724', '726', '728', '731', '736', '738', '741', '742', '746',
'748', '751', '752', '753', '758', '813', '814', '815', '817', '824', '825', '827',
'831', '835', '837', '841', '842', '847', '851', '852', '853', '857', '861', '862',
'863', '864'].
On a ainsi défini notre processus récursif.
Traduction en langage python :
def ok(c) :
"""
c='*254' signifie
reine colonne 1, ligne 2;
reine colonne 2, ligne 5;
reine colonne 3, ligne 4.
Retourne True si reines non en prise.
On teste seulement la dernière reine
par rapport aux précédentes.
L'étoile placée en début de c ne sert qu'à avoir
des indices de 1 à n correspondant à une
numérotation 'naturelle' des colonnes de 1 à n.
"""
n=len(c)-1 # nb de reines
rr=c[-1] # ligne de la reine à tester
for i, r in enumerate(c) :
if 0<i<n :
if r==rr : return False
elif i+int(r)==n+int(rr) : return False
elif i-int(r)==n-int(rr) : return False
return True
def LesSolutions(n) :
""" Retourne la liste des solutions
pour un échiquier n*n."""
def solut(n,r) :
"""
n : echiquier n*n.
r : numéro de la colonne où l'on cherche à placer une reine.
retourne la liste des emplacements possibles pour la
colonne r.
"""
if r==1 : return [str(i) for i in range(1,n+1)]
else :
S=[]
for j in solut(n, r-1) :
for k in range(1,n+1) :
if ok('*'+j+str(k)) :
S.append(j+str(k))
return S
return solut(n,n)
def afficher(solu, n) :
"""
Affichage d'une solution
pour un échiquier n*n.
La solution solu donnée en argument est sous la forme '*235...'
"""
print(' ',end=' ')
for k in range(1,n+1) : print(k,end='|')
print()
for l in range(1,n+1) :
print(l,end='|')
for c in range(1,n+1) :
if solu[c]==str(l) :
print('R',end='|')
else :
print(' ',end='|')
print()
n=8 # taille de l échiquier
S=LesSolutions(n) # liste des solutions
print("Le nombre de solutions : ", len(S), "\n") # nombre de solutions
print(S,"\n") # affichage des solutions sous la forme chaînes
afficher('*'+S[0],n) # affichage de la première solution
# de la liste sous la forme dessin de grille
On obtient pour S[0] :
1|2|3|4|5|6|7|8| 1|R| | | | | | | | 2| | | | | | |R| | 3| | | | |R| | | | 4| | | | | | | |R| 5| |R| | | | | | | 6| | | |R| | | | | 7| | | | | |R| | | 8| | |R| | | | | |
et pour la liste S (92 solutions) :
['15863724', '16837425', '17468253', '17582463', '24683175', '25713864', '25741863', '26174835', '26831475', '27368514', '27581463', '28613574', '31758246', '35281746', '35286471', '35714286', '35841726', '36258174', '36271485', '36275184', '36418572', '36428571', '36814752', '36815724', '36824175', '37285146', '37286415', '38471625', '41582736', '41586372', '42586137', '42736815', '42736851', '42751863', '42857136', '42861357', '46152837', '46827135', '46831752', '47185263', '47382516', '47526138', '47531682', '48136275', '48157263', '48531726', '51468273', '51842736', '51863724', '52468317', '52473861', '52617483', '52814736', '53168247', '53172864', '53847162', '57138642', '57142863', '57248136', '57263148', '57263184', '57413862', '58413627', '58417263', '61528374', '62713584', '62714853', '63175824', '63184275', '63185247', '63571428', '63581427', '63724815', '63728514', '63741825', '64158273', '64285713', '64713528', '64718253', '68241753', '71386425', '72418536', '72631485', '73168524', '73825164', '74258136', '74286135', '75316824', '82417536', '82531746', '83162574', '84136275']
On peut facilement écrire ici une version non récursive de l'algorithme décrit précédemment.
def ok(c) :
""" c='*254' signifie
reine colonne 1, ligne 2;
reine colonne 2, ligne 5;
reine colonne 3, ligne 4.
Retourne True si reines non en prise.
On teste seulement la dernière reine par rapport aux précédentes.
L'étoile placée en début de c ne sert qu'à avoir
des indices de 1 à n correspondant à une numérotation 'naturelle' des colonnes de 1 à n.
"""
n=len(c)-1 # nb de reines
for i in range(1,n) :
if c[i]==c[n] : return False
elif i+int(c[i])==n+int(c[n]) : return False
elif i-int(c[i])==n-int(c[n]) : return False
return True
def resolution(n) :
""" Retourne la liste des solutions pour un échiquier n*n."""
solu=['*'+str(i) for i in range(1,n+1)]
for i in range(2,n+1) :
solut=solu[:]
solu=[]
for j in solut :
for k in range(1,n+1) :
if ok(j+str(k)) : solu.append(j+str(k))
return solu
def afficher(solu, n) :
""" Affichage d'une solution pour un échiquier n*n.
La solution solu donnée en argument est sous la forme '*235...' """
print(' ',end=' ')
for k in range(1,n+1) : print(k,end='|')
print()
for l in range(1,n+1) :
print(l,end='|')
for c in range(1,n+1) :
if solu[c]==str(l) :
print('R',end='|')
else :
print(' ',end='|')
print()
n=8 # taille de l échiquier
S=resolution(n) # liste des solutions
print("Le nombre de solutions : ", len(S), "\n") # nombre de solutions
print(S,"\n") # affichage des solutions sous la forme chaînes
afficher('*'+S[0],n) # affichage de la première solution
# de la liste sous la forme dessin de grille