Dhouihri Alaa - site éducative pour les étudiants de ...Ce nouveau calcul n'utilise pas un procédé itératif mais il appelle la même fonction avec un nouveau paramètre qui est

4INFINFRC0001 Page 1

LES ENREGISTREMENTS

I/ Définition : Un enregistrement est un type de données défini par l'utilisateur et qui permet de

II/ Déclaration : Déclaration d’une structure enregistrement En algorithmique : Puisque l'enregistrement est un nouveau type, on commence par sa déclaration : Tableau de déclaration des nouveaux types

Type Nom_type = Enregistrement champ 1 : Type 1 - - - - champ n : Type n Fin Nom_Type Puis la déclaration des objets (variables) utilisant ce type Tableau de déclaration des objets

Objet Type / Nature Rôle identificateur_objet

Nom_type Enregistrement pour …

En Pascal : TYPE Nom_type = Record champ_1 : type_1 ; - - - - champ_n : type_n ; End; VAR identificateur_objet : Nom_type ; III/ Utilisation

grouper un nombre fini d'éléments (ou champs) de types éventuellement différents.

CHAPITRE 1

Dhouihri Alaa

http://www.najah.com


Utilisation pour une action d'affectation L'affectation de valeurs aux différents champs d'une variable de type enregistrement se fait par une opération de type :

En algorithmique En Pascal variable.champ ← valeur variable.champ := valeur ; Exemple : En algorithmique : Tableau de déclaration des nouveaux types :

Type Fiche = enregistrement nom, prénom : Chaîne sexe : Caractère numéro : Entier non signé moyenne : Réel num_cin : Entier long Fin Fiche Tableau de déclaration des objets :

Objet Type / Nature Rôle élève

Fiche Enregistrement pour une fiche d'un étudiant

Affectation de valeurs à cette variable : élève.nom ← "Swidi" élève.prénom ← "Basma" élève.sexe ← "F" élève.numéro ← 18 élève.moyenne ← 13.25 élève.num_cin ← 12345678 En Pascal : Le type enregistrement. TYPE Fiche = Record nom, prenom : String ; sexe : Char ;



numero : Byte ; moyenne : Real ; num_cin : LongInt ; End ; Déclaration de la variable élève : VAR eleve : Fiche ; Affectation des valeurs à cette variable : eleve.nom := 'Swidi' ; eleve.prenom := 'Basma' ; eleve.sexe := 'F' ; eleve.numero := 18 ; eleve.moyenne := 13.25 ; eleve.num_cin := 12345678 ; Utilisation pour une action de lecture

Au niveau de l'analyse Au niveau de l'algorithme Au niveau du Pascal variable.champ = Donnée Lire (variable.champ) ReadLn (variable.champ); Exemple : Au niveau de l'analyse : élève.nom = Donnée ("Entrer le nom de l'élève : ") Au niveau de l'algorithme : Ecrire ("Entrer le nom de l'élève : ") ; Lire (élève.nom) Au niveau du Pascal : Write ('Entrer le nom de l''élève : ') ; ReadLn (eleve.nom) ; Utilisation pour une action d'écriture

Au niveau de l'analyse et de l'algorithme Au niveau du Pascal Ecrire (variable.champ) Write (variable.champ); Exemple :



Au niveau de l'analyse et de l'algorithme : Ecrire ("Nom : ", élève.nom) Au niveau du Pascal : WriteLn ('Nom : ', eleve.nom) ; Structure Avec .. Faire Pour simplifier l'écriture et éviter l'utilisation répétée des champs et de la notation avec le point (variable.champ), on peut utiliser l'instruction Avec .. Faire (With .. Do). Cette structure s'utilise aussi bien avec une opération d'affectation, de lecture ou d'écriture. Syntaxe :

Au niveau de l'analyse et de l'algorithme Au niveau du Pascal Avec variable Faire {ensemble d'actions} Fin Avec

With variable Do Begin {ensemble d'actions} End;

Au Niveau de l'algorithme : Avec élève Faire {Affectation}

nom ← "Swidi" {Lecture} Ecrire ("Entrer le sexe de l'étudiant : ") ; Lire (sexe) {Ecriture}

Ecrire ("Moyenne : ", moyenne) Fin Avec Au Niveau du Pascal : With etudiant Do Begin nom := 'Swidi' ; Write ('Entrer le sexe de l''élève : ') ; ReadLn (sexe) ;

WriteLn ('Moyenne : ', moyenne) ; End;



Vecteur d'enregistrements Un tableau ne peut grouper ou contenir que des éléments de même type, et puisque les éléments d'un enregistrement sont de même type qui est celui de l'enregistrement, donc on peut utiliser un tableau ou un vecteur d'enregistrements. Exemple : Tableau de déclaration des nouveaux types : Déclaration de la variable T utilisant les enregistrements des élèves :

Tableau de déclaration des objets :

Objet Type / Nature Rôle T Tab Tableau d'enregistrements pour les fiches des élèves Activité Un médecin enregistre sur ordinateur les fiches de ses Patients. Une fiche a la la structure suivante :

- un nom (chaîne de 30 caractères maximum) - un numéro (entier) - un numéro de téléphone (10 caractères maximum) - un code d'assurance (entier non signé).

1/ Ecrire les analyses, les algorithmes des différents modules d'un programme nommé Fiche, qui permet la saisie et l'affichage de l'enregistrement d'un Patient. 2/ Traduire ce programme en Pascal

1/ Analyses et algorithmes : Analyse du programme principal Résultat : Affichage d'une fiche - Traitement : - Une fiche peut être représentée par une structure d'enregistrement

comportant 4 champs (le nom, le numéro, le numéro de téléphone et le code d'assurance). - L'affichage des différents champs sera la tâche de la procédure Afficher.

Type Fiches = Enregistrement nom, prénom : Chaîne sexe : Caractère numéro : Entier non signé moyenne : Réel num_cin : Entier long Fin Fiches Tab = Tableau de 30 Fiches {tableau d'enregistrements fiches}



- La saisie des différents champs se fera par la procédure Saisir. Fin Analyse Algorithme du programme principal 0) Début Fiche 1) Saisir (Patient) 2) Afficher (Patient) 3) Fin Fiche Tableau de déclaration des nouveaux types

Type Personne = Enregistrement nom : Chaîne de 30 caractères numéro : Entier tel : Chaîne de 10 caractères code : Entier non signé Fin Personne Tableau de déclaration des objets globaux :

Nom Type / Nature Rôle Patient Saisir Afficher

Personne Procédure Procédure

Enregistrement pour une fiche personne Saisie des champs Affichage des champs

Analyse de la procédure saisir Résultat : Saisir les champs Traitement : La saisie des différents champs de l'enregistrement se fera par des opérations de lecture avec l'utilisation de la structure Avec .. Faire, sur la variable Patient. Patient : représente la variable de l'enregistrement. Fin Analyse Algorithme de la procédure Saisir 0) Procédure Saisir (VAR Patient : Personne) 1) Avec Patient Faire Ecrire ("Entrer le nom de la personne : ") ; Lire (nom) Ecrire ("Entrer son numéro : ") ; Lire (numéro) Ecrire ("Entrer son numéro de téléphone : ") ; Lire (tel) Ecrire ("Entrer le code d'assurance : ") ; Lire (code)



Fin Avec 2) Fin Saisir Analyse de la procédure Afficher Résultat : Afficher les champs Traitement : L'affichage des différents champs de l'enregistrement se fera par des opérations d'écriture avec l'utilisation de la structure Avec .. Faire, sur la variable Patient. Fin Analyse. Algorithme de la procédure Afficher 0) Procédure Afficher (Patient : Personne) 1) Avec Patient Faire Ecrire ("Nom : ", nom) Ecrire ("numéro : ", numéro) Ecrire ("Numéro de téléphone : ", tel) Ecrire ("Code assurance : ", code) Fin Avec 2) Fin Afficher 2/ Traduction en Pascal PROGRAM Fiche ; USES Crt ; TYPE Personne = Record nom : String [30] ; numero : Integer ; tel : String [10] ; code : Word ; End ; VAR Patient : Personne ; {--------------------------------------------------------------------------------------------} PROCEDURE Saisir (VAR Patient : Personne) ; BEGIN With Patient Do Begin

Write ('Entrer le nom de la personne : ') ; ReadLn (nom) ; Write ('Entrer son numéro : ') ; ReadLn (numero) ; Write ('Entrer son numéro de téléphone : ') ; ReadLn (tel) ; Write ('Entrer son code d’’assurance : ') ; ReadLn (code) ; End ; END ; {--------------------------------------------------------------------------------------------} PROCEDURE Afficher (Patient : Personne) ; BEGIN With Patient Do



Begin WriteLn ('Nom : ', nom) ;

WriteLn ('Numéro : ', numero) ; WriteLn ('Numéro du téléphone : ', tel) ; WriteLn ('Code d’’assurence : ', code) ; End; END; {= = = = = = = = = = = Programme Principal = = = = = = = = = = =} BEGIN Saisir (Patient) ; Afficher (Patient); END.



CHAPITRE 2

LA RECURSIVITE

I- Introduction

Activité 1 Reprenons l'exercice de calcul de la factorielle étudié en troisième année. Nous avons écrit la fonction suivante : Analyse de la fonction Factorielle Résultat : Factorielle Traitement : On initialise F à 1 (F ← 1), car Factorielle de zéro = 1 et Factorielle de 1 = 1 On termine le calcule, par une itération complète de 2 à N

Pour i de 2 à n Faire F ← F * i

Fin Analyse Algorithme de la fonction Factorielle 0) Fonction Factorielle (n : Entier) : Entier Long 1) F ← 1 2) Pour i de 2 à n Faire F ← F * i Fin Pour 3) Factorielle ← F 4) Fin Factorielle Tableau de codification des objets locaux

Objets Type/Nature Rôle F Entier Long La factorielle de n i Entier Compteur NB : Ce calcul a été obtenu à partir d'une boucle Pour … Faire. C'est un traitement itératif. Reprenons, pas à pas, le calcul de la factorielle.



n ! = n * (n-1) * (n-2) * (n-3) * … * 1 Avec 0 ! = 1

On peut mettre en évidence les différentes étapes :

Factorielle (n) = n * (n-1) * (n-2) * (n-3) * … * 1 et factorielle (0) = 1

On remarque que l'écriture en rouge représente la factorielle de n-1, donc on peut écrire :

Factorielle (n) = n * factorielle (n-1) et factorielle (0) = 1

Ce nouveau calcul n'utilise pas un procédé itératif mais il appelle la même fonction avec un nouveau paramètre qui est (n-1).

Ce procédé, un module qui fait appel à lui-même, s’appelle Traitement Récursif

On peut donc écrire une fonction récursive de calcul de la factorielle d'un entier N. Algorithme de la fonction Factorielle : solution récursive 0) Fonction Factorielle (n : Entier) : Entier Long 1) Si (n = 0) Alors Factorielle ← 1 {test de sortie} Sinon Factorielle ← n * Factorielle (n-1) {appel récursif} Fin Si 2) Fin Factorielle

Programme Pascal utilisant la fonction récursive de calcul de la factorielle PROGRAM Fact_rec; Uses Crt; Var n : Integer; {----------------------------------------------------------------} Function Factorielle (n : Integer) : LongInt; Begin

