-
SERIE 6 PSI 2014 - 2015
L.OUSTOUH 1 / 3 CPGE ISMAILIA
CLASSES PREPARATOIRES AUX GRANDES ECOLES : CPGE Option :
Physique et Sciences de lIngnieur (PSI sp)
Etablissement : CPGE ISMAILIA
Algorithmique et programmation
Chapitre 6 : rcursivit SERIE N6
Enseignante : L.OUSTOUH
EXERCICE DE COMPREHENSION DE COURS ET DAPPLICATION Exercice
1
1. crire une fonction rcursive calculant la somme des n premiers
termes dune suite arithmtique de premier terme a et de raison r
donns.
2. Mme chose pour une suite gomtrique 3. Ecrire une fonction
rcursive calculant le PGCD de deux entiers positifs (non tous deux
nuls) a et b
par lalgorithme dEuclide. 4. Ecrire une fonction rcursive
renvoyant linverse dune chaine de caractres passe en argument.
Par exemple : >>>inverse("blabla") albalb
>>>inverse("") >>>inverse("ressasser")
ressasser
5. En dduire une fonction palindrome testant si une chaine est
gale son inverse (elle renvoie boolen).
Exercice 2 : calcul de puissances. Cet exercice est classique et
fondamental
1. Ecrire une fonction puissance prenant en entre deux paramtres
x et n et calculant rcursivement , en exploitant lgalit valable
pour tout n 1. On conviendra que pour tout rel
2. Estimer la complexit de votre fonction. 3. Voici une autre
fonction :
def puissance2(x,n): if n==0:
return(1) else:
q,r=n//2,n%2 u=puissance2(x,q) if r==0:
return(u*u) else:
return(u*u*x) dmontrer la terminaison et la correction de
puissance2.
4. Montrer que puissance2 sexcute en temps O(log(n)) (en termes
doprations arithmtiques).
-
SERIE 6 PSI 2014 - 2015
Page 2 sur 3
EXERCICE Exercice 1 : crire une fonction rcursive base10to2
prenant en entre un entier positif N, et renvoyant lcriture binaire
de N sous la forme dune chane de caractres. On renverra la chane
vide pour zro. >>> base10to2(35) 100011 Exercice 2 : La
tte Toto (un exo IOI). 0 (zro), a scrit aussi (0 + 0), ou encore
((0 + 0) + (0 + 0)). crire une fonction rcursive zeros en Python,
prenant en entre un entier n et affichant lcran la chane
correspondante. Par exemple : >>> zeros(0) 0 >>>
zeros(2) ((0+0)+(0+0)) >>> zeros(4)
((((0+0)+(0+0))+((0+0)+(0+0)))+(((0+0)+(0+0))+((0+0)+(0+0))))
PROBLEME : Les tours de HANO Sur une tablette sont plantes trois
tiges que nous nommerons A, B,C. au dpart, on enfile n disques de
rayons dcroissants sur la tige A de manire former une pyramide. Il
sagit de dplacer les disques de la tige A vers la tige C un un en
respectant la rgle suivante : on peut ter le disque du sommet pour
lenfiler sur une autre tige condition quil ne se pose pas sur un
disque de rayon plus petit (autrement dit, les disques forment
toujours des pyramides sur chaque tige).
1. Rsoudre le problme la main pour n=1,2,3. 2. Ce problme se
rsout trs simplement par rcurrence. Appelons deplacer(A,B,C,n)
lopration qui
consiste dplacer les n disques suprieurs de la tige A vers la
tige C en se servant de la tige B comme tige intermdiaire.
Si n=1, il ny a qu dplacer le disque de A vers C.
En revanche si n>1, nous pouvons commencer par dplacer les
n-1 disques suprieurs de A vers B. ceci fait, nous dplaons le plus
grand disque de Avers C, puis nous dplaons de nouveau les n-1
disques deB vers C. en procdant ainsi, nous sommes certains de
respecter la rgle du jeu.
a. Ecrire une fonction move(A,C) qui affiche lecran le mouvement
de la forme tige A tige C, o A et C sont deux lments distincts, La
signification du mouvement est la suivante : dplacer le disque en
haut de lemplacement A sur lemplacement C.
Situation initiale
Aprs deplacer(A,C,B,n-1)
Aprs move(A,C)
Aprs deplacer(B,A,C,n-1)
-
SERIE 6 PSI 2014 - 2015
Page 3 sur 3
b. Ecrire la fonction rcursive deplacer(A,B,C,n), la fonction
devra afficher lcran une suite de mouvements des disques.
3. Quelle est la complexit de votre fonction, dduire le nombre
de mouvement de disques. 4. Dessiner larbre des appels rcursifs
pour n=3. 5. Estimer le temps ncessaire pour dplacer 64 disques si
un dplacement se faisant en une
microseconde, puis en une nanoseconde.
