4SI - Programmation
a
202 afa
24/ A N
5
: 20 AD
Partie 5 :
A.S . SA
Les algorithmes récurrents :
(Algorithmique et Programmation)
r
:M
f
Pro
32
4SI - Programmation
Les algorithmes récurrents:
1- Définition :
Un algorithme ou un traitement est dit récurrent s'il utilise un procédé itératif
a
ou récursif pour donner un résultat qui peut dépendre de un ou plusieurs
résultats précédents.
202 afa
Un algorithme récurrent d’ordre n est un
algorithme donnant un résultat qui dépend
24/ A N
de n résultats précédents.
5
1- Exemples de traitements récurrents :
Le calcul de la somme , de la factorielle, de la puissance, du nombre, d’un terme d’une suite, la
: 20 AD
recherche du maximum, le triangle de Pascal, la suite de Fibonacci, le nombre d’or, … sont des
exemples de traitements récurrents.
2.1/ Calcul de la somme :
Exercice 28 (Somme matrice)
A.S . SA
1- Soit M une Matrice de type Mat formée par L lignes et de C colonnes déjà remplie par des
entiers. On demande de faire l’algorithme de la fonction qui calcule et retourne la somme de
la matrice M.
2- Quel est l’ordre de récurrence du traitement développé dans la question précédente ?
r
f :M
Pro
33
4SI - Programmation
2.2/ Traitement récurrent sur les chaines :
Exercice 29 (Suite de Thue-Morse)
C’est une suite binaire définie par : U0 = 0 ou U0 = 1 et par la récurrence suivante : pour
passer de Un à Un+1 on remplace tous les 0 de Un par 01 et tous les 1 par 10.
a
Exemple d’exécution :
202 afa
U0=0 (ou U0=1)
U1=01
U2=01 10
U3=01 10 10 01
24/ A N
Travail demandé :
1- Sachant que U0=0, Calculer le terme U4 de la suite Thue-morse
…………………………………………………………………………………………………………………………………………..
5
2- Quelle est l’ordre de récurrence de cette suite ?
…………………………………………………………………………………………………………………………………………..
: 20 AD
3- Faire le programme Python qui permet de :
• Saisir le premier terme de la suite de Thue Morse (qui peut être 0 ou 1).
• Saisir N , le nombre de termes à calculer (avec N > 2).
• Calculer et afficher les N premiers termes de la suite Thue-morse
A.S . SA
r
f :M
Pro
34
4SI - Programmation
2.3/ Triangle de Pascal :
Le triangle de pascal est la matrice des coefficients (coefficients du binôme) qui sont utilisées
pour développer des expressions comme (a+b)0 , (a+b)1 , … , (a+b)n
Exemple :
a
(a+b)0 = 1 les coefficients : 1
(a+b) = 1*a + 1*b
1 les coefficients : 1,1
202 afa
(a+b)2= 1*a2 + 2*a*b + 1*b2 les coefficients : 1,2,1
(a+b) = 1*a + 3*a *b + 3*a*b +1*b
3 3 2 2 3 les coefficients : 1,3,3,1
(a+b)4= 1*a4 + 4*a3*b + 6*a2*b2 + 4*a*b3 +1*b4 les coefficients : 1,4,6,4,1
Calculer les coefficients pour (a+b)5 ➔ ………………………………………………………………..
24/ A N
Pour N=5, le triangle de pascal affiché est le suivant:
5
: 20 AD
On constate que le calcul de MAT[4,3] fait référence à deux résultats précédents : MAT[3,3] et
A.S . SA
MAT [3,2] donc il s’agit d’un traitement récurrent d’ordre 2.
Comment obtenir un triangle de pascal ?
De façon générale le triangle de pascal (d’ordre N) s’obtient de la façon suivante :
• Initialiser une matrice carré M (d’ordre N) par la valeur 0
• La première colonne de M doit contenir dans chaque cellule, la valeur 1.
r
• Les autres éléments sont déterminés en appliquant la formule suivante :
M[i,j] = M[i-1,j] + M[i-1,j-1] (avec i =numéro de la ligne et j =numéro de la colonne)
:M
Exercice 30 (Triangle de Pascal)
On se propose d’afficher les N premières lignes du triangle de Pascal (avec 3 ≤ N <20). On vous
demande de faire le programme python permettant de remplir et d’afficher les N premières
f
lignes du triangle de Pascal comme le montre l’exemple suivant :
Pro
Exemple d’exécution :
35
4SI - Programmation
2.4/ Suite de Fibonacci :
Leonardo Pisano, connu sous le nom de Fibonacci, étudia la reproduction des lapins (du point de
vue numérique). Il a remarqué qu’un couple de jeunes lapins met une saison pour devenir
adulte, attend une autre saison puis met au monde un couple de jeunes lapins à chaque saison
suivante. Et il a conclu que la reproduction des lapins peut être représentée par la suite
suivante :
a
U1 = 1
U2 = 1
202 afa
Un = Un-1+Un-2
Exercice 31 (Suite de Fibonacci)
24/ A N
1- Quelle est l’ordre de récurrence de la suite de Fibonacci ? Réponse : ……………………………….
2- Donner les valeurs correspondantes aux termes suivants :
U1 U2 U3 U4 U5 U6 U7
5
1 1
2- Pour un entier N donné, donner l’algorithme de la fonction « fibo » qui calcule et renvoie le
Nième terme de la suite de Fibonacci :
: 20 AD
a- en utilisant un traitement itératif
A.S . SA
r
b- en utilisant un traitement récursif
f :M
Pro
36
4SI - Programmation
2.5/ Nombre d’Or :
Exercice 32 (Nombre d’or)
1- Compléter le tableau suivant :
a
202 afa
24/ A N
5
: 20 AD
A.S . SA
Il semble que Vn = Fib(n+1) / Fib(n) converge vers 1,618. Donc la suite de Fibonacci et la
valeur 1,618 sont fortement liées. La valeur à laquelle converge Vn s’appelle le nombre d’or
r
Travail demandé :
:M
Soient deux suites U et V définies comme suit :
U1= 1
U2=1
Un=Un-1 + Un-2 pour n ≥ 3
et
f
V1= 1
Pro
Vn=Un/Un-1 pour tout n ≥ 2
La suite Vn tend vers une limite appelée nombre d’or.
On suppose que le nième terme de la suite V est égal à Vn.
Vn est la valeur approchée du nombre d’or avec une précision e dès que | V n – Vn-1| ≤ e.
On désire faire le programme python qui cherche Vn à 10-4 près et son rang.
37