If (n = 0) Then Factorielle := 1 Else Factorielle := n * Factorielle (n - 1);

End; {= = = = = = = Programme Principal = = = = = = = = } BEGIN

Write ('n = '); ReadLn (n); Write ('n! = ', Factorielle (n));

END.

Activité 2



- Ecrire une analyse et l'algorithme d'une Procédure qui saisie un entier N tel que (2 ≤ N ≤ 100).

Nous avons vu qu'une fonction peut être récursive. Une procédure peut-elle être l'être ? Si oui, proposer une version récursive de cette procédure saisie.

Analyse Résultat = Lire et n'accepter qu'une valeur de N entre 2 et 100. Traitement : Répéter la lecture de N jusqu'à une saisie valide suivant la condition proposée. Fin Analyse Algorithme : 0) Procédure Saisie (VAR N : Entier) 1) Ecrire ("Entrer un entier N : ") 2) Lire (N) 3) Si (N < 2) OU (N > 100) Alors Saisie (N) {appel récursif} 4) Fin Saisie II- Définitions La récursivité est une méthode algorithmique qui consiste à appeler un sous-programme dans son propre corps. Un sous-programme récursif est un module qui fait appelle à lui-même. A chaque appel, il y a mémorisation d’une valeur différente d'un même paramètre formel. Un programme récursif doit : * Avoir au moins un point d'arrêt (une condition de sortie) pour ne pas être dans une boucle infinie. * Avoir un ou plusieurs traitements représentés par des appels récursifs.



Application 1

On se propose de calculer et d’afficher la valeur de x à la puissance n. x et n sont respectivement un réel et un entier donnés. Questions : a) Analyser le problème en utilisant un module récursif, b) Donner les algorithmes correspondants, c) Traduire l'ensemble en un programme Pascal.

a) Analyse du problème Résultat : Ecrire (x, " à la puissance ", n, " = ", Fn Puissance (x, n)) Traitement :

Puissance est une fonction récursive permettant de calculer la valeur de xn. Fin Analyse b) Algorithme du programme principal 0) Début Prg_puissance 1) Ecrire ("Donner un réel : ") , Lire (x) 2) Ecrire ("Donner en entier n : ") , Lire (n) 3) Ecrire (x, " à la puissance ", n, " = ", Fn Puissance (x, n)) 4) Fin Prg_puissance



Tableau de codification des objets globaux Objets Type/Nature Rôle

x Réel Donnéen Entier L’exposantPuissance Fonction Permet de déterminer la valeur xn

Analyse de la fonction Puissance Résultat : Puissance Traitement : Si (n = 0) alors Puissance ← 1 {condition de sortie} Sinon Si (n < 0) alors Puissance ← 1 / Fn Puissance (a, -n) Sinon Puissance ← a * Fn Puissance (a, n-1) Fin Analyse Algorithme récursif de la fonction Puissance 0) Fonction Puissance (x : Réel ; n : Entier) : Réel 1) Si n = 0 Alors Puissance ← 1 Sinon Si n < 0 Alors Puissance ← 1 / Fn Puissance (a, -n) Sinon Puissance ← a * Fn Puissance (a, n-1) Finsi 2) Fin Puissance Programme Pascal PROGRAM Prg_Puissance ; USES WinCrt ; VAR x : Real ; n : Integer ; {------------------------------------------------------------------------------------} Function Puissance (x : Real; n : Integer) : Real; Begin If (n = 0) Then Puissance := 1 Else If (n < 0) Then Puissance := 1 / Puissance (a, -n) Else Puissance := a * Puissance (a, n - 1); END; {========================== p p ==============================} BEGIN Write ('Donner un réel '); ReadLn (x); Write ('Donner un entier : '); ReadLn (n);



WriteLn (' x, " à la puissance ", n, " = ", Puissance (x, n)) ; END. Application 2 Ecrire un module récursif, qui cherche la présence d’une valeur entière V dans un tableau T de n d'entiers (4 ≤ n ≤ 20), en utilisant la méthode de recherche dichotomique. NB : Le tableau sera trié au cours de son remplissage.

Questions : a) Analyser le problème et écrire son algorithme b) Proposer une analyse et un algorithme du module récursif, a) Analyse du problème Résultat : Si existe Alors Ecrire (V, " existe dans le tableau T.") Sinon Ecrire (V, " n’existe pas dans le tableau T.") Traitement : existe est le résultat Booléen d'une fonction de recherche par la technique de dichotomie, elle est appelée Dicho_Rec (Dichotomie récursive) Fin Analyse Algorithme du programme principal Recherche 0) Début Recherche 1) Saisir (n) 2) Remplir_Trier (n, T) 3) Ecrire ("Donner un entier : ") , Lire (V) 4) existe Dicho_Rec (1, n, V, T) 5) Si existe Alors Ecrire (V, " existe dans le tableau T.") Sinon Ecrire (V, " n’existe pas dans le tableau T.") Fin si 5) Fin Recherche



Tableau de déclaration des objets globaux

Objets Type/Nature Rôle T Tab Tableau d'entiers n Entier Taille du tableau V Entier Valeur recherchée Dicho_Rec Fonction Recherche récursive et dichotomique de V dans T Saisir Procédure Permet de saisir la taille du tableau Remplir_Trier Procédure Permet de remplir le tableau trié existe Boolean Reçoit le résultat de la fonction Dicho_Rec

Tableau de déclaration des nouveaux types

Type Tab = Tableau de 20 entiers



b/ Analyse de la fonction Dicho_Rec Résultat : Dicho_Rec Traitement : - le résultat final est un Booléen qui indique que V est trouvée ou non. - Une première condition de sortie est que V = T[milieu] alors V existe dans T. Une seconde est que V n'existe pas dans le tableau. Sinon Si V< T[milieu] et début < milieu, alors nous cherchons l’existence de V dans la première moitié du tableau (Dich_Rec ← Fn Dich_Rec (debut, milieu-1, V, T)) Sinon Si V > T[milieu] et Fin > milieu, alors nous on cherche V dans l'autre moitié du tableau (Dicho_Rec ← Fn Dicho_Rec (milieu+1, fin, V, T)) milieu est le milieu d'un tableau entre début (case de départ) et Fin (case finale)

milieu ← (début + fin) Div 2 Fin Analyse Algorithme récursif de la fonction Dicho_Rec 0) Fonction Dicho_Rec (début, fin, V : Entier ; T : Tab ) : Booléen 1) milieu ← (début + fin) Div 2 2) Si V = T[milieu] Alors Dicho_Rec ← Vrai Sinon Si (V < T[milieu]) ET (début < milieu) Alors Dicho_Rec ← Fn Dicho_Rec (début, milieu-1, V, T) Sinon Si (V > T[milieu]) ET (fin > milieu) Alors Dicho_Rec ← Fn Dicho_Rec (milieu +1, fin, V, T) Sinon Dicho_Rec ← Faux Fin Si 3) Fin Dicho_Rec Tableau de déclaration des objets locaux

Objets Type/Nature Rôle milieu Entier Indice de l’élément du milieu de la partie dans laquelle

s’effectue la recherche. Analyse de la procédure Saisie Résultat : Saisie de la taille du tableau Traitement :

Répéter Lire (n)

Jusqu'à n Dans [4 .. 20] Fin Analyse Algorithme de la procédure Saisie 0) Procédure Saisie (VAR n : Entier ) 1) Répéter Ecrire ("N = "); Lire (n) Jusqu'à n Dans [4 .. 20]



2) Fin Saisie Analyse de la procédure Remplir_Trier Résultat : Tableau trié Traitement :

Lire T[1] Lire T[2] et n'accepter la que une valeur supérieure ou égal T[1] Répéter ce traitement pour les n valeurs du tableau. Fin Analyse

Algorithme de la procédure Remplir_Trier 0) Procédure Remplir_Trier (n : Entier ; VAR T : TAB) 1) Ecrire ("T[1] = ") 2) Lire (T[1]) 3) Pour i de 2 à n Faire Répéter Ecrire ("T[", i, "] = ") Lire (T[i]) Jusqu'à (T[i] ≥ T[i-1]) 4) Fin Remplir_Trier Tableau de codification des objets locaux

Objets Type/Nature Rôle i Entier Compteur Traduction en Pascal PROGRAM Recherche ; USES WinCrt ; TYPE TAB = ARRAY[1..20] Of Integer ; VAR T: TAB ; n, V : Integer ; existe : Boolean ; {-----------------------------------------------------------------------------------------} PROCEDURE Saisie (VAR n : Integer); BEGIN Repeat Write ('N = '); ReadLn (n); Until n IN [4..20]; END ;



{-----------------------------------------------------------------------------------------} PROCEDURE Remplir_Trier (n : Integer ; VAR T : TAB) ; VAR i : Integer ; BEGIN

Write ('T[1] = ') ; ReadLn (T[1]) ; For i:= 2 To N Do Begin

Repeat Write ('T[', i, '] = ') ; ReadLn (T[i]) ; Until (T[i] >= T[i-1]) ; End; END; {-----------------------------------------------------------------------------------------} FUNCTION Dicho_Rec (debut, fin, V : Integer ; T : Tab) : Boolean ; VAR milieu : Integer ; BEGIN

milieu := (debut + fin) DIV 2 ; If (V = T[milieu]) Then Dicho_Rec := True Else If (V < T[milieu] ) AND (debut < milieu)

Then Dicho_Rec := Dicho_Rec (debut, milieu-1, V, T) Else If (V > T[milieu] ) And (fin > milieu)

Then Dicho_Rec := Dicho_Rec (milieu +1, fin, V, T) Else Dicho_Rec := False

END ; {================= P P ===================================} BEGIN Saisie (n) ; Remplir_Trier (n, T) ;

Write ('Donner un entier : ') ; ReadLn (V) ; existe := Dicho_Rec (1, n, V, T) ; If existe Then WriteLn (V, ' existe dans le tableau T.')

Else WriteLn (V, ' n''existe pas dans le tableau T.') ; END.



CHAPITRE 3

LES ALGORITHMES DE TRI I/ Introduction Selon le dictionnaire "trier" signifie «répartir des objets suivant certains critères». En informatique le "tri" un processus de classement d'une suite d'éléments dans un ordre donné. Il existe deux catégories de tris : - Les tris internes : Méthodes destinées à des masses de données limitées, stockées dans une structure de données se trouvant dans la mémoire centrale (Exemple : tableaux). - Les tris externes : Méthodes destinées à de grandes masses de données, stockées dans des structures de données comme par exemple les fichiers. I/ Tri par sélection Activité Ecrire un programme nommé Tri_Sélection, qui remplit de façon aléatoire un tableau T par N Réels. Affiche l'état actuel du tableau puis celui du tableau trié par ordre croissant en utilisant la méthode du tri par sélection. N est entier compris entre 4 et 25.

* - * - * - * - * - * - * - * - * - * - *

