PROGRAMMER AVEC ZAYDOUN T2

2016 PROGRAMMER AVEC ZAYDOUN Algorithmique et programmation Ce livre est destiné aux élèves du 4eme année de l'enseignement secondaire SECTION SCIENCES DE L'INFORMATIQUE Ahmed Amine Rassas Etudiant Rassas Amine 1  PREFACE Zied Chaouch (mort Janvier 5, 2016) est un professeur universitaire d'informatique. Il était très connu dans la ville de Sousse comme professeur d'algorithmique de tutorat pour les élèves des écoles secondaires. Cette œuvre a pour but d'assembler les travaux du défunt monsieur Zied Chouch, mon cher professeur d'Informatique durant sa carrière d'enseignement en vu de la documentation de ses chef d'œuvres . Plusieurs générations ont profité du savoir qu'il ne cessait de répandre là où il passait. L'amour et le respect ont imprégné les rapports que les apprenants tenaient avec cet terminent savant . Son sérieux et son attachement à son travail étaient non seulement à l'origine du succès de tous ses disciples mais aussi du respect et de reconnaissance de ses collègues. D'ailleurs , un bon nombre de ses élèves ont poursuivi leurs études universitaires en informatique avec excellence. Humainement il était très proche de ses élèves, allant jusqu'à entretenir des relations amicales avec eux. Il était d'une bonté sans égale et d'une sincérité remarquable. Pour moi, c'était un père avec ses conseils , un ami avec son humilité , un frère avec son soutien . J'ai tant essayé de lui adresser cette reconnaissance quand il était avec nous , malheureusement , la mort me l'a arraché. tu resteras toujours vivant dans mon cœur et dans ma mémoire. Que votre âme repose en paix. #ZAYDOUN L'homme qui a passionné toute une génération par l'informatique 2  SOMMAIRE Chapitre 1 : Les enregistrements et les fichiers ........................................................ 3 Chapitre 2 : La récursivité ........................................................ 52 Chapitre 3 : Les algorithmes arithmétiques ........................................................ 67 Chapitre 4 : Les algorithmes de tri & de recherche ........................................................ 78 Chapitre 5 : Les algorithmes récurrents ........................................................ 89 Chapitre 6 : Les algorithmes approximation ....................................................... 105 Chapitre 1 : Les enregistrements et les fichiers I. Les enregistrements 3  1) Enregistrement simple : X C1 C2 Champ1 C3 Champ2 Champ3 TDNT Type Nom_type = enregsitrement C1 : type C2 :type C3 :type Fin nom_type Pascal : Type Nom_type = record C1 :type ; C2 :type ; C3 :type ; End ; Exercice n°1 Déclarer un nouveau type nommé groupe, sachant qu’un groupe est caractérisé par un code, un nom, nombre de personne dans le groupe. TDNT Type groupe = enregsitrement cod : entier nom :chaîne [20] nbr : entier Fin groupe Pascal : Type groupe = record cod : integer; nom : string[20] ; nbr : integer; End ; Exercice n°2 Déclarer un nouveau type nommé éléve , sachant qu’un élève est caractérisé par un CIN, un nom, prénom , âge. TDNT 4  Type eleve = enregsitrement CIN, age : entier Nom, prenom :chaîne [20] Fin eleve Exercice n°3 : Ecrire une analyse et un programme pascal permettant de saisir deux produit A et B, sachant qu’un produit est caractérisé par un code, libellé et un prix. Afficher le produit le plus cher. Analyse principale : Résultat = proc affich(A, B) A = proc saisi(A) B = proc saisi(B) Fin TDNT Type Produit = enregistrement Cod :entier Lib :chaîne Prix :réel Fin produit TDOG Nom A, B Saisi Affich Type Produit Procédure Procédure Analyse de la procédure saisie Def proc saisi ( var X : produit) Résultat = X x.Cod=donnée x.Lib = donnée x.Prix = donnée Fin proc saisi Analyse de la procédure saisie (2ème méthode le plus utilisé) : on ulilise avec qu’avec saisi et l’affichage. Def proc saisi ( var X : produit) Résultat = X Avec X faire Cod=donnée Lib = donnée Prix = donnée Fin avec Fin proc saisi 5  Analyse de procédure affich Def proc affich (A, B :produit) Résultat = [ ] si A.prix>B.prix alors écrire (A.cod,A.lib,A.prix) sinon si B.prix>B.prix alors écrire (B.cod ,B.lib,B.prix) sinon écrire(''de même prix''); Fin proc affich Pascal : program ex; uses wincrt; type produit = record cod:longint; lib:string; prix:real; end; var a, b:produit; {************************ les modules ************************} procedure saisi(var x:produit); begin with x do begin write('code: '); readln(cod); write('libellé: '); readln(lib); write('prix: '); readln(prix); end; end; procedure affich(a, b:produit); begin if a.prix>b.prix then writeln(a.cod,' ',a.lib,' ',a.prix:0:3) else if b.prix>a.prix then writeln(b.cod,' ',b.lib,' ',b.prix:0:3) else writeln('de même prix'); end; {************************ PP ************************} begin saisi(a); saisi(b); affich(a,b); end. Exercice n°2 6  Ecrire une analyse et un programme pascal permettant de saisir les informations de deux élèves, sachant qu’un élève est caractérisé par son nom, note1, coefficient 1, note2, coefficient2, afficher le nom de l’élève possédant la meilleure moyenne ainsi que sa moyenne. Analyse principale : Résultat = proc affich (X, Y) Y = proc saisi(Y) X = proc saisi (X) Fin ex TDNT Type Eleve= enregistrement Nom :chaîne n1,c1,n2,c2 :réel fin eleve TDOG Nom X,Y Saisi Affich Type Eleve Procédure procédure Analyse de la procédure saisi Def proc saisi (var A : eleve) Résultat = A Avec A faire Nom=donnée N1=donnée C1= donnée N2= donnée C2= donnée Fin avec Fin proc saisi Analyse de la procédure affich Def proc affich(X, Y :eleve) Résultat = [] Moy1 ((x.n1*x.c1)+ (x.n2*x.c2))/(x.c1+x.c2) Moy2 ((y.n1*y.c1)+ (y.n2*y.c2))/(y.c1+y.c2) Si moy1>moy2 alors écrire(x.nom) Sinon si moy2>moy1 alors écrire(y.nom) Sinon écrire(‘’même moyenne’’) Fin si Fin proc affich TDOL 7  Nom Moy1, moy2 Type Réel 2) Enregistrement imbriqué Exercice 2: Ecrire un programme permettant de saisir deux personne x et y, sachant qu’une personne est caractérisé par : un nom, un prénom et une date de naissance et afficher la personne la plus jeune. Nom prenom X J M DN A x.dn.m x.nom Nom prenom y J M DN A Analyse principale : Résultat = proc affich(x, y) X= proc saisi(x) Y = proc saisi(y) Fin ex TDNT Type Date= enregistrement J, m, a :entier Fin date pers= enregistrement Nom :chaîne Prenom : chaîne Dn : date Fin eleve TDOG Nom X, Y Saisi Affich Type pers Procédure Procédure Analyse de la procédure saisi Def proc saisi (var z :eleve) Résultat = z Z= Avec z faire 8  Nom= donnée Prenom=donnée Avec dn faire J, m, a= donnée Fin avec Fin avec Fin proc saisi Analyse de la procédure affich Def proc affich (x, y : eleve) Résultat = [] [ ]= Si x.dn.a > y.dn.a alors écrire(x.nom, x.prenom, x.dn,j,’’/’’, x.dn,m,’’/’’, x.dn,a) Sinon si x.dn.a < y.dn.a alors écrire(y.nom, y.prenom, y.dn,j,’’/’’, y.dn,m,’’/’’, y.dn,a) Sinon si x.dn.m > y.dn.m alors écrire(x.nom, x.prenom, x.dn,j,’’/’’, x.dn,m,’’/’’, x.dn,a) Sinon si x.dn.m < y.dn.m alors écrire(y.nom, y.prenom, y.dn,j,’’/’’, y.dn,m,’’/’’, y.dn,a) Sinon si x.dn.j > y.dn.j alors écrire(x.nom, x.prenom, x.dn,j,’’/’’, x.dn,m,’’/’’, x.dn,a) Sinon si x.dn.j < y.dn.j alors écrire(y.nom, y.prenom, y.dn,j,’’/’’, y.dn,m,’’/’’, y.dn,a) Sinon écrire(‘’même age’’) Fin si Fin proc affich 3) Tableau d’enregistrement : Exercice 1 : Ecrire un programme permettant de saisir un tableau par n produit avec n compris entre 5 et 20, sachant qu’un produit est caractérisé par un code, date de fabrication, prix, afficher le prix le plus cher. Analyse principale : Résultat = proc affich (t, n) T, n = proc saisi(t, n) Fin ex TDNT Type Date = enregistrement J, m, a :entier Fin date Prod= enregistrement Cod :entier Prix :réel Df :date Fin prod Tab = tableau [1..20] de produit TDOG Nom T N Type Tab Entier 9