Analyse du programme Tri_Sélection Résultat = Tableau trié Traitement : - Une procédure Affiche_Tab, permet d'afficher le contenu du tableau. Elle va servir pour l'affichage du tableau non trié puis pour le tableau trié. - Une procédure Tri_Sélect, permet le tri par sélection du tableau. - Une procédure Saisie, permet la saisie et le test de N. - Une procédure Remplir_Hasard, permet de remplir de façon aléatoire (au hasard) le tableau. Fin Analyse Algorithme 0) Début Tri_Sélection 1) Proc Saisie (N) 2) Proc Remplir_Hasard (T, N) 3) Ecrire ("Tableau non trié ") 4) Proc Affiche_Tab (T, N)



5) Proc Tri_Select (T, N) 6 ) Ecrire ("Tableau trié ") 7) Proc Affiche_Tab (T, N) 8) Fin Tri_Sélection Tableau de déclaration des objets globaux

Objet Type / Nature Rôle N T Saisie Remplir_Hasard Affiche_Tab Tri_Sélect

Entier Tab Procédure Procédure Procédure Procédure

Nombre d'éléments du tableau Tableau des réels Saisie et test de N Remplit au hasard le tableau T Affiche le contenu du tableau Tri le tableau par sélection

Tableau de déclaration des nouveaux types

Types TAB = Tableau de 25 réels Analyse de la procédure Saisie Résultat = Saisie et test de N Traitement Répéter N = Donnée ("Entrer la taille du tableau : ") Jusqu'à (4 ≤ N ≤ 25) Fin Saisie Algorithme 0) Procédure Saisie (VAR N : Entier) 1) Répéter Ecrire ("Entrer la taille du tableau : ") Lire (N) Jusqu'à (4 ≤ N ≤ 25) 2) Fin Saisie Analyse de la procédure Remplir_Hasard Résultat = Remplir le tableau T par des réel pris au hasard Traitement : - La fonction prédéfinie Hasard (N ) en Pascal Random (N), renvoie un entier aléatoire compris entre 0 et N-1. Si N est omis, la fonction renvoie un réel compris entre 0 et 9.999…. Donc pour obtenir un réel, par exemple entre 0 et 100, on multiplie le résultat de Hasard par 100.



Pour i de 1 à N Faire T[i] Hasard * 100

Fin Pour En Pascal, pour que cette fonction génère à chaque appel des nombres différents, elle doit être initialisée avec la procédure prédéfinie Randomize. Fin Analyse Algorithme 0) Procédure Remplir_Hasard (VAR T : Vect ; N : Entier ) 1) Randomize 2) Pour i de 1 à N Faire

T[i] Hasard * 100 Fin Pour 3) Fin Remplir_Hasard Tableau de déclaration des objets locaux

Objet Type / Nature Rôle i Entier Compteur Analyse de la procédure Tri_Select Résultat = Tableau T trié Traitement : Lorsque le tri est par ordre croissant, la méthode est parfois appelée tri par recherche de minima, car on commence par le plus petit élément. Lorsque le tri est par ordre décroissant, la méthode appelée tri par recherche de maxima, car on commence par le plus grand. Dans notre cas c'est un tri décroissant, donc c'est une sélection par par recherche de minima. La méthode de tri par sélection est donc la suivante : 1- On cherche le plus petit élément en parcourant tout le tableau et on le permute avec celui occupant la première case. 2- La plus petite valeur occupe définitivement sa place qui est la première case. On cherche maintenant la plus petite valeur dans le tableau T mais on commençant à partir du deuxième élément. Si elle existe elle sera permuter avec c'elle de la deuxième case. 3- On répète le même traitement à partie de la troisième case et ainsi de suite jusqu'à la case N-1. - La recherche de la position de la plus petite valeur à partir d'un point de départ donné est confiée à une fonction nommé Cherche_Min. - La permutation du contenu de deux cases du tableau est faite par une procédure nommé Permute. Fin Analyse



Algorithme 0) Procédure Tri_Select (VAR T : Vect ; N : Entier ) 1) Pour i de 1 à N-1 Faire Pos_Min Fn Cherche_Min (T, i, N) Si Pos_Min ≠ i Alors Proc Permute (T[i] , T[Pos_Min]) Fin Si Fin Pour 2) Fin tri_Select Tableau de déclaration des objets locaux

Objet Type / Nature Rôle i Pos_Min Cherche_Min Permute

Entier Entier Fonction Procédure

Compteur Position de la valeur minimale Retourne la position de la valeur minimale Permute le contenu de deux variables

Analyse de la fonction Cherche_Min Résultat = Cherche_Min Traitement : - On suppose que l'élément de départ est le plus petit donc sa position est son indice. Min T[départ] Indice Départ - On parcourt le tableau à partir de la position départ + 1 jusqu'à N à la recherche d'un élément plus petit, s'il existe, on mémorise sa valeur et sa position. Pour j de départ + 1 à N Faire Si T[j] < Min Alors Min T[j] indice j Fin Si Fin Pour

- Le résultat est la valeur indice Cherche_Min indice Fin Analyse Algorithme 0) Fonction Cherche_Min (T : Vect ; départ, N : Entier ) : Entier 1) Min T[départ] 2) Indice Départ 3) Pour j de départ + 1 à N Faire Si T[j] < Min Alors Min T[j] indice j Fin Si Fin Pour 4) Cherche_Min indice 5) Fin Cherche_Min



Tableau de déclaration des objets locaux

Objet Type / Nature Rôle j Min indice

Entier Réel Entier

Compteur Valeur minimale Position de la valeur minimale

Analyse de la procédure Permute Résultat = Permuter le contenu de deux variables Traitement : - Pour permuter le contenu de deux variables, nous allons utiliser une troisième pour la sauvegarde temporaire d'une des deux valeurs. temp a a b b temp Fin Anlyse Algorithme 0) Procédure Permute (VAR a, b : Réel) 1) temp a a b b temp 2) Fin Permute Tableau de déclaration des objets locaux

Objet Type / Nature Rôle temp Réel Variable temporaire pour la permutation Analyse de la procédure Affiche_Tab Résultat = Afficher le contenu du tableau T. Traitement : - Parcourir le tableau et afficher tous ses éléments à l'aide d'une itération complète. Pour i de 1 à N Faire Ecrite (T[i]) Fin Pour Fin Analyse Algorithme 0) Procédure Affiche_Tab (T : Vect ; N : Entier)



1) Pour i de 1 à N Faire Ecrite (T[i]) Fin Pour 2) Fin Affiche_Tab Tableau de déclaration des objets locaux

Objet Type / Nature Rôle i Entier Compteur Programme en Pascal PROGRAM Tri_Selection ; USES Crt ; TYPE Vect = ARRAY [1 .. 25 ] Of Real ; VAR N : Integer ; T : Vect ; {----------------------------------------------------------------------------------------} PROCEDURE Saisie (VAR N : Integer ); BEGIN

Repeat Write ('Entrer la taille du tableau : ') ;

ReadLn (N) ; Until N In [4 .. 25 ] ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Remplir_Hasard (VAR T : Vect ; N : Integer ) ; VAR i : Integer ; BEGIN Randomize ; For i := 1 To N Do T[i] := Random * 100 ; END ; {----------------------------------------------------------------------------------------} FUNCTION Cherche_Min (T : Vect ; depart, N : Integer) : Integer ; VAR j, indice : Integer ; Min : Real ; BEGIN



Min := T[depart] ; Indice := depart ; For j := depart + 1 To N Do

Begin If (T[j] < Min) Then Begin

Min := T[j] ; indice := j ; End ; End ; Cherche_Min := indice ; End ; {----------------------------------------------------------------------------------------} PROCEDURE Permute (VAR a, b : Real ) ; VAR Temp : Real ; BEGIN temp := a ;

a := b ; b := temp ;

END ; {----------------------------------------------------------------------------------------} PROCEDURE Tri_Select (VAR T : Vect ; N : Integer ) ; VAR i, Pos_Min : Integer ; BEGIN For i := 1 To N-1 Do Begin Pos_Min := Cherche_Min (T, i, N) ; If Pos_Min i Then Permute (T[i] , T[Pos_Min]) ; End ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Affiche_Tab (T : Vect ; N : Integer) ; VAR i : Integer ; BEGIN

For i := 1 To N Do WriteLn (T[i] : 8 : 3) ; END ; {= = = = = = = = = = = = = = = = = = P P = = = = = = = = = = = = = = = = = = = = = = } BEGIN Saisie (N) ; Remplir_Hasard (T, N) ;



WriteLn ('Tableau non trié '); Affiche_Tab (T, N) ;

Tri_Select (T, N) ;

WriteLn ('Tableau trié " ); Affiche_Tab (T, N) ; END. II/ Tri à bulles Activité Ecrire un programme nommé Tri_Bulles, qui permet le tri d'un tableau T de N réels, par la méthode du tri à bulles. Ce programme affiche le contenu du tableau non trié puis le contenu du tableau trié par ordre décroissant. N est entier compris entre 4 et 25. Le tableau est remplit de façon aléatoire un tableau T par N Réels.

* - * - * - * - * - * - * - * - * - * - *

Analyse du programme Tri_Bulles Résultat = Tableau trié Traitement : - Les procédures de saisie de N, du remplissage du tableau et de l'affichage sont les mêmes que ceux de l'activité précédente. - Une procédure nommée Bulles, permet le tri du tableau par une des méthodes du tri à bulles. Fin Analyse Algorithme 0) Début Tri_Bulles 1) Proc Saisie (N) 2) Proc Remplir_Hasard (T, N) 3) Ecrire ("Tableau non trié ") 4) Proc Affiche_Tab (T, N) 5) Proc Bulles (T, N) 6 ) Ecrire ("Tableau trié ") 7) Proc Affiche_Tab (T, N) 8) Fin Tri_Sélection Analyse de la procédure Bulles



Il existe plusieurs méthodes du tri à bulles, en voici une : L'algorithme du tri à bulles (bubble sort en anglais) consiste à comparer les différentes valeurs adjacentes du tableau T, et à les permuter s'ils ne sont pas dans le bon ordre.

Pour i de 1 à N-1 Faire Si (T[i] > T[i+1]) Alors Proc Permuter (T[i], T[i+1]) Si au moins une permutation est faite, une variable booléenne (échange) reçoit par exemple Vrai, si elle a été initialisée au départ à Faux échange Vrai Le tri se termine quand il n'y a plus de permutations (échange = faux) sinon on répète le même traitement. Jusqu'à échange = Faux Fin Analyse Algorithme 0) Procédure Bulles (VAR T : Vect ; N : Entier) 1) Répéter échange Faux

Pour i de 1 à N-1 Faire Si (T[i] > T[i +1] ) Alors Proc Permute (T[i], T[i+1]) échange Vrai Fin Si Fin Pour Jusqu'à échange = Faux 2) Fin Bulles Tableau de déclaration des objets locaux

Objet Type / Nature Rôle i échange Permuter

Entier Booléen Procédure

Compteur Drapeau de test Permute le contenu de deux variables

Programme complet en Pascal PROGRAM Tri_Bulles ; USES Crt ; TYPE Vect = ARRAY [1 .. 25 ] Of Real ; VAR N : Integer ; T : Vect ;



{----------------------------------------------------------------------------------------} PROCEDURE Saisie (VAR N : Integer ); BEGIN


ReadLn (N) ; Until N In [4 .. 25 ] ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Remplir_Hasard (VAR T : Vect ; N : Integer ) ; VAR i : Integer ; BEGIN Randomize ; For i := 1 To N Do T[i] := Random * 100 ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Permute (VAR a, b : Real ) ; VAR Temp : Real ; BEGIN temp := a ;

a := b ; b := temp ;

END ; {----------------------------------------------------------------------------------------} PROCEDURE Bulles (VAR T : Vect ; N : Integer ) ; VAR i : Integer ; echange : Boolean ; BEGIN

Repeat echange := False ;

For i := 1 To N-1 Do If (T[i] > T[i +1] ) Then

Begin Permute (T[i], T[i+1]) ;

echange := True ; End ; Until (echange = False); END ;



{----------------------------------------------------------------------------------------} PROCEDURE Affiche_Tab (T : Vect ; N : Integer) ; VAR i : Integer ; BEGIN

For i := 1 To N Do WriteLn (T[i] : 8 : 3) ; END ; {= = = = = = = = = = = = = = = = = = P P = = = = = = = = = = = = = = = = = = = = = = } BEGIN Saisie (N) ; Remplir_Hasard (T, N) ; WriteLn ('Tableau non trié ');

Affiche_Tab (T, N) ;

Bulles (T, N) ; WriteLn ('Tableau trié '); Affiche_Tab (T, N) ; END. III/ Tri par insertion Activité Ecrire un programme nommé Tri_Insertion, qui permet le tri d'un tableau T de N réels, par la méthode du tri par insertion. Ce programme affiche le contenu du tableau non trié puis le contenu du tableau trié par ordre décroissant. N est entier compris entre 4 et 25. Le tableau est remplit de façon aléatoire un tableau T par N Réels.

* - * - * - * - * - * - * - * - * - * - * Analyse du programme Tri_Insertion Résultat = Tableau trié Traitement : - Les procédures de saisie de N, du remplissage du tableau et de l'affichage sont les mêmes que ceux de l'activité précédente. - Une procédure nommée T_Insertion, permet le tri du tableau par la méthode du tri par insertion. Fin Analyse Algorithme 0) Début Tri_Insertion 1) Proc Saisie (N)



2) Proc Remplir_Hasard (T, N) 3) Ecrire ("Tableau non trié ") 4) Proc Affiche_Tab (T, N) 5) Proc T_Insertion (T, N) 6 ) Ecrire ("Tableau trié ") 7) Proc Affiche_Tab (T, N) 8) Fin Tri_Insertion Analyse de la procédure T_Insertion Le principe du tri par insertion, est identique au classement qu'un joueur de "rami" ou de "belote" utilise pour ranger ses cartes. Il tire une carte et la met à sa place parmi les autres cartes déjà rangées puis il recommence avec la carte suivante jusqu'au rangement de toutes les certes dans sa main. Le principe global est d'insérer ième élément à sa bonne place dans la liste formée par les (i-1) éléments qui le précèdent e qui sont déjà triés. Cette action est répétée jusqu'au dernier élément (le Nième). Pour i de 2 à N Faire L'itération commence à partir de 2, car on considère que le premier élément est trié et qu'il occupe sa place. Le processus d'insertion consiste à : - Utiliser une variable intermédiaire tmp pour conserver la valeur à insérer, - Déplacer les éléments T[i-1], T[i-2], ... vers la droite tant que leur valeur est supérieure à celle de tmp. - Affecter alors à l'emplacement laissé libre par ce décalage la valeur de tmp.

Tmp T[i] j i

Proc Décaler (T, j, Tmp) T[j] Tmp

Fin Analyse Algorithme 0) Procédure T_Insertion (VAR T : Vect ; N : Entier) 1) Pour i de 2 à N Faire

Tmp T[i] j i Proc Décaler (T, j, Tmp)

T[j] Tmp Fin Pour 2) Fin T_Insertion Tableau de déclaration des objets locaux

Objet Type / Nature Rôle i Entier Compteur



Tmp j Décaler

Réel Entier Procédure

Variable intermédiaire Position d’insertion Permettant de décaler des éléments d’un tableau d’un certain nombre de positions

Analyse de la procédure Décaler Résultat : Décaler à droite les éléments du tableau T d'indice début à l’indice fin Traitement : Il s'agit d'un traitement répétitif à condition d'arrêt réalisant le décalage : Tant Que T[p -1] > Temporaire Faire T[p] T[p-1] p p -1 Fin Tant Que - L'action de décalage est une simple affectation : T[p] T[p-1]

Puis La décrémentation de 1 de la variable p Fin analyse Algorithme 0) Procédure Décaler (VAR T : Vect; VAR p : Entier ; temporaire : Réel) 1) Tant que (T[p -1] > Temporaire) Faire T[p] T[p-1] p p -1 Fin tant que 2) Fin Décaler Programme complet en Pascal PROGRAM Tri_Insertion ; USES Crt ; TYPE Vect = ARRAY [1 .. 25 ] Of Real ; VAR N : Integer ; T : Vect ; {----------------------------------------------------------------------------------------} PROCEDURE Saisie (VAR N : Integer ); BEGIN




ReadLn (N) ; Until N In [4 .. 25 ] ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Remplir_Hasard (VAR T : Vect ; N : Integer ) ; VAR i : Integer ; BEGIN Randomize ; For i := 1 To N Do T[i] := Random * 100 ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Decaler (VAR T : Vect; VAR p : Integer ; temporaire : Integer) ; BEGIN

While T[p -1] > Temporaire Do Begin

T[p] := T[p-1] ; p := p -1 ; End ; END ; {----------------------------------------------------------------------------------------} PROCEDURE T_Insertion (VAR T : Vect ; N : Integer) ; VAR i, j: Integer ; tmp : Real ; BEGIN

For i:= 2 To N Do Begin

Tmp := T[i] ; j := i ; Decaler (T, j, Tmp) ;

T[j] := Tmp ; End ;

END ; {----------------------------------------------------------------------------------------} PROCEDURE Affiche_Tab (T : Vect ; N : Integer) ; VAR i : Integer ; BEGIN

For i := 1 To N Do WriteLn (T[i] : 8 : 3) ; END ;



{= = = = = = = = = = = = = = = = = = P P = = = = = = = = = = = = = = = = = = = = = = } BEGIN Saisie (N) ; Remplir_Hasard (T, N) ; WriteLn ('Tableau non trié ');


T_Insertion (T, N) ; WriteLn ('Tableau trié ' ); Affiche_Tab (T, N) ; END. IV/ Tri Shell En analysant l'algorithme du tri par insertion, nous pouvons remarquer qu'il fait n*(n-1) comparaisons et décalages. Il est toutefois évident que si le vecteur est initialement presque trié dans le bon ordre, le nombre d'opérations sera beaucoup plus réduit. Si la méthode de tri par insertion est efficace quand la liste est à peu près triée, elle est inefficace en moyenne car elle ne change les valeurs que d'une position par instruction. En effet, cette méthode traite un à un les éléments de la liste à trier et réalise un décalage des éléments précédents jusqu'à avoir la position d'insertion de l'élément en cours. Principe du tri Shell Donald L. Shell proposa, en 1959, une variante du tri par insertion. Ce tri consiste à trier séparément des sous tableaux du tableau initial, formés par les éléments répartis en un nombre P calculé d'éléments. Le tri Shell est donc une amélioration du tri par insertion. Au lieu de faire un décalage de tous les éléments, il fera un décalage par pas de P éléments, ce qui permet d'affiner le tri du tableau et de faire moins de déplacements d'éléments. Le tri Shell commence par un pas assez élevé et il le diminue au fur et à mesure jusqu'à arriver à un pas de 1. Ceci permet de réduire le désordre donc de diminuer le travail aux étapes suivantes. Le pas est diminué à l'aide d'une suite calculée. Shell propose la suite d'incréments vérifiant P1 = 1, Pn+1 = 3Pn+1 en réalisant les tris du plus grand incrément possible vers le plus petit. Au dernier stade, P0 est égal à 1 (retour au tri par insertion normal). Nous déterminerons le pas maximal par récurrence en inversant la relation donnée ci-dessus :

Pk + 1 = 3 * Pk + 1



et en s'assurant qu'il y a encore un nombre suffisant de composantes dans les sous tableaux considérés. Conclusion : Le tri Shell trie chaque liste d'éléments séparés de P positions chacun avec le tri par insertion. L'algorithme effectue plusieurs fois cette opération en diminuant le pas P jusqu'à un pas égal à 1 ce qui équivaut à trier tous les éléments ensemble (tri par insertion normal). Activité Ecrire un programme nommé Tri_Shell, qui permet le tri d'un tableau T de N réels, par la méthode du tri Shell. Comme dans les activités précédentes, ce programme : - affiche le contenu du tableau non trié puis le contenu du tableau trié par ordre décroissant. - Lit un entier N compris entre 4 et 25. - Le tableau est remplit de façon aléatoire par N Réels.

* - * - * - * - * - * - * - * - * - * - *

Analyse du programme Tri_Shell Résultat = Tableau trié Traitement : - Les procédures de saisie de N, du remplissage du tableau et de l'affichage sont les mêmes que ceux des activités de tri précédentes. - Une procédure nommée Shell, permet le tri du tableau par la méthode du tri Shell. Fin Analyse Algorithme 0) Début Tri_Shell 1) Proc Saisie (N) 2) Proc Remplir_Hasard (T, N) 3) Ecrire ("Tableau non trié ") 4) Proc Affiche_Tab (T, N) 5) Proc Shell (T, N) 6 ) Ecrire ("Tableau trié ") 7) Proc Affiche_Tab (T, N) 8) Fin Tri_Shell Analyse de la procédure Shell Résultat = Tableau T trié Traitement : C’est trier séparément des sous tableaux du tableau initial dont les éléments sont distants de P cases par la méthode du tri par insertion.



Pour chaque valeur du pas (P) calculé, on utilise un traitement répétitif à condition d’arrêt appliqué à chacun des sous tableaux. P 1 Tant Que (P< N) Faire

P (3* P +1) Pour i de P +1 à NFaire

Si T[i] n’est pas à sa place alors on réalise les actions suivantes : - Ranger la valeur de T[i] dans la variable TMP - Décaler vers la droite par un pas = P les valeurs de T[i - P], T[i-2* P], ...

Jusqu’à arriver à une valeur qui est inférieure à T[i]. - Affecter au dernier élément décalé la valeur de TMP

Pour avoir la valeur maximale du pas, on utilise une boucle à condition d’arrêt : P 1 Tant Que (P< N) Faire P (3* P +1) Fin Tant Que

Algorithme Nous allons écrire côte à côte les deux tris. Le tri par insertion normal, c'est-à-dire avec un pas = 1 et le tri Shell qui applique un pas P à ce même tri. Tri par insertion normal Tri Shell 0) Procédure Tri_insertion (N: Entier; VAR T : Vect) 1) Pour c de 2 à N Faire Si (T[c] < T[c-1]) Alors

Tmp T[c] pos c

Tant que (pos >1) ET (T[pos-1]> tmp) Faire

T[pos] T[pos-1] pos pos-1

Fin Tant que T[pos] Tmp

Fin Si Fin Pour

2) Fin Tri_insertion

0) Procédure Shell (N : entier; VAR T : Vect) 1) P 1 Tant Que (P< N) Faire P (3* P +1) Fin Tant Que 2) Tant Que (P ≠1) Faire

P P DIV 3 Pour c de P + 1 à N Faire Si (T[c] < T[c-p]) Alors

Tmp T[c] pos c

Tant Que (pos > P-1) et (T[pos-P]> tmp) Faire

T[pos] T[pos-P] pos pos-P

Fin Tant que T[pos] Tmp

Fin Si Fin Pour Fin Tant Que 3) Fin Shell



Programme complet en Pascal PROGRAM Tri_Shell ; USES Crt ; TYPE Vect = ARRAY [1 .. 25 ] Of Real ; VAR N : Integer ; T : Vect ; {----------------------------------------------------------------------------------------} PROCEDURE Saisie (VAR N : Integer ); BEGIN


ReadLn (N) ; Until N In [4 .. 25 ] ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Remplir_Hasard (VAR T : Vect ; N : Integer ) ; VAR i : Integer ; BEGIN Randomize ; For i := 1 To N Do T[i] := Random * 100 ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Shell (VAR T : Vect ; N : Integer) ; VAR P, c, pos : Integer ; Tmp : Real ; BEGIN P := 1 ; While ( P < N) Do Begin p := (3* P +1) ;



End ; While (P < > 1) Do Begin P := P DIV 3 ;

For c := P + 1 To N Do Begin If (T[c] < T[c-p]) Then

Begin Tmp := T[c] ; pos := c ;

While (pos > P-1) AND (T[pos-P]> tmp) Do Begin

T[pos] := T[pos-P] ; pos := pos-P ;

End ; {End While } T[pos] := Tmp ;

End ; {End If } End ; {End For} End ; {End While } END ; {----------------------------------------------------------------------------------------} PROCEDURE Affiche_Tab (T : Vect ; N : Integer) ; VAR i : Integer ; BEGIN

For i := 1 To N Do WriteLn (T[i] : 8 : 3) ; END ; {= = = = = = = = = = = = = = = = = = P P = = = = = = = = = = = = = = = = = = == = } BEGIN Saisie (N) ; Remplir_Hasard (T, N) ; WriteLn ('Tableau non trié ');


Shell (T, N) ; WriteLn ('Tableau trié '); Affiche_Tab (T, N) ; END. V/ Tri par fusion



Principe Le tri fusion est construit suivant la stratégie "diviser pour régner". Le principe de base est que pour résoudre un gros problème, il est souvent plus facile de le diviser en petits problèmes élémentaires. Une fois chaque petit problème résolu, il n'y a plus qu'à combiner les différentes solutions pour résoudre le problème global. La méthode "diviser pour régner" est tout à fait applicable au problème de tri : plutôt que de trier le tableau complet, il est préférable de trier deux sous tableaux de taille égale, puis de fusionner les résultats. Un algorithme récursif est très pratique. En effet, les deux sous tableaux seront eux même triés à l'aide de même algorithme de tri fusion. Un tableau ne comportant qu'un seul élément sera considéré comme trié : c'est la condition de fin du tri (arrêt). Etapes de l'algorithme : - Division de l'ensemble de valeurs en deux parties - Tri de chacun des deux ensembles - Fusion des deux ensembles obtenus pour reconstituer le tableau trié. Remarque : Nous constatons que la méthode de tri par fusion nécessite un tableau intermédiaire aussi grand que le tableau initial à trier et c'est là où réside le principal inconvénient. Exemple Soit le tableau T Suivant :

T 12 3 0 15 -5 22 23 -7 10 8 8 12 34 35 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

On peut diviser ce tableau en deux sous tableaux d'entiers T1 et T2 de longueurs respectives 7 et 8. T1 12 3 0 15 -5 22 23 T2 -7 10 8 8 12 34 35 3 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 Triés par ordre croissant les deux sous tableaux T1 et T2 T1 -5 0 3 12 15 22 23 T2 -7 3 8 8 10 12 34 35 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 On propose d'utiliser la méthode de tri par fusion pour fusionner T1 et T2. Le résultat sera rangé dans le tableau T. Etape 1 On commence par : - comparer le premier élément de chacun des deux tableaux T1 et T2

Le plus petit est T2 [1] = -7 - placer -7 dans T [1] et se pointer à l'élément n°2 de T2



- se pointer à l'élément n°2 de T - Remarquez que nous sommes toujours à la première position de T1. T -7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Etape 2 - comparer le premier élément de T1 et le deuxième élément de T2

Le plus petit est T1 [1] = -5 - placer -5 dans T [2] et se pointer à l'élément n°2 de T1 - se pointer à l'élément n°3 de T T -7 -5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Etape 3 - comparer T1 [2] et T2 [2] Le plus petit est T1 [2] = 0 - placer 0 dans T [3] et se pointer à l'élément n°3 de T1 - se pointer à l'élément n°4 de T T -7 -5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

- On poursuit la fusion de cette façon jusqu'à la fin de l'un des deux tableaux. T -7 -5 0 3 3 8 8 10 12 12 15 22 23 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Tous les éléments du tableau T1 ont été rangés dans le tableau T, il ne reste que des éléments dans le tableau T2. Ces éléments vont être transférés directement dans le tableau T. T -7 -5 0 3 3 8 8 10 12 12 15 22 23 34 35 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Activité On propose d'écrire un programme qui réalise la méthode de tri décrite précédemment (diviser le tableau uniquement en 2 sous tableaux, sans appliquer la méthode complète du tri par fusion, c'est-à-dire sans les divisions jusqu'à un tableau à 1 seul élément). - La saisie de N, le remplissage du tableau et l'affichage sont les mêmes que les activités précédentes.

* - * - * - * - * - * - * - * - * - * - * Analyse du programme Tri_Fus1



Résultat = Tableau trié Traitement : - Les procédures de saisie de N, du remplissage du tableau et de l'affichage sont les mêmes que ceux des activités de tri précédentes. - Une procédure nommée Fus, permet le tri du tableau par la méthode décrite. Fin Analyse Algorithme 0) Début Tri_Fus1 1) Proc Saisie (N) 2) Proc Remplir_Hasard (T, N) 3) Ecrire ("Tableau non trié ") 4) Proc Affiche_Tab (T, N) 5) Proc Fus (T, N) 6 ) Ecrire ("Tableau trié ") 7) Proc Affiche_Tab (T, N) 8) Fin Tri_Fus1 Analyse de la procédure Fus Résultat = Tableau T trié Traitement : - Fusionner deux sous tableaux triés dans le tableau T, c'est le rôle de la procédure Fusionner. - Trier successivement les deux sous tableaux, c'est le rôle de la procédure Trier. - Diviser le tableau T en deux sous tableaux, c'est le rôle de la procédure Diviser. Fin Analyse Algorithme 0) Procédure Fus (VAR T : Vect; N : Entier) 1) Proc Diviser (T, N, T1, T2, N1, N2) 2) Proc Trier (T1, N1) 3) Proc Trier (T2, N2) 3) Proc Fusionner (T, N, T1, T2, N1, N2) 4) Fin Fus Tableau de déclaration des objets locaux

Objet Type / Nature Rôle Diviser Trier Fusionner

Procédure Procédure Procédure

Diviser le tableau T en deux sous tableaux Trier un tableau Fusionner deux sous tableaux triés

Analyse de la procédure Diviser Résultat = Diviser le tableau T en 2 sous tableaux Traitement : - Calculer les tailles des sous tableaux



N1 N DIV 2 N2 N - N1 - Diviser le tableau en deux sous tableaux presque égaux. Pour i de 1 à N1 Faire T1[i] T[i] Fin Pour Pour i de 1à N2 Faire T2[i] T1[N1 + i] Fin Pour Fin Analyse Algorithme 0) Procédure Diviser (T : Vect ; N : Entier, VAR T1, T2 : Vect2 ; VAR N1, N2 : Entier) 1) N1 N DIV 2 2) N2 N - N1 3) Pour i de 1 à N1 Faire T1[i] T[i] Fin Pour 4) Pour i de 1à N2 Faire

T2[i] T1[N1 + i] Fin Pour 5) Fin Diviser Tableau de déclaration des objets locaux

Objet Type / Nature Rôle i Entier Compteur Analyse de la procédure Trier Résultat = Tableau trié Traitement : - Pour i de 1 à taille-1 Faire Pour j de i+1 à taille Faire Si Tx[i] > Tx[j] Alors aux Tx[i] Tx[i] Tx[j] Tx[j] aux Fin Si Fin Pour Fin Analyse Algorithme 0) Procédure Trier (VAR Tx : Vect2 ; taille : Entier) 1) Pour i de 1 à taille-1 Faire



Pour j de i+1 à taille Faire Si Tx[i] > Tx[j] Alors aux Tx[i] Tx[i] Tx[j] Tx[j] aux Fin Si Fin Pour 2) Fin Trier Tableau de déclaration des objets locaux

Objet Type / Nature Rôle i, j aux

Entier Réel

Compteurs Variable auxiliaire

Analyse de la procédure Fusionner Résultat = Trier en fusionnant les deux tableaux T1 et T2 Traitement : - Ranger les éléments des tableaux T1 et T2 jusqu'à la fin de l'un des tableaux T1 ou T2. c 0

c1 1 c2 1

Répéter Inc (c, 1) Si (T1 [c1] < T2 [c2])

Alors T[c] ¨ T1 [c1] Inc (c1, 1) Sinon T[c] T2 [c2] Inc (c2, 1) Fin Si Jusqu'à (c1 > N1) OU (c2 > N2) - Ranger le reste des éléments du tableau T1 ou T2 (il s'agit d'une action de copie)

Si (c1 > n1) Alors {tous les éléments de T1 ont été rangés dans T, il reste à copier les éléments de T2}

Pour i de c2 à N2 Faire T[c] T2[i] Inc (c, 1) Fin Pour Sinon {copier le reste des éléments de T2} Pour i de c1 à N1 Faire T[c] T1[i] Inc (c, 1) Fin Pour

Fin Si Fin Analyse



Algorithme 0) Procédure Fusionner (VAR T : Vect ; N : Entier ; T1, T2 : Vect2 ; N1, N2 : Entier) 1) c 0 2) c1 1 3) c2 1 4) Répéter Inc (c, 1) Si (T1 [c1] < T2 [c2])

Alors T[c] T1 [c1] Inc (c1, 1) Sinon T[c] T2 [c2] Inc (c2, 1) Fin Si Jusqu'à (c1 > N1) OU (c2 > N2) 5) Si (c1 > N1) Alors Pour i de c2 à N2 Faire

T[c] T2[i] Inc (c, 1)

Fin Pour Sinon Pour i de c1 à N1 Faire

T[c] T1[i] Inc (c, 1)

Fin Pour Fin Si

6) Fin Fusionner Tableau de déclaration des objets locaux

Objet Type / Nature Rôle c, c1, c2 Entier Compteurs Programme complet en Pascal PROGRAM Tri_Fusion_Simple ; USES Crt ; TYPE Vect = ARRAY [1 .. 25 ] Of Real ; Vect2 = ARRAY [1.. (25 DIV 2) +1] Of Real ; VAR N, N1, N2 : Integer ;



T : Vect ; T1, T2 : Vect2; {----------------------------------------------------------------------------------------} PROCEDURE Saisie (VAR N : Integer ); BEGIN


ReadLn (N) ; Until N In [4 .. 25 ] ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Remplir_Hasard (VAR T : Vect ; N : Integer ) ; VAR i : Integer ; BEGIN Randomize ; For i := 1 To N Do T[i] := Random * 100 ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Diviser (T : Vect ; N : Integer ; VAR T1, T2 : Vect2 ; VAR N1, N2 : Integer) ; VAR i : Integer ; BEGIN

N1 := N DIV 2 ; N2 := N - N1 ; For i := 1 TO N1 Do

T1[i] := T[i] ; For i := 1 TO N2 Do

T2[i] := T[N1 + i] ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Fusionner (VAR T : Vect ; N : Integer ; T1, T2 : Vect2 ; N1, N2 : Integer) ; VAR c, c1, c2, i : Integer ; BEGIN

c := 0 ; c1 := 1; c2 := 1 ; Repeat

If (T1 [c1] < T2 [c2]) Then Begin T[c] := T1 [c1] ; Inc (c1, 1) ;



End Else Begin T[c] := T2 [c2] ; Inc (c2, 1) ; End ; Inc (c, 1) ;

Until (c1 > N1) OR (c2 > N2) ; If (c1 > N1) Then

For i := c2 TO N2 Do Begin

T[c] := T2[i] ; Inc (c, 1) ;

End Else For i := c1 TO N1 Do Begin

T[c] := T1[i] ; Inc (c, 1) ;

End ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Trier (VAR Tx : Vect2 ; taille : Integer ) ; VAR i, j : Integer ; Aux : Real ; BEGIN

For i := 1 TO taille-1 Do For j := i+1 TO taille Do If (Tx[i] > Tx[j]) Then Begin

aux := Tx[i] ; Tx[i] := Tx[j] ; Tx[j] := aux ; End ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Fus (VAR T : Vect; N : Integer) ; BEGIN

Diviser (T, N, T1, T2, N1, N2) ; Trier (T1, N1) ; Trier (T2, N2) ; Fusionner (T, N, T1, T2, N1, N2) ;

END ; {----------------------------------------------------------------------------------------} PROCEDURE Affiche_Tab (T : Vect ; N : Integer) ; VAR i : Integer ;



BEGIN For i := 1 To N Do

WriteLn (T[i] : 8 : 3) ; END ; {= = = = = = = = = = = = = = = = = = P P = = = = = = = = = = = = = = = = = = == = } BEGIN Saisie (N) ; Remplir_Hasard (T, N) ; WriteLn ('Tableau non trié ');


Fus (T, N) ; WriteLn ('Tableau trié ' ); Affiche_Tab (T, N) ; END. Application : Reprendre le programme précédent et remplacer la procédure de tri classique par une procédure de tri_fusion selon le principe "diviser pour régner". Cette procédure fait appel à la procédure fusion. PROGRAM Tri_Fusion2 ; USES WinCrt ; TYPE Tab = ARRAY [1 .. 25 ] Of Real ; VAR N, N1, N2 : Integer ; T : Tab ; {----------------------------------------------------------------------------------------} PROCEDURE Saisie (VAR N : Integer ); BEGIN


ReadLn (N) ; Until N In [4 .. 25 ] ; END ; {----------------------------------------------------------------------------------------} PROCEDURE Remplir_Hasard (VAR T : Tab ; N : Integer ) ; VAR i : Integer ;



BEGIN Randomize ; For i := 1 To N Do T[i] := Random * 100 ; END ; {---- fusionner t[debut..milieu] et t[milieu +1..fi] ---------} PROCEDURE fusion (VAR T : Tab ; debut, milieu, fin: Integer); VAR

aux : Tab; i, j, k, l, taille : Integer;

BEGIN i := debut; j := milieu+1; taille := fin - debut +1; For k:=1 To taille Do Begin If ((j > fin) OR (I < = milieu) AND (t[i] < t[j])) Then Begin

aux[k] := t[i] ; i := i +1;

End Else Begin

aux[k] := t[j] ; j := j +1; End;

End;

{Recopier aux dans T} l := 1; For k := debut To fin Do Begin

t[k] := aux[l]; l := l +1;

End; END; PROCEDURE tri_fusion (VAR T : Tab ; N : Integer); VAR

debut, fin, i, milieu : Integer; BEGIN

i := 1; While (i



While (debut + i-1 N) Then fin := N; Fusion (t, debut, debut + i-1, fin);

debut := debut + i + i; End; I := i+1; End; END; {----------------------------------------------------------------------------------------} PROCEDURE Affiche_Tab (T : Tab ; N : Integer) ; VAR i : Integer ; BEGIN

For i := 1 To N Do WriteLn (T[i] : 8 : 3) ; END ; {= = = = = = = = = = = = = = = = = = P P = = = = = = = = = = = = = = = = = = == = } BEGIN Saisie (N) ; Remplir_Hasard (T, N) ; WriteLn ('Tableau non trié ');


Tri_Fusion (T, N) ; WriteLn ('Tableau trié ' ); Affiche_Tab (T, N) ; END.



CHAPITRE 4 LES ALGORITHMES RECURRENTS

I/ Introduction : Un algorithme ou un traitement est dit récurrent s’il utilise un procédé itératif ou récursif pour engendrer un résultat qui dépend de 1 ou plusieurs résultats précédents, on parle alors d’un algorithme ou d’un traitement récurrent d’ordre. L'ordre est le nombre de traitements précédents dont dépend le résultat. Un algorithme récurrent d’ordre p est un algorithme donnant un résultat dépendant des p résultats précédents. p peut être 1,2,3, etc. II/ Exemples d'algorithmes récurrents

II-1 Calcul de somme Activité

1/ Ecrire une analyse et un algorithme de la procédure Somme_Matrice, qui calcule la somme des éléments d’une matrice carrée d’entiers comportant n lignes et n colonnes (4 ≤ n ≤ 20). 2/ Ce traitement est-il récurent ?

Dans l’affirmative donnez son ordre.

* - * - * - * - * - * - * - * - * - * - * Réponse à la question 2 : 1- Pour calculer la somme des éléments d'une matrice, nous devons cumuler la totalité de ses éléments. Le cumul nécessite une initialisation à zéro de la variable de calcul, ici Somme. Un parcourt, de toute les lignes et les colonnes est donc nécessaire pour lire le contenu des cases et les ajouter chaque fois à la somme. Somme somme + M[ligne, colonne] Puisque ce traitement fait toujours référence à l’élément précédent, donc c’est un traitement récurent d’ordre 1. Analyse de la fonction Somme_Matrice Résultat : SOMME_MAT Traitement : Pour calculer la somme des éléments de la matrice M de type MAT, nous devons cumuler tous les éléments quelle contient. Deux boucles complètes, une pour parcourir les lignes et l’autre pour parcourir les colonnes de la matrice sont nécessaires. Une initialisation à zéro de la variable Somme est obligatoire (traitement récurent d'ordre 1).

Pour ligne de 1 à N Faire Pour colonne de 1 à N Faire Somme Somme + M [ligne, colonne]



Fin Pour Fin Pour

Fin Analyse Algorithme de la fonction SOMME_MAT 0) Fonction Somme_Matrice (M : MAT ; N : Entier) : Entier 1) Somme 0 2) Pour ligne de 1 à N Faire Pour colonne de 1 à N Faire Somme S + M [ligne, colonne] Fin Pour Fin Pour 3) Somme_Matrice Somme 4) Fin Somme_Matrice Tableau de codification des objets locaux :

Objets Type / Nature Rôle Somme Entier Variable de cumul ligne Entier Compteur des lignes de la matrice colonne Entier Compteur des colonnes de la matrice Traduction en Pascal FUNCTION Somme_Matrice (M : MAT; N : Integer) : Integer ; VAR Somme, ligne, colonne : Integer ; Begin Somme := 0; For ligne := 1 To N Do Begin For colonne := 1 To N Do Begin Somme := Somme + M[ligne, colonne] ; End ; End ; Somme_Matrice := Somme ; End; III/ Algorithme récurrent sur les chaînes Activité Suite de Thue-Morse



Si on considère sur l’ensemble des chaînes constituées uniquement de "0" et de "1"(mots binaires), la transformation qui consiste à remplacer toute occurrence du caractère "0" par la chaîne "01" et toute occurrence du caractère "1" par la chaîne "10", on définit la suite de Thue-Morse en partant de la chaîne "0" :

U0 "0" U1 "01" U2 "0110" U3 "01101001" U4 "0110100110010110" U5 "0110 1001100101100110100110010110"

* - * - * - * - * - * - * - * - * - * - *

1/ Cette suite est-elle récurrente ?

Dans l’affirmative donnez son ordre. 2/ Ecrire un programme nommé Suite_Thue_Morse permettant de calculer et d'afficher les N premiers termes de la suite de Thue-Morse à partir d’un caractère A ("0" ou "1") donnée.

- * - * - * - * - * - * - * - * - * - * - * - * -

Réponse à la question 1 : Le premier résultat dépend de la première valeur du caractère ("0" ou "1"), un deuxième résultat est obtenu à partir du premier trouvé, et ainsi de suite. On conclu que c'est une suite récurrente d’ordre 1. 2- Analyse Analyse du programme principal Résultat : Ecrire ("La suite de Thue-morse à partir de ", A, " Est ", Fn Thue_Morse (N, A) ) Traitement : Thue_Morse est une fonction appelée au niveau du programme principal dans un contexte d'affichage. Cette fonction génère la suite Thue_Morse à partir d'un caractère A de départ qui est soit "0" sit "1". Fin Saisie Algorithme du programme principal 0) Début Suite_Thue_Morse 1) Saisie (N, A) 2) Ecrire ("La suite de Thue-morse à partir de ", A, " Est ", Fn Thue_Morse (N, A) ) 3) Fin Suite_Thue_Morse Tableau de codification des objets globaux :

Objets Type / Nature Rôle



N Entier Nombre d'éléments de la suite A Caractère Caractère "0" ou "1" Thue_Morse Fonction Fonction qui génère la suite Thue_Morse Analyse de la fonction Thue_Morse Résultat = Thue_Morse Traitement : - On initialise la chaîne de caractères Ch à la valeur de A - On initialise un compteur j à la valeur 1. Ce compteur avance d'un pas de 2 car à chaque fois on ajoute deux caractères "01 ou "10" à la chaîne Ch. - On vérifie la valeur de CH[j], si elle vaut "0" alors on insère le caractère "1" dans la chaîne Ch à la position J+1, sinon on insère le caractère "0" puis on incrémente de 2 le compteur j. - On répète ce traitement N fois. Fin Analyse Algorithme de la fonction Thue_Morse 0) Fonction Thue_Morse (N : Entier ; A: Caractère) : Chaîne 1) CH A 2) Pour i de 1 à N Faire

j 1 Répéter

Si CH[j] = "0" Alors insère ("1", CH , j +1) Sinon insère ("0", CH, j +1) Fin Si

L Long (Ch) j j + 2

Jusqu'à (j > L) Fin Pour 3) Thue_Morse Ch 4) Fin Thue_Morse Tableau de codification des objets locaux :

Objets Type / Nature Rôle i Entier Compteur j Entier Compteur L Entier Longueur de la chaîne Ch Chaîne Chaîne représentant la suite Thue_morse Traduction en Pascal PROGRAM Suite_Thue_Morse ; USES Crt ; VAR N : Integer ; A : Char ;



{------------------------------------------------------------------------------------} PROCEDURE Saisie (VAR N : Integer ; VAR A: Char ); Begin Repeat Write('Donner le nombre d''éléments de la suite : '); readLn (N); Until N In [2 .. 100] ; Repeat Write('Donner un caractère 0 ou 1 : '); readLn (A); Until A In ['0', '1'] ; End; {------------------------------------------------------------------------------------} FUNCTION Thue_Morse (N: Integer; A : Char ) : String ; VAR Ch : String ; i, j, L : Integer ; Begin Ch := A ; For i := 1 To N Do Begin j := 1 ; Repeat If Ch [j] = '0' Then Insert ('1', Ch, j+1) Else Insert ('0', Ch, j+1); L := Length (Ch) ; j := j+ 2; Until j > l ; End; Thue_Morse := Ch ; End ; {========== Programme principal ===================} BEGIN Saisie (N, A) ; WriteLn('La suite de Thue-morse à partir de ', A, ' Est ', Thue_Morse (N, A) ) ; END . IV/ Triangle de Pascal Le triangle de Pascal est le tableau des coefficients qui sont utilisés pour le développement de certaines expressions comme (a+b)² ou (a+b)n. Cela s'appelle la "formule du binôme de Newton". Les coefficients s'appellent les "coefficients binomiaux" ou "coefficients du binôme". Ce triangle est le suivant :



0 : 1 (a+b)0 = 1 1 : 1 1 (a+b)1 = 1*a + 1*b 2 : 1 2 1 (a+b)2 = 1*a2 + 2*a*b + 1*b2 3 : 1 3 3 1 (a+b)3 = 1*a3 + 3*a2*b + 3*a*b2 + 1*b3 4 : 1 4 6 4 1 (a+b)4 = 1*a4 + 4*a3*b + 6*a2*b2 + 4*a*b3 + 1*b4 On obtient chaque coefficient en additionnant le nombre qui lui est situé au-dessus ainsi que celui qui lui est situé au-dessus à gauche. Pour n = 3, le Triangle de Pascal affiché est le suivant :

Ligne 1 1 Ligne 2 1 1 Ligne 3 1 2 1 Colonnes 1 2 3

Pour n = 5, le Triangle de Pascal affiché est le suivant :

Ligne 1 1 Ligne 2 1 1 Ligne 3 1 2 1 Ligne 4 1 3 3 1 Ligne 5 1 4 6 4 1 Colonnes 1 2 3 4 5

On constate que le calcul du contenu de la case (3,2) fait référence au contenu de deux cases précédentes. C'est un traitement récurrent d'ordre 2. Lecture : La tradition attribue le nom de triangle de Pascal au triangle décrit plus haut. Cependant, ce triangle était déjà connu en Orient et moyen Orient plusieurs siècles avant la publication de Blaise Pascal. Il était ainsi connu des mathématiciens persans, par exemple al-Karaji (953 - 1029) ou Omar Khayam au XIe siècle qui l'utilisent pour développer (a + b)n Activité

MAT[5,4] = MAT[4,4] + MAT[4,3]

MAT[3,2] = MAT[2,2] + MAT[2,1]



On se propose d’afficher les N premières lignes du Triangle de Pascal avec (3 ≤ N ≤ 100). On rappelle que le principe de remplissage des n premières lignes de la matrice MAT représentant le Triangle de Pascal est le suivant : Pour une ligne donnée : Le premier élément et le dernier élément sont égaux à 1, Les autres éléments sont déterminés en appliquant la formule suivante :

MAT [ligne, colonne] = MAT [ligne-1, colonne] + MAT [ligne-1, colonne-1] Questions 1/ Est-ce que ce traitement est récurrent ?

Dans l’affirmative donnez son rang. 2- Ecrire un programme nommé Triangle_de_Pascal, Qui affiche pour un nombre de lignes compris entre 1 et 20 (3 ≤ N ≤ 20), deux fois le triangle. Le premier triangle est obtenu par traitement itératif et le second par un traitement récursif.

* - * - * - * - * - * - * - * - * - * - *

1/ L'exemple ci-dessous montre que le calcul du contenu de la case (3, 2) fait référence au contenu de deux cases précédentes. C'est un traitement récurrent d'ordre 2. 2/ Analyse du problème Analyse du programme principal Résultat : Deux affichages d’une matrice contenant les différentes valeurs du Triangle de Pascal, réalisé chaque fois par l'appel la procédure Afficher_Triangle Traitement : - Le premier affichage est celui de la matrice obtenue par le traitement itératif (Proc Triangle_itératif). - Le deuxième affichage est celui de la matrice obtenue par le traitement récursif (Proc Triangle_récursif). - L'entier N qui représente le nombre de lignes du Triangle, est lu par la procédure Saisie. Fin analyse Algorithme du programme principal 0) Début Triangle_Pascal 1) Proc Saisie (N) 2) Proc Triangle_itératif (N, MAT) 3) Proc Afficher_Triangle (N, MAT) 4) Proc Triangle_récursif (N, MAT) 5) Proc Afficher_Triangle (N, MAT) 6) Fin Triangle_Pascal



Tableau de codification des objets globaux : Objets Type / Nature Rôle N Entier Nombre de lignes du triangle de Pascal MAT Matrice Représentant le Triangle de Pascal Saisir Procédure Permet de saisir N le nombre de lignes du Triangle Triangle_itératif Procédure Permet de remplir la matrice représentant le Triangle

de Pascal par un procédé itératif Triangle_récursif Procédure Permet de remplir la matrice représentant le Triangle

de Pascal par un procédé récursif Affiche_Triangle Procédure Permet d’afficher le Triangle de Pascal Max_N Constante = 20 Nombre de lignes max du triangle Tableau de codification des nouveaux types :

Type Matrice = Tableau de 20 lignes et N colonnes d’entiers

Analyse de la procédure Triangle_iteratif Résultat = Remplir la matrice MAT Traitement : On constate que : Ligne 1 MAT [1,1] contient la valeur 1 Ligne 2 MAT [2,1] et MAT [2,2] contiennent la valeur1 Ligne x On utilise deux boucles : une pour les lignes et une autre pour les colonnes.

Pour ligne de 3 à N Faire MAT [ligne, 1] 1 (première case de la ligne reçoit 1) MAT [Ligne, Ligne] 1 (dernière case de la ligne reçoit 1) Pour colonne de 2 à ligne -1 Faire

MAT [ligne, colonne] MAT [ligne - 1, colonne] + MAT [ligne -1, colonne - 1]

Fin Pour Fin Pour Algorithme 0) Procédure Triangle_itératif (N: Entier; VAR MAT : Matrice); 1) MAT [1,1] 1 2) MAT [2,1] 1 3) MAT [2,2] 1 4) Pour ligne de 3 à N Faire

MAT [ligne, 1] 1 MAT [Ligne, Ligne] 1 Pour colonne de 2 à ligne -1 Faire

MAT [ligne, colonne] MAT [ligne - 1, colonne] + MAT [ligne -1 , colonne - 1]

Fin Pour Fin Pour 5) Fin Triangle_itératif



Tableau de codification des objets locaux :

Objets Type / Nature Rôle ligne Compteur Compteur des lignes de la matrice colonne Compteur Compteur des colonnes de la matrice Analyse de la procédure Triangle_récursif Résultat : matrice remplie représentant le Triangle de Pascal Traitement : Pour chacune des n lignes de la matrice, un parcourt des colonnes (de la première à celle qui porte le numéro de la ligne), est nécessaire pour déterminer leurs valeurs en faisant appel à la fonction récursive Val_Triangle. Algorithme 0) Procédure Triangle_récursif (N : Entier ; VAR MAT : matrice) 1) Pour ligne de 1 à n Faire Pour colonne de 1 à ligne Faire Mat [ligne, colonne] ← Fn Val_Triangle (colonne, ligne) FinPour FinPour 2) Fin Triangle_récursif Analyse de la fonction Val_Triangle Résultat : Val_Triangle Traitement : (déterminer une valeur du Triangle selon la ligne (x) et la colonne (y) données comme paramètres). Pour la première ligne, la valeur est égale à 1, Si le numéro de ligne est égal au numéro de colonne, la valeur est aussi égale à 1, sinon la valeur trouvée à l’intersection de la ligne x et de la colonne y est égale à (la valeur trouvée à l’intersection de la ligne x et de la colonne y-1) + (la valeur trouvée à l’intersection de la ligne x-1 et de la colonne y-1) Fin Analyse Algorithme 0) Fonction Val_Triangle (x, y : Entier) : Entier 1) Si (x = 1) OU (y = x) Alors Val_Triangle ← 1 Sinon Val_Triangle ← Fn Val_Triangle (x, y - 1) + Fn Val_Triangle (x - 1, y - 1) Finsi 2) Fin Val_Triangle Analyse de la procédure Afficher_Triangle Résultat = Afficher la matrice MAT



Traitement : On utilise deux boucles : une pour les lignes et une autre pour les colonnes afin d'afficher le contenu de la matrice. Fin Analyse Algorithme de la procédure Afficher_Triangle 0) Procédure Afficher_Triangle (N : Entier ; MAT : Matrice) 1) Pour ligne de 1 à N Faire Pour colonne de 1 à ligne Faire Ecrire (Mat [ligne, colonne]," ") {Sans retour à la ligne} FinPour Ecrire ( ) {avec retour à la ligne} FinPour 2) Fin Afficher_Triangle Traduction en Pascal PROGRAM Triangle_de_Pascal ; USES Crt ; CONST

max = 20; TYPE

Matrice = ARRAY[1.. 20, 1.. 20] Of Integer ; VAR

N : Integer ; MAT : Matrice ;

{------------------------------------------------------------------------------------} PROCEDURE Saisie (VAR N : Integer ); BEGIN Repeat Write ('Nombre de lignes du triangle : '); ReadLn (N) ; Until N IN [3.. max] ; END ; {------------------------------------------------------------------------------------} PROCEDURE Triangle_iteratif (N: Integer; VAR MAT : Matrice); VAR

ligne, colonne : Integer ; BEGIN MAT [1,1] := 1 ; MAT [2,1] := 1 ;



MAT [2,2] := 1 ; For ligne := 3 To N Do Begin MAT [ligne, 1] := 1; MAT [Ligne, Ligne] := 1; For colonne := 2 To ligne -1 Do Begin MAT [ligne, colonne] := MAT [ligne - 1, colonne] + MAT [ligne -1 , colonne - 1]; End ; End ; END ; {------------------------------------------------------------------------------------} FUNCTION Val_Triangle (x, y : Integer) : Integer ; BEGIN

If (x = 1) OR (y = x) Then Val_Triangle := 1 Else Val_Triangle := Val_Triangle (x, y - 1) + Val_Triangle (x - 1, y - 1) ;

END ; {------------------------------------------------------------------------------------} PROCEDURE Afficher_Triangle (n : Integer; MAT : matrice); VAR ligne, colonne : Integer ; BEGIN For ligne := 1 To N Do Begin For colonne := 1 To ligne Do Begin Write(Mat [ligne, colonne]:2,' ') ; End; WriteLn ; End; END ; {------------------------------------------------------------------------------------} PROCEDURE Triangle_recursif (N : Integer; VAR MAT : Matrice) ; VAR ligne, colonne : Integer ; BEGIN For ligne := 1 To N Do For colonne := 1 To ligne Do Mat [ligne, colonne] := Val_Triangle (colonne, ligne) ; END; {=============== Programme principal ============== } BEGIN



Saisie (N) ; WriteLn ('Triangle de Pascal - Traitement itératif '); Triangle_iteratif (N, MAT) ; Afficher_Triangle (N, MAT) ; WriteLn; WriteLn('Triangle de Pascal - Traitement récursif '); Triangle_recursif (N, MAT); Afficher_Triangle (N, MAT) ; END. V/ La suite de Fibonacci Léonard de Pise, plus connu sous le nom de Fibonacci, étudia du point de vue numérique la reproduction des lapins. L'unité de base est un couple de lapins, il considère qu'un couple de jeunes lapins met une saison pour devenir adulte, attend une deuxième saison de gestation, puis met au monde un couple de jeunes lapins à chaque saison suivante. En supposant que les lapins ne meurent jamais, et lorsque l'on met côte à côte le nombre de couples de lapins à chaque saison, cela donne... la suite de Fibonacci :

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610............

Le nombre de couples de lapins Un à la saison n est égal au nombre de couples de lapins adultes, c'est-à-dire le nombre total de lapins qu'il y avait à la saison précédente n-1, auquel on ajoute le nombre de couples de jeunes lapins, qui est égal au nombre de couples de lapins adultes à la saison précédente, donc au nombre total de couples à la saison n-2. C'est pourquoi on a: Un = Un-1 + Un-2 Tout ceci est plus clair avec un tableau:

saison n nombre de couples de lapins adultes ( = un-1) nombre de couples de jeunes lapins (= un-2)

nombre total de couples de lapins un (Fibo)

1 0 1 1 2 1 0 1 3 1 1 2 4 2 1 3 5 3 2 5 6 5 3 8 7 8 5 13 8 13 8 21 9 21 13 34

La suite de Fibonacci est une suite récurrente dont chaque élément obéit à la relation de récurrence : Un = Un-1 + Un-2



Avec U1 = 1 et U2 = 1 Donc c'est une suite récurrente d'ordre 2. Activité 1 Ecrire un programme qui, pour un entier N donné, calcule le Nième terme de la suite de Fibonnaci. Un = Un-1 + Un-2 Avec U1 = 1 et U2 = 1 Donner une solution itérative, sans avoir recourt à un tableau, utilisant une fonction nommée Fibo_Itérative. N étant un entier compris entre 1 et 50.

* - * - * - * - * - * - * - * - * - * - *

Analyse du programme principal Suite_itérative_Fibonacci Résultat : Ecrire ("Fibo de ", N, " = " , Valeur_Fibo) Traitement : - Une fonction itérative Fibo_Itérative retourne la valeur du Nième terme de la suite. - Une procédure Saisie, assure la lecture et le test de l'entier N. Fin Suite_itérative_Fibonacci Algorithme 0) Début Suite_itérative_Fibonacci 1) Proc Saisie (N) 2) Valeur_suite Fn Fibo_Itérative (N) 3) Ecrire ("Fibo de ", N , " = " ,Valeur_Fibo) 4) Fin Suite_itérative_Fibonacci Tableau de codification des objets globaux : Objets Type / Nature Rôle N Entier Nombre de terme de la suite Valeur_Fibo Entier Long Valeur de la suite Analyse et algorithme de la procédure Saisie

- Voir les exemples précédents, car cette procédure à fait l'objet de plusieurs études. Il est à noter qu'elle figure au niveau de la traduction en Pascal. Analyse de la fonction Fibo_Itérative Résultat = Fibo_Itérative Traitement :



- Cette suite est récurrente d'ordre 2. On doit initialiser ses deux premiers termes. U1 = 1 U2 = 1 - Donc on constate que si N ≤ 2, le dernier terme de la suite est égal à 1 Si N ≤ 2 Alors Fibo 1 - Sinon on calcule cette suite par une itération de 3 à N

Fibo u1 + u2 u1 u2 u2 Fibo - Le résultat final est la dernière valeur obtenue Fibo_Itérative Fibo Fin Fibo_Itérative Algorithme 0) Fonction Fibo_Itérative (N : Entier) : Entier Long 1) U1 1 2) U2 1 3) Si N ≤ 2 Alors Fibo 1 Sinon Pour i de 3 à N Faire Fibo U1 + U2 U1 U2 U2 Fibo Fin Pour Fin Si 5) Fibo_Itérative Fibo 6) Fin Fibo_Itérative Tableau de codification des objets locaux : Objets Type / Nature Rôle U1, U2 Entier Eléments de la suite Fibo Entier Long Calcul de la suite i Entier Compteur Traduction en Pascal PROGRAM Suite_iterative_Fibonacci ; USES Crt ; CONST Nmax = 50 ; VAR Valeur_Fibo : LongInt ; N : Integer ;



{-----------------------------------------------------------------------------} PROCEDURE Saisie (VAR N : Integer); BEGIN Repeat Write ('N = '); ReadLn (N); Until N IN [1.. Nmax] ; END ; {-----------------------------------------------------------------------------} FUNCTION Fibo_Iterative (N : Integer ) : LongInt ; VAR U1, U2, i : Integer ; Fibo : LongInt ; BEGIN

U1 := 1 ; U2 := 1 ; If N



Analyse de la fonction Fibo_Tab Résultat = Fibo_Tab Traitement : - On initialise les deux premières case du tableau T à 1. T[1] 1 T(2] 1 - Donc on constate que si N ≤ 2, le dernier terme de la suite est égal à 1 Si N ≤ 2 Alors Fibo 1 - Sinon on calcule cette suite par une itération de 3 à N

Pour i de 3 à N Faire T[i] T[i - 1] + T[i - 2] - Le résultat final est la dernière valeur obtenue Fibo_Itérative T[N] Fin Fibo_Tab Algorithme 0) Fonction Fibo_Tab (N : Entier ; T : Tab) : Entier Long 1) T[1] 1 2) T[2] 1 3) Si N ≤ 2 Alors Fibo 1 Sinon Pour i de 3 à N Faire T[i] T[i-1] + T[i-2] Fin Pour Fibo T[n] Fin Si 4) Fibo_Tab Fibo 5) Fin Fibo_Tab Modification du tableau de codification des objets globaux : Objets Type / Nature Rôle N Entier Nombre de terme de la suite Valeur_Fibo Entier Long Valeur de la suite T Tab Tableau des termes de la suite Nmax Constante = 50 Valeur maximal de N Tableau de codification des nouveaux types

Types Tab = Tableau de Nmax Entier Long Tableau de codification des objets locaux : Objets Type / Nature Rôle Fibo Entier Long Calcul de la suite i Entier Compteur



Traduction en Pascal de la fonction Fibo_Tab FUNCTION Fibo_Tab (N : Integer ; T : Tab) : LongInt ; VAR i : Integer ; Fibo : LongInt ; BEGIN T[1] := 1 ;

T[2] := 1 ; If (N < = 2) Then Fibo := 1 Else For i := 3 To N Do Begin

T[i] := T[i-1] + T[i-2] ; End ; Fibo := T[n] ;

Fibo_Tab := Fibo ; END ; Activité 3 Remplacer dans le programme précédent la fonction Fibo_Tab par une autre fonction réalisant le même traitement mais cette fois avec un procédé récursif. Cette fonction sera nommée Fibo_Récursive.

* - * - * - * - * - * - * - * - * - * - *

Analyse de la fonction Fibo_Récursive Résultat = Fibo_Récursive Traitement : Le calcul de la fonction de Fibonacci fait référence aux deux éléments précédents. Un = Un-1 + Un-2 Avec U1 = 1 et U2 = 1 PuisqueU3 fait référence à ces deux éléments précédents U1 et U2 qui sont connus, on peut dire que U3 est aussi connu. Pour un l'élément N on peut écrire : Fibo_Récursive Fn Fibo_Récursive (N-1) + Fn Fibo_Récusive (N-2) C'est un traitement récursif Fin Analyse 3/ Solutions récursive :



Algorithme 0) Fonction Fibo_Récursive (N : Entier ) : Entier Long 1) Si N ≤ 2 Alors Fibo_Récursif 1 Sinon Fibo_Récursif Fn Fibo_Récursif (N-1) + Fn Fibo_Récursif (N-2) Fin Si 2) Fin Fibo_Récursif Traduction en Pascal de la fonction Fibo_Récursif FUNCTION Fibo_Recursif (N : Integer ) : LongInt ; BEGIN If (N < = 2) Then Fibo_Recursif := 1

Else Fibo_Recursif := Fibo_Recursif (N-1) + Fibo_Recursif (N-2) ;

END ; VI/ Le nombre d'or Définition et valeur du nombre d'or Le nombre d'or est la solution positive de l'équation : x2 -x -1 = 0 C'est-à dire le nombre (1 + 5 ) / 2

La suite (Vn) définie sur N* par Vn = (n) Fib

1) (n Fib + semble converger vers le nombre d'or

ϕ = 2

5 1+ dont une valeur approchée est 1,618.

Exemples pour n de 1 à 7:

n Fib (n) Valeur exacte de Fib (n+1) / Fib (n) Valeur approchée de

Fib (n+1) / Fib (n) 1 1 1 1 2 1 2 2 3 2 3/2 1,5 4 3 5/3 1,666 5 5 8/5 1,6 6 8 13/8 1,625 7 13 21/13 1,615



Les 100 premières décimales du nombre d'or sont : 1,618 033 988 749 894 848 204 586 834 365 638 117 720 309 179 805 762 862 135 448 622 705 260 462 189 024 497 072 072 041 On a vu précédemment que : La suite de Fibonacci est une suite de nombres entiers. Voici le début de cette suite :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... jusqu'à l'infini. Un nombre de la suite est le résultat de la somme de ses deux précédents (U3 = U1 + U2). Voici maintenant pourquoi le nombre d'or et la suite de Fibonacci sont étroitement liés: 1/0 = Ceci n'existe pas. 1/1 = 1 2/1 = 2 3/2 = 1.5 5/3 = 1.6666... 8/5 = 1.6 13/8 = 1.625 21/13 = 1.61538... 34/21 = 1.61904...

(n) Fib1) (n Fib + = 1.6….

Le nombre d'or, habituellement désigné par la lettre φ (phi) de l'alphabet grec. Activité Ecrire une fonction nommé Nombre_Or, qui retourne une approximation du nombre d'or avec une précision de 10-6

* - * - * - * - * - * - * - * - * - * - * Analyse de la fonction Nombre_Or Résultat = Nombre_Or Traitement : On calcule en premier lieu la suite de Fibonacci dans un tableau. U[i ] = U[i -1] + U[i - 2] avec U[1] = 1 et U[2] = 1

Puis on calcule La suite (Vn) définie sur N* par Vn = (n) Fib

1) (n Fib + qui converge vers le

nombre d'or. V[i] = U[i] / U[i-1] On répète ce

Documents

Dhouihri Alaa - site éducative pour les étudiants de ...Ce nouveau calcul n'utilise pas un procédé itératif mais il appelle la même fonction avec un nouveau paramètre qui est