Home

d`Algorithmique - Faculté des Sciences Rabat

1. Instructions actions effets Xe X 3 X x 2 x 2 x 2 plus de 3 ex LT x Y X M El Marraki 12 31 03 2013 Algorithmique SMIA module M E2 La derni re instruction Y X signifie copier dans Y la valeur actuelle de X Un petit exercice instructif Quelles sont les valeurs successives prises par les variables X et Y suit aux instructions suivantes XEL GS RES XE Y a Y E X2 y at Y0 R ponses X 1 1 4 9 9 9 Y 4 4 4 7 13 Remarque noter aussi que l affectation est une expression comme une autre c est dire qu elle retourne une valeur Il est donc possible d crire Ko yY amp Z ceci revenant affecter Y le r sultat de l valuation de Z 2 puis X le r sultat de l affectation Y Z c est dire la valeur qu on a donn e Y Remarquez l ordre d valuation de la droite vers la gauche L affectation des types primitifs est tr s simple Puisque les donn es de type primitif contiennent une valeur r elle et non une r f rence un objet en affectant une valeur une variable de type primitif on copie le contenu d un endroit un autre Par exemple si on crit A B pour des types primitifs alors le contenu de B est copi dans A Si alors on modifie A bien entendu B n est pas affect par cette modification C est ce qu on rencontre g n ralement en programmation Echanger deux valeurs Probl me soit 2 variables quelcon
2. partir de quatre l ments invariables Ce n est que le nombre de ces l ments et l ordre dans lequel ils sont arrang s qui vont d terminer si on obtient une puce ou un l phant Les ordinateurs eux m mes ne sont fondamentalement capables d ex cuter que quatre op rations logiques 1 l affectation de variables 2 la lecture criture 3 les tests 4 les boucles Un algorithme informatique se ram ne donc toujours au bout du compte la combinaison de ces quatre petites briques de base Il peut y en avoir quelques unes quelques dizaines et jusqu plusieurs centaines de milliers dans certains programmes La taille d un algorithme ne conditionne pas en soi sa complexit de longs algorithmes peuvent tre finalement assez simples et de petits algorithmes peuvent tre tr s compliqu s L informatique est la science du traitement automatique de l information Pour cela il faut 1 mod liser cette information 2 d finir l aide d un formalisme strict les traitements dont elle fera l objet 3 et enfin traduire ces traitements dans un langage compr hensible par un ordinateur Les deux premiers points concernent l algorithmique alors que le dernier point rel ve de ce que l on nomme la programmation M El Marraki 2 31 03 2013 Algorithmique SMIA module M E2 L criture d un programme consiste g n ralement implanter une m thode de r solution d j connue et souvent con ue ind pendammen
3. tapes successives donnent lieu des sous algorithmes qui peuvent tre consid r s comme les primitives de machine interm diaires proc dures en Pascal fonction en C Le travail de l analyse est termin lorsqu on a obtenu un algorithme ne comportant que e Des primitives de la machine initiale e Des algorithmes d j connus L analyse descendante est la mise en pratique du Discours de la m thode de Descartes L ordre des instructions est essentiel la machine ne peut ex cuter qu une action la fois et dans l ordre donn c est la propri t de s quentialit Une fois ces actions d termin es 1l suffit de les traduire dans le langage de programmation Durant l criture d un programme on peut tre confront 2 types d erreur o les erreurs syntaxiques elles se remarquent la compilation et sont le r sultat d une mauvaise criture dans le langage de programmation o les erreurs s mantiques elles se remarquent l ex cution et sont le r sultat d une mauvaise analyse Ces erreurs sont beaucoup plus graves car elles peuvent se d clencher en cours d exploitation du programme 1 3 5 Ex cuter un programme La mise au point d un programme informatique se fait en plusieurs tapes Donn es Ex cution du programme Transformation des donn es Ordinateur en r sultats M El Marraki CO 31 03 2013 Algorithmique SMIA module M E2 1 3 6 Pseudo langage Un algorithme doit tre lisible
4. 1 leteste irem x i 0 est toujours vrai x prend toujours la m me valeur et la liste contiendra une infinit de 1 on obtient une boucle infini Exercice 4 sur 3 points 1 Solution variables n m debut fin d P S152 Entier ecrire entrer l entier n lire n ecrire entrer l entier m lire m s 0 52 0 ad 2 TantQue d d lt n faire Si irem n d 0 alors S1 S1 d n d finsi d amp d 1 FinTantQue p lt 2 TantQue p p lt m faire Si irem m p 0 alors S2 S2 p m p finsi p lt p li FinTantQue Si S1 S2 alors Ecrire n et m sont amis Sinon Ecrire n et m ne sont pas amis finsi 2 Solution variables n m i S1 S2 debut M El Marraki Entier ecrire entrer l entier n lire n ecrire entrer l entier m lire m s 0 SZ 0 Pour i allant de 2 n 1 faire Si irem n i 0 alors Si S1 i finsi FinPour Pour i allant de 2 m 1 faire 46 31 03 2013 Algorithmique SMIA module M E2 Si irem m i 0 alors s2 S2 i finsi FinPour Si S1 S2 alors Ecrire n et m sont amis Sinon Ecrire n et m ne sont pas amis finsi fin 5 3 Examen d informatique 1 session de Juillet 2004 Exercice 1 4 points Les tudiants ayant pass l examen du module 2 en session de Juin ont t class s selon leurs notes en trois cat gories pour une note inf rieure strictement 5
5. crira une fois Premi re boucle puis six fois de suite Deuxi me boucle et ceci dix fois en tout A la fin il y aura donc eu 10 x 6 60 passages dans la deuxi me boucle celle du milieu Notez la diff rence marquante avec cette structure Variables i j entier Pour i allant de 1 10 crire Premi re boucle Finpour Pour j allant de 1 6 crire Deuxi me boucle Finpour Ici il y aura dix critures cons cutives de Premi re boucle puis six critures cons cutives de Deuxi me boucle et ce sera tout Examinons l algorithme suivant M El Marraki 27 31 03 2013 Algorithmique SMIA module M E2 Variable 1 entier Pour i allant de 1 10 it i x2 crire Passage num ro i Finpour On remarque que la variable i est g r e en double ces deux gestions tant contradictoires D une part la ligne Pour augmente la valeur de i de 1 chaque passage D autre part la ligne i i 2 double la valeur de i chaque passage Il va sans dire que de telles manipulations perturbent compl tement le d roulement normal de la boucle Exemple Probl me On veut crire un algorithme qui calcul la somme des entiers positifs inf rieurs ou gaux N R solution 1 tape Analyse 1 Entrer la valeur de N 2 Calculer la somme des N premiers entiers positifs 3 Afficher le r sultat 2 tapes Conceptions 1 d claration des variables N i somme e
6. crit sur le clavier et lit sur l cran M El Marraki 16 31 03 2013 Algorithmique SMIA module M E2 3 2 3 Les libell s Avant de lire une variable il est tr s fortement conseill d crire des libell s l cran afin de pr venir l utilisateur de ce qu il doit frapper crire Entrez votre nom lire NomFamille 3 2 4 Exemples Exemple 1 Quel est le r sultat produit par le programme suivant Variables val dval entiers D but val 234 dval val 2 crire val crire dval Fin R ponses 234 468 1 am lioration Variables val dval entiers D but crire donner un entier un libell lire val dval val 2 crire le double est crire dval Fin Ex cution donner un entier 234 le double est 468 2 am lioration Nom double R le demande un nombre et affiche sont double Entr e val Sortie dval Variables val dval entiers D but crire donner un entier lire val dval val 2 crire le double de val est dval Fin Ex cution donner un entier 234 le double de 234 est 468 M El Marraki 17 31 03 2013 Algorithmique SMIA module M E2 Exemple 2 Probl me Multiplier deux nombres entiers En utilisant les primitives suivantes lire crire affecter multiplier Solution Algorithme Nom multiplication R le demander deux nombres et afficher leur multiplicati
7. le maximum est max fin M El Marraki 55 31 03 2013 Algorithmique SMIA module M E2 Exercice 2 Soit l algorithme suivant variables a b r entiers d but crire donner les valeurs de a et b lire a b TantQue b gt 0 faire asb a b reste de la division de a par b E D Er Oo t o FinTanQue crire a 1 Ex cuter le programme pr c dent afficher dans un tableau les valeurs de a b et r pour a a 35 et b 12 b a 96 et b 81 oR a 34 et b 21 2 Impl menter ce programme en langage C 3 Que fait ce programme Correction 1 mystere 35 12 a 35 12 11 1 b 2 11 1 0 r 1 1 0 La valeur affich e est 1 mystere 96 81 a 96 81 15 6 3 b 81 15 6 3 0 r 15 6 3 0 La valeur affich e est 3 mystere 34 21 a 34 21 13 8 5 3 2 1 b 21 13 8 5 3 2 1 0 r ES 8 5 3 2 1 0 La valeur affich e est 1 2 include lt stdio h gt include lt conio h gt void main int a byi 3 printf donner a et b scanf d d amp a amp b while b 0 Sb a b reste de la division de a par b O DH WU I h D printf le pgcd est d n a getch M El Marraki 56 31 03 2013 Algorithmique SMIA module M E2 Exercice 3 Deux nombres entiers n et m sont qualifi s d amis si la somme des diviseurs de n est gale m et la somme des diviseurs d
8. module M E2 2 Variables Dans un programme informatique on va avoir en permanence besoin de stocker provisoirement des valeurs Il peut s agir de donn es issues du disque dur fournies par l utilisateur frapp es au clavier Ces donn es peuvent tre de plusieurs types elles peuvent tre des nombres du texte etc D s que l on a besoin de stocker une information au cours d un programme on utilise une variable 2 1 D claration des variables La premi re chose faire avant de pouvoir utiliser une variable est de cr er la bo te et de lui coller une tiquette Ceci se fait tout au d but de l algorithme avant m me les instructions proprement dites C est ce qu on appelle la d claration des variables Une variable ne peut tre utilis e que s elle est d clar e La d claration se fait par la donn e du nom de la variable et du type de la variable 2 1 1 Noms de variables Le nom de la variable l tiquette de la bo te ob it des r gles qui changent selon le langage utiliser Les principales r gles respecter sont e Le nom de variable peut comporter des lettres et des chiffres e On exclut la plupart des signes de ponctuation en particulier les espaces e Un nom de variable doit commencer par une lettre e Le nombre maximal de caract res qui composent le nom d une variable d pend du langage utilis e Ne pas utiliser les mots cl s du langage de programmation 2 1 2 Types de varia
9. pour j allant de 1 n faire RS it pour k allant de 1 n faire S S A i k B k j finpour C il j S finpour fipour affichage de la matrice de C pour i allant de 1 n faire pour j allant de 1 n faire crire Cli l j finpour crire n retour la ligne finpour fin Exercice 25 1 Ecrire un algorithme qui effectue la lecture d une matrice carr e A ainsi que sa taille n et affiche la trace de A pour une matrice A a Trace A a la somme des l ments sur la diagonale 2 Ecrire un algorithme qui effectue la lecture d une matrice carr e A ainsi que sa taille n et affiche la matrice transpos tA de A Pour une matrice A ai tA a i Exercice 26 1 crivez un algorithme qui effectue la lecture de n un entier vect un tableau de n nombre r els mat une matrice carr e de nxn nombre r els il calcule et affiche le produit de la matrice mat par le vecteur vect 2 crivez un algorithme qui effectue la lecture de deux matrices allou es dynamiquement et affiche le produit de ces deux matrices 4 3 Applications 4 3 1 Les algorithmes de recherche dans un tableau Probl me recherche d un l ment dans un tableau Recherche s quentielle Analyse Parcours s quentiel du tableau Arr t lorsque la valeur est trouv e Retour l indice correspondant La valeur n est pas trouv e Retour d une valeur sp ciale M
10. 1 Si T i 1 T i 1 alors j O0 i n 1 FinsSi FinPour Si j 1 alors Ecrire les termes du tableau sont cons cutifs Sinon Ecrire les termes du tableau ne sont pas cons cutifs Finsi Fin 5 5 Examen d informatique L session de Juin 2005 Exercice 1 Ecrire un algorithme qui demande l ge d un enfant l utilisateur Ensuite il l informe de sa cat gorie e La cat gorie d un enfant est Poussin si lt age lt 8 e La cat gorie d un enfant est Pupille si 8 lt age lt 10 e La cat gorie d un enfant est Minime si 10 lt age lt 12 e La cat gorie d un enfant est Cadet si age 2 12 Exercice 2 1 Ecrivez un algorithme qui lit un entier n et compte le nombre de 1 dans la repr sentation binaire de cet entier 2 crivez un algorithme qui lit un entier n la taille du tableau le tableau d entiers T de n l ments l entier x et indique le nombre de fois que x figure dans le tableau T M El Marraki 50 31 03 2013 Algorithmique SMIA module M E2 3 Ecrivez une proc dure qui prend pour arguments un entier n la taille du tableau le tableau de r els T et affiche le plus grand l ment du tableau T ainsi que sa position dans le tableau On suppose que le tableau T est form d l ments tous distincts Exercice 3 Soit la fonction mystere crite en Maple suivante gt mystere proci L t local u i aS 0 for i from 1 to nops L do
11. 2 3 4 5 6 7 8 9 Ces instructions initialisent quatre tableaux de la mani re suivantes M El Marraki 37 31 03 2013 Algorithmique SMIA module M E2 T T2 T3 T 1 2 3 1 2 3 1 2 3 0 1 2 3 4 4 5 6 4 5 6 4 5 6 0 5 6 7 8 7 8 9 7 8 9 7 8 9 0 9 0 0 0 0 0 0 0 0 0 0 0 Remarque Rappelons que ces repr sentations rectangulaires sont tr s conventionnelles Dans la m moire de l ordinateur ces quatre tableaux sont plut t arrang s en lignes T gt 1234567809 T gt 1234567809 T gt 1230456078900000 T gt 1234567890000000 4 2 3 Lecture et criture d une matrice Lecture d une matrice variable Tableau matrice 10 10 i j n k entiers d but crire donner le nombre de ligne de la matrice lire n crire donner le nombre de colonne de la matrice lire k pour i allant de 1 n faire crire donner les l ments de la i ligne pour j allant de 1 k faire lire matrice i j finpour fipour fin Ecriture d une matrice variables Tableau Mat 10 10 i j n k entier d but pour i allant de 1 n faire pour j allant de 1 k faire crire Mat i j finpour crire n retour la ligne finpour fin 4 2 4 Exemples d utilisation d une matrice Somme de deux matrices constante N 20 variables Tableau A N INI BINIJIN CINIIN i j n entier d but crire donner la taille des matrices lt 20 M El Marraki 38 31 03 2013
12. C est de la glace et passe directement la fin sans tre ralenti par l examen d autres possibilit s qui sont forc ment fausses Cette deuxi me version n est donc pas seulement plus simple crire et plus lisible elle est galement plus performante l ex cution Les structures de tests imbriqu s sont donc un outil indispensable la simplification et l optimisation des algorithmes Exercices Exercice 10 Ecrivez un algorithme qui donne le maximum de trois nombres saisis au clavier Effectuez des tests pour 2 5 8 15 8 6 1 Exercice 11 Ecrivez un algorithme qui demande deux nombres l utilisateur et l informe ensuite si leur produit est n gatif positif ou nul attention on ne doit pas calculer le produit des deux nombres Exercice 12 crivez un algorithme qui permet de discerner une mention un tudiant selon la moyenne de ses notes Tr s bien pour une moyenne comprise entre 16 et 20 16 lt moyenne lt 20 Bien pour une moyenne comprise entre 14 et 16 14 lt moyenne lt 16 Assez bien pour une moyenne comprise entre 12 et 14 12 lt moyenne lt 14 Passable pour une moyenne comprise entre 10 et 12 10 lt moyenne lt 12 M El Marraki 23 31 03 2013 Algorithmique SMIA module M E2 Exercice 13 crivez un algorithme qui permet de r soudre une quation du second degr ax bx c 0aveca 0 Exercice 14 Les tudiants ayant pass l ex
13. E2 Exercice 1 1 2 crivez un algorithme qui effectue la lecture de trois nombres et affiche le plus grands de ces trois nombres crivez un algorithme qui effectue la lecture de n nombres ensuite affiche le plus grands de ces n nombres n saisie au clavier Correction I 14 solution chercher une solution avec le minimum de tests Nom maximum R le donne le maximum de trois nombres Entr e a b c nombres Sortie message Variables a b c nombres D but ecrire donner trois nombres lire a b c si a gt b alors si a gt c alors ecrire le maximum est a sinon ecrire le maximum est c finsi sinon si b gt c alors ecrire le maximum est b sinon ecrire le maximum est c finsi fin 2 solution Nom maximum R le donne le maximum de trois nombres Entr e a b c nombres Sortie max nombre Variables b c max nombres D but ecrire donner trois nombres lire a b c max a si b gt max alors max b finsi si c gt max alors max c finsi ecrire le maximum est max fin Nom maximum R le donne le maximum de trois nombres Entr e a nombre Sortie max nombre Variables a max nombres D but ecrire donner l entier n lire n ecrire donner le premier nombre lire max pour i allant de 2 n faire ecrire donner le i nombre lire a si a gt max alors max a finsi finpour ecrire
14. El Marraki 40 31 03 2013 Algorithmique SMIA module M E2 Conception Un programme qui demande la taille du tableau T les l ments du tableau T la valeur de x la valeur cherch e le programme donne la premi re position de x dans le tableau T si x est dans le tableau T et donne la valeur 1 si x n est pas dans le tableau T variables n i entier tableau T r el x r el d but crire donner la taille de T lirei n crire donner les n l ments de T pour i allant de 0 jusqu n 1 faire lire T i finpour crire donner la valeur de x lire x i 0 Tant que i lt n et T i x faire i amp i 1 fintantque si i lt n alors retourne i sinon retourne 1 fin Test e Sionprendn 10 T 1 9 2 0 3 5 2 4 11 1 et x 7 la fonction retourne 1 puisque 7 ne se trouve pas dans T e Sionprendn 10 T 1 9 2 0 3 5 2 4 11 1 et x 2 la fonction retourne 2 puisque T 2 2 la premi re position trouv e Recherche dichotomique On se place dans le cas o le tableau est ordonn et les l ments du tableau sont deux deux distincts Analyse x l ment recherch T tableau ordonn sans duplication n la taille du tableau le nombre d l ments du tableau mil indice du milieu du tableau si x T mil alors retourne mil sinon si x lt T mil alors recherche dans la 1 moiti du tableau T d mil 1 sinon recherche dans la 2 moiti
15. T Sra y b x x y FRERE pT Ye mer y x a tb y a tb b a x x y x a b a b y a donc tout va bien Le programme complet avec notre pseudo langage est Nom change entiers R le changer deux valeurs enti res Entr e x et y Sortie x et y Variables x y nombres Debut x E3 initialisation de x et y y 6 x x y y amp Ex y x x y Fin 3 1 2 Expression et op rateurs Expression Dans une instruction d affectation on trouve o gauche de la fl che un nom de variable o droite de la fl che ce qu on appelle une expression un ensemble de valeurs reli es par des op rateurs et quivalent une seule valeur o L expression situ e droite de la fl che doit tre du m me type que la variable situ e gauche Si l un des trois points num r s ci dessus n est pas respect la machine sera incapable d ex cuter l affectation et d clenchera une erreur M El Marraki 14 31 03 2013 Algorithmique SMIA module M E2 Op rateurs Un op rateur est un signe qui relie deux valeurs pour produire un r sultat o Op rateurs num riques Ce sont les quatre op rations arithm tiques addition soustraction x multiplication division Mentionnons galement le qui signifie puissance 45 au carr s crira donc 45 2 La multiplication et la division sont prioritaires sur l addition et la soustraction e 12 3 5e et 12
16. du tableau T mil 1 f finsi M El Marraki 41 31 03 2013 Algorithmique SMIA module M E2 finsi crire l l ment x n est pas dans T Conception variables n i d fy mil entier tableau T r el x r el d but crire donner la taille de T lire n crire donner les n l ments de T pour i allant de 0 jusqu n 1 faire lire T i finpour crire donner la valeur de x lire x d but da o f En 1 Tantque d lt f mil d f 2 si x T mil crire l l ment x est la position mil sinon si x lt T mil f mil 1 sinon d mil 1 finsi finsi fintantque crire l l ment x n est pas dans T fin Test Soit le tableau T 1 9 ordonn et sans r p tition suivant 0 1 2 3 4 5 6 7 8 2 6 8 11 17 18 22 45 102 On cherche l l ment 8 d 0 0 1 f 8 3 3 mil 4 1 2 Au d but d 0 f 8 comme d lt f on rentre dans la boucle Tantque mil 0 8 2 4 et comme x lt T mil 8 lt 17 onaf mil 1 f 3 d 0 puisque d lt f 0 lt 3 on reste dans la boucle Tantque etonamil 0 3 2 1etcomme x gt T mil 8 gt 6 donc d mil 1 2 et f 3 par cons quent d lt f 2 lt 3 alors on reste dans la boucle Tantque et mil 2 la x T mil 8 T 2 alors le programme affiche la valeur 2 qui est bien la position que occupe la valeur x 8 M El Marraki 42 31 03 2013 Algorithmique SMIA
17. e Abstraction par rapport au mat riel ind pendance application plate forme mat rielle e Interm diaire entre le langage machine binaire et le langage humain 1 3 2 Langages de programmation Le langage utilis par le processeur est appel langage machine Il s agit d une suite de 0 et de 1 du binaire Toutefois le langage machine est difficilement compr hensible par l humain Ainsi il est plus pratique de trouver un langage interm diaire compr hensible par l homme qui sera ensuite transform en langage machine pour tre exploitable par le processeur L assembleur est le premier langage informatique qui ait t utilis Celui ci est encore tr s proche du langage machine mais il permet d j d tre plus compr hensible Toutefois un tel langage est tellement proche du langage machine qu il d pend troitement du type de processeur utilis chaque type de processeur peut avoir son propre langage machine Ainsi un programme d velopp pour une machine ne pourra pas tre port sur un autre type de machine on d signe par le terme portable un programme qui peut tre utilis sur un grand nombre de machines Pour pouvoir l utiliser sur une autre machine il faudra alors parfois r crire enti rement le programme Il y a trois cat gories de langage de programmations les langages interpr t s et les langages interm diaires et les langages compil s Langage interpr t Un langage de programmation est par d finiti
18. et compr hensible par plusieurs personnes Il doit donc suivre des r gles pr cises il est compos d une ent te et d un corps l ent te qui sp cifie o le nom de l algorithme Nom o sonutilit R le o les donn es en entr e c est dire les l ments qui sont indispensables son bon fonctionnement Entr e o les donn es en sortie c est dire les l ments calcul s produits par l algorithme Sortie o les donn es locales l algorithmique qui lui sont indispensables D claration le corps qui est compos o du mot clef d but o d une suite d instructions indent es o du mot clef fin Le plus important pour un algorithme sont les d clarations ainsi que les instructions qui constituent le corps de l algorithme Il existe des instructions qui ne servent qu la clart de l algorithme l ordinateur les ignore compl tement ce sont les commentaires Un commentaire a la syntaxe suivante ceci est un commentaire Exemple voici le sch ma d un algorithme crit en notre pseudo langage Nom le nom de l algorithme R le que fait cet algorithme Facultatifs Entr e les donn es n cessaires Sortie les r sultats produits par l algorithme Variables la d claration des variables Debut Instruction 1 Instruction 2 He les commentaires explicatives des instructions Instruction k Fin M El Marraki 9 31 03 2013 Algorithmique SMIA
19. faire Si u gt v alors u u v Sinon v v u finsi FinTanQue crire u Fin 1 Donner les valeurs de u et v apr s chaque it ration dans le cas suivant u 24 v 14 2 Donner les valeurs de u et v apr s chaque it ration dans le cas suivant u 96 v 81 3 Que fait ce programme Exercice 3 4 5 points Soit T un tableau qui contient n valeurs r elles Ecrire un programme qui lit l entier n la taille de T le tableau T ensuite le programme affiche si les l ments du tableau T sont tous cons cutifs ou non Exemples 1 Soit le tableau T de 8 l ments 911011111213 14 151 16 Le programme affiche les l ments du tableau T sont cons cutifs 2 Soit le tableau T2 de 6 nombres 5110 40 66199112 Le programme affiche les l ments du tableau T ne sont pas cons cutifs Exercice 4 5 points Un nombre parfait est un entier positif sup rieur 1 gal la somme de ses diviseurs on ne compte pas comme diviseur le nombre lui m me Exemple 6 est un nombre parfait puisque 6 3 2 1 4 Donner un nombre parfait diff rent de 6 5 Ecrire un programme qui effectue la lecture d un entier n et affiche si n est parfait ou non M El Marraki 59 31 03 2013
20. puisque chaque ligne de la matrice est en effet un tableau donc une matrice nxk peut par exemple tre repr senter par n tableaux de k l ments chacun Mais cette repr sentation sera difficile g rer surtout si on veut impl menter un algorithme qui effectue la multiplication ou l addition de deux matrices L informatique nous offre la possibilit de d clarer des tableaux dans lesquels les valeurs ne sont pas rep r es par un indice seule mais par deux indices C est la solution notre probl me de repr sentation de matrice Un tel tableau se d clare ainsi tableau matrice 10 10 entier Cette d claration signifie r server un espace de m moire pour 10 x 10 entiers et quand j aurai besoin de l une de ces valeurs je les rep rerai par deux indices matrice i j est l ment de la matrice qui se trouve l intersection de la ligne i et la colonne j matrice 2 3 5 Cette instruction signifie mettre l emplacement qui se trouve l intersection de la deuxi me ligne avec la troisi me colonne la valeur 5 Dans la m moire l ordinateur repr sente un tableau matrice 10 10 par un seul tableau avec la taille 10x10 4 2 2 Initialisation de matrice Pour initialiser une matrice on peut utiliser par exemple les instructions suivantes Ti LS 3 1 2 3 4 5 63 7 8 9 T2 3 3 1 2 3 4 5 6 7 8 9 TslAILAI 1 2 3 4 5 63 7 8 9 7 Ta 4 4 1
21. 1 Affectation expression et op rateurs 3 1 1 Affectation D finition et notation L affectation est l action l mentaire dont l effet est de donner une valeur une variable ranger une valeur une place L affectation est r alis e au moyen de l op rateur ou en C et en Pascal Elle signifie prendre la valeur se trouvant du c t droit souvent appel e rvalue et la copier du c t gauche souvent appel e value Une rvalue repr sente toute constante variable ou expression capable de produire une valeur mais une lvalue doit tre une variable distincte et nomm e autrement dit il existe un emplacement physique pour ranger le r sultat Par exemple on peut affecter une valeur constante une variable A lt 4 mais on ne peut pas affecter quoi que ce soit une valeur constante elle ne peut pas tre une Ivalue on ne peut pas crire 4 A Exemple X lt 3 Signifie mettre la valeur 3 dans la case identifi e par X A l ex cution de cette instruction la valeur 3 est rang e en X nom de la variable La valeur correspond au contenu 3 La variable correspond au contenant X On peut repr senter la variable X par une boite ou case et quand elle prend la valeur 3 la valeur 3 est dans la case X el i On remarque qu une variable ne peut contenir un instant donn qu une seule valeur Utilisations Voici quelques effets d clench es par l utilisation de l affectation
22. 3 5 valent strictement la m me chose savoir 41 e En revanche 12 3 5 vaut 12 8 soit 96 o Op rateur alphanum rique amp Cet op rateur permet de concat ner deux cha nes de caract res Exemple Nom concat ner R le concat ner deux cha nes de caract res Entr e et B Sortie 2 G Variables A B C caract re D but A Bonjour B Tous le monde C lt A amp B Fin La valeur de C la fin de l algorithme est Bonjour Tous le monde 3 2 Lire et crire 3 2 1 Introduction Soit le programme suivant Variable enti re D but A 12 2 Fin Ce programme nous donne le carr de 12 soit 144 On remarque que o si l on veut le carr d un autre nombre que 12 il faut r crire le programme M El Marraki 15 31 03 2013 Algorithmique SMIA module M E2 o Le r sultat est calcul par la machine elle le garde pour elle et l utilisateur qui ex cute ce programme ne saura jamais quel est le carr de 12 C est pourquoi il faut utiliser des instructions qui permettent l utilisateur de dialoguer avec la machine 3 2 2 Donn es et r sultat Pour pouvoir effectuer un calcul sur une variable la machine doit conna tre la valeur de cette variable Si cette valeur n a pas t d termin e par des initiations ou des calculs pr c dents 1l faut que l utilisateur lui fournisse c est une donn e Il s agit alors d introduire une valeur partir de l e
23. Algorithmique SMIA module M E2 lire n lecture de la matrice A pour i allant de 1 n faire crire donner les l ments de la i ligne pour j allant de 1 n faire lire A i j finpour fipour lecture de la matrice B pour i allant de 1 n faire crire donner les l ments de la i ligne pour j allant de 1 n faire lire B i j finpour fipour la somme de C A B pour i allant de 1 n faire pour j allant de 1 n faire C i j A i j B i j finpour fipour affichage de la matrice de C pour i allant de 1 n faire pour j allant de 1 n faire crire C i j finpour crire n finpour retour la ligne fin Produit de deux matrices constante N 20 variables Tableau A N N BIN N CIN N i j k n S d but entier crire donner la taille des matrices lt 20 lire n emi lecture de la matrice A pour i allant de 1 n faire crire donner les l ments de la i ligne pour j allant de 1 n faire lire A i j finpour fipour pour i allant de 1 n crire donner les lecture de la matrice B faire l ments de la i ligne n faire pour j allant de 1 lire B i j finpour fipour le produit de C M El Marraki 39 A B 31 03 2013 Algorithmique SMIA module M E2 pour i allant de 1 n faire
24. Algorithmique SMIA module M E2 Universit Mohammed V Agdal Facult des Sciences Rabat D partement d Informatique Le module M E SMIA Algorithmique Par Pr Mohamed El Marraki marraki fsr ac ma 2012 2013 M El Marraki 1 31 03 2013 Algorithmique Sommaire 1 G n ralit s sur l Algorithmique Introduction L algorithmique Principe Les caract ristiques d un Algorithme Analyse descendante L algorithmique et la programmation Le but de la programmation Langages de programmation Pseudo langage 2 Les variables D claration des variables Noms de variables Types de variables 3 Les Primitives Affectation D finition et notation Utilisations Lire et crire Donn es et r sultats Les objets manipul s par l algorithme Les tests si alors si alors sinon Conditions compos es Organigramme Tests imbriqu s Les Boucles La boucle TantQue La boucle R p ter jusqu La boucle Pour jusqu Les boucles imbriqu es Une m thodologie pour l criture d une boucle 4 Les structures de donn es statiques Tableaux une dimension Introduction Notation et utilisation algorithmique Types pour les tableaux Quelques algorithmes utilisant les tableaux une dimension Tableaux deux dimensions Notation et d finitions Algorithmes sur les matrices 5 Exercices et Probl mes d examens M El Marraki 2 SMIA module M E2 31 03 2013 Algorithmiq
25. Allocation nom nombre type Dans la quelle il faut pr ciser le nom du tableau le nombre d l ments et le type des l ments allouer Notez que tant qu on n a pas pr cis le nombre d l ments d un tableau d une mani re ou d une autre ce tableau est inutilisable Il ne faut pas oublier de lib rer le tableau la fin de son utilisation avec l instruction Lib re nom Exemple on veut faire saisir des notes pour un calcul de moyenne mais on ne sait pas combien il y aura de notes saisir L algorithme sera variables tableau Note moyenne somme r els Ty n entiers d but crire entrer le nombre de notes saisir lire n allouer n nombres de types r els allocation Notes n r els saisir les notes crire entrer les n notes pour i allant de 0 n 1 faire M El Marraki 36 31 03 2013 Algorithmique SMIA module M E2 lire Note i finpour effectuer la moyenne des notes somme 0 pour i allant de 0 n 1 faire somme somme Note i finPour moyenne somme n affichage de la moyenne crire la moyenne des n notes est moyenne lib rer le tableau Notes lib re Notes fin Exercice 24 Refaire l Exercice 1 pr c dent en utilisant des tableaux dynamiques 4 2 Tableaux deux dimensions 4 2 1 Introduction Pour repr senter par exemple les matrices dans un ordinateur un tableau ne suffit pas
26. La primitive si C alors A sinon B finsi A pour effet de faire ex cuter A si C est satisfaite ou bien B dans la cas contraire C non satisfaite Une condition est une comparaison C est dire qu elle est compos e de trois l ments a une valeur a un op rateur de comparaison a une autre valeur Les valeurs peuvent tre a priori de n importe quel type num riques caract res Les op rateurs de comparaison sont lt gt lt gt L ensemble constitue donc si l on veut une affirmation qui a un moment donn est VRAIE ou FAUSSE A noter que ces op rateurs de comparaison s emploient tout fait avec des caract res Ceux ci sont cod s par la machine dans l ordre alphab tique les majuscules tant syst matiquement plac es avant les minuscules Ainsi on a t lt my VRAI Maman gt Papa FAUX maman gt Papa VRAI Conditions compos es Certains probl mes exigent parfois de formuler des conditions qui ne peuvent pas tre exprim es sous la forme simple expos e ci dessus Prenons le cas n est compris entre 5 et 8 En fait cette phrase cache non une mais deux conditions Car elle revient dire que n est sup rieur 5 et n est inf rieur 8 Il y a donc bien l deux conditions reli es par ce qu on appelle un op rateur logique le mot ET Comme on l a voqu plus haut l informatique met notre disposition trois op rateurs logiques ET OU et NON
27. Le ET a le m me sens en informatique que dans le langage courant Pour que C ET C3 soit VRAI il faut imp rativement que C soit VRAIE et que C2 soit VRAIE M El Marraki 20 31 03 2013 Algorithmique SMIA module M E2 Il faut se m fier un peu plus du OU Pour que C OU C soit VRAI il suffit que C soit VRAIE ou que C soit VRAIE Le point important est que si C est VRAIE et C2 est VRAIE alors C O C2 est VRAIE Le OU informatique ne veut donc pas dire ou bien VRAI NON FAUX On repr sente tout ceci dans des tables de v rit ET V F OU V F Exemple Probl me Etant donn s deux nombres entiers positifs identifier le plus grand des deux nombres Solution Analyse si A gt B alors le plus grand est A sinon le plus grand est B Conception Algorithme variables A B entiers d but crire Programme permettant de d terminer le plus grand de deux entiers positifs crire Entrer le premier nombre lire A crire Entrer le second nombre lire B si A gt B alors crire Le nombre le plus grand est A sinon crire Le nombre le plus grand est B finsi fin Organigramme M El Marraki 21 31 03 2013 Algorithmique SMIA module M E2 5g Te a Tests imbriqu s Graphiquement on peut tr s facilement repr senter un si comme un aiguillage de chemin de fer Un si ouvre donc deux voies correspond
28. TantQue Si S n alors Ecrire le nombre n est parfait Sinon Ecrire le nombre n n est pas parfait finsi Fin Exercice 3 1 mystere 35 12 a 35 2 11 b 12 1 1 r LL 0 La valeur affich e est 1 mystere 96 81 a 96 81 15 6 b 81 15 6 3 r 15 6 3 0 La valeur affich e est 3 mystere 34 21 a 34 21 13 8 5 3 2 b 21 13 8 5 3 2 1 rc r3 8 5 3 2 I 0 La valeur affich e est 1 2 Cet algorithme donne le plus grand commun diviseur le pgcd de deux nombres entiers a et b Exercice 4 l variables n i x T 20 entiers debut ecrire entrer la valeur de n lire n ecrire entrer le tableau T pour i allant de 1 n faire lire T i finpour ecrire entrer la valeur de x lire x i 1 TantQue i lt n et T i x faire i amp i 1 FinTantQue Si i lt n 1 alors Ecrire l l ment x se trouve dans le tableau T Sinon fin M El Marraki Ecrire l l ment x ne se trouve pas dans le tableau T finsi 49 31 03 2013 Algorithmique SMIA module M E2 2 Dans cette question on suppose que les variables n et T sont connues 1 version Variable i entier D but i 1 TantQue i lt n ET T i 1 T i 1 i atl FinTantQue Si i lt n alors Ecrire les termes du tableau ne sont pas cons cutifs Sinon Ecrire les termes du tableau sont cons cutifs FinSi Fin 2 version Variable i j entier D but Joe Pour i allant de 1 n
29. ables A B et C Ecrivez un algorithme transf rant A la valeur de B B la valeur de C et C la valeur de A quels que soient les contenus pr alables de ces variables Exercice 6 Ecrivez un algorithme qui calcule et affiche la surface et la circonf rence d un cercle 27 r et x r L algorithme demandera l utilisateur d entrer la valeur du rayon Exercice 7 Comment calculer le plus rapidement possible x Calculer x avec le minimum de multiplication Exercice 8 Ecrivez un algorithme qui calcule et affiche la surface et la circonf rence d un cercle 27 r et zr L algorithme demandera l utilisateur d entrer la valeur du rayon Exercice 9 crire un algorithme qui effectue la lecture du temps t en seconde et il affiche le temps t en jours heure minutes secondes Exemple si t 21020 secondes l algorithme affichera 0 jours 5 heures 50 minutes et 20 secondes M El Marraki 19 31 03 2013 Algorithmique SMIA module M E2 3 5 4 si alors si alors sinon Les primitives que nous allons pr senter maintenant vont permettre la machine de choisir les ex cutions suivant les valeurs des donn es Lors de l ex cution l algorithme la primitive si C alors A finsi O C est une condition on pr cisera plus loin la nature de cette condition et A une instruction ou une suite d instructions a pour effet de faire ex cuter A si et seulement si C est satisfaite
30. amen d algorithmique en session de Juin ont t class s selon leurs notes en trois cat gories pour une note inf rieure strictement 5 l tudiant est limin pour une note sup rieure ou gale 5 et inf rieur strictement 10 l tudiant passe la session de rattrapage pour une note sup rieure ou gale 10 l tudiant valide le module Ecrivez un algorithme qui demande l utilisateur d entrer la note du module puis affiche la situation de l tudiant selon sa note on suppose que l utilisateur entre une note valide entre 0 et 20 3 5 5 Les Boucles La notion d it ration boucle est une des notions fondamentales de l algorithmique On l utilise souvent quand on doit exercer plusieurs fois le m me traitement sur un m me objet ou plusieurs objets de m me nature Mais son r el int r t r side dans le fait que l on peut modifier chaque r p tition les objets sur lesquels s exerce l action r p t e Pour comprendre l int r t des boucles on se place dans un cas bien pr cis Prenons le cas d une saisie au clavier une lecture par exemple on pose une question laquelle l utilisateur doit r pondre par O Oui ou N Non Mais l utilisateur maladroit risque de taper autre chose que O ou N D s lors le programme peut soit planter par une erreur d ex cution parce que le type de r ponse ne correspond pas au type de la variable attendu soit se d rouler normalement j
31. ant deux traitements diff rents Mais il y a des tas de situations o deux voies ne suffisent pas Par exemple un programme devant donner l tat de l eau selon sa temp rature doit pouvoir choisir entre trois r ponses possibles solide liquide ou gazeuse Exemple Variable Temp entier D but crire Entrez la temp rature de l eau lire Temp si Temp lt 0 Alors crire C est de la glace finsi si Temp gt 0 Et Temp lt 100 Alors crire C est du liquide finsi si Temp gt 100 Alors crire C est de la vapeur finsi Fin Les tests successifs portent sur une la m me chose la temp rature la valeur de la variable Temp Il serait ainsi bien plus rationnel d imbriquer les tests de cette mani re M El Marraki 22 31 03 2013 Algorithmique SMIA module M E2 Exemple Variable Temp en Entier D but crire Entrez la temp rature de l eau lire Temp si Temp lt 0 Alors crire C est de la glace sinon si Temp lt 100 Alors crire C est du liquide sinon crire C est de la vapeur finsi finsi Fin Nous avons fait des conomies au niveau de la frappe du programme au lieu de devoir taper trois conditions dont une compos e nous n avons plus que deux conditions simples Mais aussi et surtout nous avons fait des conomies sur le temps d ex cution de l ordinateur Si la temp rature est inf rieure z ro celui ci crit dor navant
32. bles Lorsqu on d clare une variable il ne suffit pas de cr er une bo te r server un emplacement m moire il faut pr ciser ce que l on voudra mettre dedans car de cela d pendent la taille de la bo te l emplacement m moire et le type de codage utilis Types num riques classiques Commen ons par le cas tr s fr quent celui d une variable destin e recevoir des nombres Si l on r serve un octet pour coder un nombre on ne pourra coder que 2 256 valeurs diff rentes Cela peut signifier par exemple les nombres entiers de 1 256 ou de 0 255 ou de 127 128 Si l on r serve deux octets on a droit 2 65 536 valeurs avec trois octets 2 16 777 216 etc M El Marraki 10 31 03 2013 Algorithmique SMIA module M E2 Type Num rique Plage Octet de 0 255 Entier simple de 32768 32767 Entier double de 2147483648 2147483647 de 3 40x10 1 40x10 pour les n gatives de 1 40x10 3 40x10 R el simple S pour les positives R el double de LOTO 4 94x10 de 4 94x10 1 79x10 324 308 les n gatives les positives La syntaxe d une d claration de variable num rique en pseudo langage aura la forme Variable g Num rique Variables PrixHT TauxTVA PrixTTC Num rique Type alphanum rique On dispose donc galement du type alphanum rique galement appel type caract re t
33. comme c est le cas en langage C Donc attention Tab 2 est le troisi me l ment du tableau Tab tre un nombre entier Quel que soit le langage l l ment Tab 3 1416 n existe jamais tre inf rieure ou gale au nombre d l ments du tableau moins 1 Si le tableau Tab a t d clar comme ayant 10 l ments la pr sence dans une ligne sous une forme ou sous une autre de Tab 10 d clenchera automatiquement une erreur Remarques 1 2 La d claration tableau Tab 10 entier cr era un tableau Tab de 10 l ments le plus petit indice tant 0 et le plus grand indice est 9 Ne pas confondre l indice d un l ment d un tableau avec le contenu de cet l ment La premi re maison de la rue n a pas forc ment un habitant et la dixi me maison n a pas dix habitants En notation algorithmique il n y a aucun rapport entre i et Tab i Exercice 21 l Ecrivez un algorithme qui lit la taille n d un tableau T il saisi les n l ments du tableau T il effectue la somme des n l ments du tableau et il affiche cette somme Ecrivez un algorithme qui lit la taille n de deux tableaux T1 et T2 il effectue la lecture de ces deux tableaux ensuite il effectue la somme des tableaux T1 et T2 dans un tableau T et il affiche le tableau T Exemple pour n 8 T 4 5 8 2 5 6 0 5 T2 1 5 7 0 1 3 8 9 le tableau T obtenu est T 5 0 1 2 4 9 8 4 M El Marraki 35 31 03 2013 Alg
34. cutifs en m moire Il est donc possible d acc der un l ment d un tableau en temps constant pourvu que l on connaisse sa position ou indice Un tableau est donc une structure tr s simple et tr s efficace Il n est cependant pas possible de modifier la taille d un tableau ce qui est g nant pour un certain nombre d algorithmes On dit cette structure est statique Le nombre d l ments qu elle contient ne peut pas varier Dans notre exemple nous cr erons donc un tableau appel Note Et chaque note individuelle sera d sign e par Note i l l ment qui se trouve la position i Pour d clarer un tableau il faut pr ciser le nombre et le type de valeurs qu il contiendra Tableau Note 25 r els Cette d claration r serve l emplacement de 25 l ments de type r els Chaque l ment est rep r par son indice position de l l ment dans le tableau Dans la plus part des langages de programmation en particulier en langage C la premi re position porte le num ro 0 Dans notre exemple les indices vont de 0 24 Le premier l ment du tableau sera d sign par Note 0 le deuxi me par Note 1 le dernier par Note 24 L utilisation de Note 25 d clanchera une erreur On peut cr er des tableaux contenant des variables de tous types tableaux de num riques tableaux de caract res tableaux de bool ens tableaux de tout ce qui existe dans un langage donn comme type de variables Par contre on ne
35. d 1 entiers ecrire donner n lirei n M El Marraki 57 31 03 2013 Algorithmique SMIA module M E2 s 1 d 2 tant que d d lt n faire si n d 0 alors s s d n d finsi d lt ada i finTantque si s n alors ecrire n est parfait sinon ecrire n n est pas parfait finsi 4 6 Examen d Informatique juin 2011 Exercice 1 6 5 points I QCM 2 5 points Cocher la bonne r ponse 1 Le nombre d cimal 4321 est cod en base 16 par 1141 10E1 1E01 2 le nombre de bits n cessaire pour coder en binaire le nombre d cimal 3000 est 3 L entendu du codage sur 6 bits en binaire sign est compris entre Bik Bak 32 et 31 31 et 31 SE 4 Quelle est la valeur d cimale du nombre 100101101 crits en compl ment 1 5 Le plus grand nombre entier qu on peut coder en compl ment 2 sur 10 bits est 1023 BE SE II Codage 4 points 1 Coder les nombres entiers relatifs du tableau suivant sur 1 octet Nombre Binaire sign Compl ment 2 62a0 7600 M El Marraki 58 31 03 2013 Algorithmique SMIA module M E2 2 valuer le nombre r el en format IEEE 754 simple pr cision 1 10000100 00011100000000000000000 Exercice 2 4 points Soit le fragment de programme suivant variables u v entiers d but crire donner les valeurs de u et v lire u v TantQue u v
36. donc de copier le code voire de le M El Marraki 5 31 03 2013 Algorithmique SMIA module M E2 modifier Il y a donc risque de non respect des droits d auteur D autre part certaines applications s curis es n cessitent la confidentialit du code pour viter le piratage transaction bancaire paiement en ligne communications s curis es Exemples de langages compil s Le langage C Programmation syst me le langage C Programmation syst me objet le Cobol Gestion etc Langages interm diaires Certains langages appartiennent en quelque sorte aux deux cat gories pr c dentes LISP Java Python car le programme crit avec ces langages peut dans certaines conditions subir une phase de compilation interm diaire vers un fichier crit dans un langage qui n est pas intelligible donc diff rent du fichier source et non ex cutable n cessit d un interpr teur Les applets Java petits programmes ins r s parfois dans les pages Web sont des fichiers qui sont compil s mais que l on ne peut ex cuter qu partir d un navigateur Internet ce sont des fichiers dont l extension est class Toutefois peu pr s tous les langages de programmation sont bas s sur le m me principe Le programme est constitu d une suite d instructions que la machine doit ex cuter Celle ci ex cute les instructions au fur et mesure qu elle lit le fichier donc de haut en bas jusqu ce qu elle rencontre une instruction ap
37. e m et la somme des diviseurs de m est gale n on ne compte pas comme diviseur le nombre lui m me et 1 Exemple les nombres 48 et 75 sont deux nombres amis puisque Les diviseurs de 48 sont 2 3 4 6 8 12 16 24 et 2 3 4 6 8 12 16 24 75 Les diviseurs de 75 sont 3 5 15 25 et 3 5 15 25 48 Ecrire un algorithme qui permet de d terminer si deux entiers n et m sont amis ou non M El Marraki 32 31 03 2013 Algorithmique SMIA module M E2 4 Les structures de donn es statiques 4 1 Tableaux une dimension 4 1 1 Introduction Imaginons que dans un programme nous ayons besoin simultan ment de 25 valeurs par exemple des notes pour calculer une moyenne La solution consiste d clarer 25 variables r elles appel es par exemple n n2 n3 n2 et la variable moyenne r elle moyenne nitnotnsttnos 25 En programmation exemple langage C l ordinateur va r server 25 4 100 octets pour les valeurs r elles des 25 variables et 25 4 100 octets pour les adresses de ces 25 variables La programmation nous permet de rassembler toutes ces variables en une seule la note num ro 1 la note num ro 2 la note num ro 25 Un ensemble de valeurs portant ainsi le m me nom de variable et rep r es par un nombre s appelle un tableau et le nombre qui sert rep rer chaque valeur s appelle un indice Un tableau de taille n est une structure tr s simple constitu e de n emplacements cons
38. e m est gale n on ne compte pas comme diviseur le nombre lui m me et 1 Exemple les nombres 48 et 75 sont deux nombres amis puisque Les diviseurs de 48 sont 2 3 4 6 8 12 16 24 et 2 3 4 6 8 12 16 24 75 Les diviseurs de 75 sont 3 5 15 25 et 3 5 15 25 48 Ecrire un programme qui permet de d terminer si deux entiers n et m sont amis ou non Correction variables n m d p S1 S2 Entier debut ecrire entrer les entiers n et m lire n m s 0 s2 0 da 2 TantQue d d lt n faire Si n d 0 alors S1 S1 d n d finsi d da i FinTantQue p lt 2 TantQue p p lt m faire Si m p 0 alors S2 S2 p m p finsi pept FinTantQue Si S1 S2 alors Ecrire n et m sont amis Sinon Ecrire n et m ne sont pas amis fin Exercice 4 un nombre parfait Un nombre parfait est un entier positif sup rieur 1 gal la somme de ses diviseurs on ne compte pas comme diviseur le nombre lui m me Exemple 6 est un nombre parfait puisque 6 3 2 1 1 Donner un nombre parfait diff rent de 6 2 Donner l analyse de l algorithme correspondant la fonction parfait 3 Donner la conception de cet algorithme Correction 1 28 est un nombre parfait puisque 28 14 7 4 2 1 2 Pour un entier n donn on calcul ses diviseurs ainsi que la somme de ses diviseurs si la somme est gale n alors le nombre n est parfait sinon il ne l est pas 3k St
39. i on a pas d pass fin a etc Exemple Probl me On veut crire un algorithme qui affiche le message Bonjour tous 100 fois R solution Au lieu d crire l instruction crire Bonjour tous 100 fois On utilise plut t une boucle variable i enti re Pour i allant de 1 100 faire crire Bonjour tous finpour On peut am liorer ce programme par a ajouter un entier n le nombre de fois que le message s afficher l cran a afficher la variable i dans la boucle pour num roter les passages dans la boucle variable n i enti res crire entrer le nombre n M El Marraki 26 31 03 2013 Algorithmique SMIA module M E2 lire n Pour i allant de 1 n faire crire Bonjour tous la i fois finpour Dans la boucle pr c dente le 1 est incr ment automatiquement Si on d sire utiliser la boucle TantQue il faut incr menter le i soit m me variable n i enti res crire entrer le nombre n lire n ici TantQue i lt n faire crire Bonjour tous la i fois i amp 1 FinTantQue Des boucles imbriqu es De m me qu une structure SI ALORS peut contenir d autres structures SI ALORS une boucle peut contenir d autres boucles Variables i j entier Pour i allant de 1 10 crire Premi re boucle Pour j allant de 1 6 crire Deuxi me boucle Finpour Finpour Dans cet exemple le programme
40. ification etc o L exploitation d un fichier par une application se fait par l interm diaire du syst me d exploitation qui accomplit les op rations logiques de base suivantes ouvrir fermer un fichier lire crire dans un fichier o L utilisateur peut cr er d truire organiser lire crire modifier et copier des fichiers ou des enregistrements qui les composent 1 3 4 La d marche de programmation et analyse descendante La r solution d un probl me passe par toute une suite d tapes e Phase d analyse et de r flexion algorithmique e Phase de programmation choisir un langage de programmation traduction de l algorithme en programme programme ou code source compilation traduction du code source en code objet traduction du code objet en code machine ex cutable compr hensible par l ordinateur e Phase de test e Phase d ex cution Compilation Programme binaire av nntahla M El Marraki 7 31 03 2013 Algorithmique SMIA module M E2 Le travail est ici surtout bas sur l analyse du probl me et l criture de l algorithme La r alisation d un programme passe par l analyse descendante du probl me il faut r ussir trouver les actions l mentaires qui en partant d un environnement initial nous conduisent l tat final L analyse descendante consiste d composer le probl me donn en sous probl mes et ainsi de suite jusqu descendre au niveau des primitives Les
41. l tudiant est limin pour une note sup rieure ou gale 5 et inf rieur strictement 10 l tudiant passe la session de rattrapage pour une note sup rieure ou gale 10 l tudiant valide le module Ecrivez un algorithme qui demande l utilisateur d entrer la note du module puis affiche la situation de l tudiant selon sa note on suppose que l utilisateur entre une note valide entre 0 et 20 Exercice 2 4 points Un nombre parfait est un entier positif sup rieur 1 gal la somme de ses diviseurs on ne compte pas comme diviseur le nombre lui m me Exemple 6 est un nombre parfait puisque 6 3 2 1 l Donner un nombre parfait diff rent de 6 2 Ecrire la conception de l algorithme qui nous dit si un entier n est parfait ou non Exercice 3 5 points Soit la fonction mystere crite en Maple suivante mystere proc a b local r while gt 0 do r irem a b a b b T I o od a end 1 Que valent mystere 35 12 mystere 96 81 et mystere 34 21 donner les valeurs que prennent les variables a b et r dans chacun des cas 2 Que fait ce programme M El Marraki 47 31 03 2013 Algorithmique SMIA module M E2 N B la fonction Maple irem x y retourne le reste de la division de x par y Exercice 4 7 points 1 crivez un algorithme qui lit la taille d un tableau n le tableau T une valeur x et il indique ensuite si l ment x appartient ou n
42. module M E2 Exercice 32 Soit le tableau T 0 10 ordonn et sans r p tition suivant 2 3 5 7 10 17 19 23 50 62 70 1 Chercher l l ment 3 dans le tableau T par dichotomie 2 Chercher l l ment 19 dans le tableau T par dichotomie 3 Chercher l l ment 56 dans le tableau T par dichotomie 5 Exercices et Probl mes d examens 5 1 Examen d informatique L session de Juin 2004 Enonc s des exercices Exercice 1 Ecrivez un algorithme qui demande l utilisateur d entrer la temp rature de l eau et affiche ensuite l tat de l eau selon la temp rature on rappelle que l tat de l eau est glace pour une temp rature inf rieure ou gale 0 est vapeur pour une temp rature sup rieure ou gale 100 et liquide pour une temp rature comprise strictement entre 0 et 100 Exercice 2 1 Ecrivez un algorithme qui lit un entier n et compte le nombre de 1 dans la repr sentation binaire de cet entier 2 crivez un algorithme qui lit un tableau d entiers de n l ments et donne la plus grande et la plus petite valeur de ce tableau Exercice 3 Soit la fonction mystere crite en Maple suivante mystere proc n tocar Tist e x i 3 P E aa 1 E liste NULL i 2 while i lt x do if irem x i 0 then x x i liste liste i else i i l ET od liste end 1 Que valent mystere 8 mystere 90 et mystere 210 justifier par un tableau de va
43. mplantation la plus efficace d un algorithme mois que ce dernier ne soit susceptible d tre utilis pour une t che tr s r p titive Dans les autres cas une mise en uvre simple conviendra souvent on pourra tre s r que le programme fonctionnera peut tre cinq ou dix fois moins vite que la version la plus optimis e ce qui se traduira ventuellement par quelques secondes suppl mentaires l ex cution En revanche un mauvais choix d algorithme peut entra ner une diff rence d un facteur cent mille ou plus ce qui se traduira en minutes en heures voir en jours au niveau des temps d ex cution Les caract ristiques d un Algorithme Un algorithme est une marche suivre 1 dont les op rations sont toutes d finies et portent sur des objets appel s informations 2 dont l ordre d ex cution des op rations est d fini sans ambigu t 3 quiest r put e r soudre de mani re certaine un probl me ou une classe de probl mes 4 s exprime dans un langage ind pendant des langages de programmation 13 L algorithmique et la programmation Un programme est la traduction d un algorithme dans un certain langage de programmation Il faut savoir qu chaque instruction d un programme correspond une action du processeur M El Marraki 4 31 03 2013 Algorithmique SMIA module M E2 1 3 1 Le but de la programmation e Utiliser l ordinateur pour traiter des donn es afin d obtenir des r sultats
44. nn e prochaine Correction Nom Foot Role donne la situation d une quipe en fonction de son classement Entr e n un entier compris entre 1 et 16 Sortie un message Variables n entier Debut crire donner votre classement entre 1 et 16 lire n M El Marraki 51 31 03 2013 Algorithmique SMIA module M E2 si n lt 0 alors crire faux classement else si n lt 2 alors crire l quipe ira la ligue des champions africaine else si n lt 4 alors crire l quipe ira la ligue des champions arabe else si n lt 14 alors crire l quipe restera en premi re division else crire l quipe jouera en deuxi me division finsi finsi finsi finsi fin Exercice 2 10 points 1 a crivez une fonction fact qui prend pour argument un entier k et retourne le factoriel de k b crivez une proc dure qui effectue la lecture d un entier n calcule et affiche la somme des factoriels des entiers de 0 n 2 utiliser la fonction fact pr c dente 2 Ecrivez une fonction qui prend en argument un entier n et retourne le nombre de 1 dans la repr sentation binaire de l entier n 3 crivez une proc dure qui lit un entier n la taille du tableau le tableau d entiers T de n l ments l entier x et indique le nombre de fois que x figure dans le tableau T Correction 1 a 2 points fonction fact n entier entier var f i entie
45. ntiers crire donner la valeur de N lire N si N lt 0 alors erreur initialiser somme et i R p ter somme somme i ic i 1 jusqu i gt N crire la somme est somme d claration des variables N i somme entiers crire donner la valeur de N lire N si N lt 0 alors erreur initialiser somme et i TantQue i lt N somme somme i ic i 1 FinTantque Ecrire la somme est somme d claration des variables N i somme entiers M El Marraki 28 31 03 2013 Algorithmique SMIA module M E2 crire donner la valeur de N lire N si N lt 0 alors erreur initialiser somme et i Pour i allant de 1 N somme somme i FinPour Ecrire la somme est somme 3 tape Test Somme N entiers Donner N 1 N doit etre gt 0 Somme N entiers Donner N 7845 La somme est 30775935 Somme N entiers Donner N 10 La somme est 55 Remarque Pour cet exemple on peut faire une v rification plus compl te en calculant une autre variable sommel N N 1 2 qui est la somme 1 2 3 N et la compar e somme ensuite afficher le r sultat de la comparaison M thodologie pour l criture d une boucle gt rep rer une action r p titive donc une boucle gt choix entre boucle avec compteur ou sans Question Peut on pr voir d terminer le nombre d it rations a si oui boucle avec compteur la boucle pour a sinon boucle sans compteur Est ce que il faut commence
46. ntrer la valeur de n 0 Pour coder 0 en binaire il faut 0 bits Erreur Am lioration Variables i n nb entiers Debut Ecrire Entrer la valeur de n lire n i n 2 Pour le cas de z ro nb 1 TantQue i lt gt 0 faire i i 2 nb nb 1 FinTantQue Ecrire Pour coder n en binaire il faut nb bits Fin Impl mentation en langage C include lt stdio h gt void main ine L nnb printf Entrer la valeur de n scanf d amp n isn nb 0 while i 0 i i 2 Il e M El Marraki 30 31 03 2013 Algorithmique SMIA module M E2 nb nb 1 printf Pour coder d en binaire il faut d bits n n nb 3 6 Exercices Exercice 15 1 crivez un algorithme qui affiche 100 fois la phrase je ne dois pas arriver en retard en classe 2 crivez un algorithme qui affiche les entiers de 1 100 3 crivez un algorithme qui affiche les entiers pairs de 1 100 Exercice 16 1 crivez un algorithme qui calcule la somme des n premiers nombres entiers positifs L algorithme demandera l utilisateur d entrer la valeur de n 2 crivez un algorithme qui calcule la somme des n premiers nombres entiers positifs paires L algorithme demandera l utilisateur d entrer la valeur de n Exercice 17 1 Ex cuter le programme suivant Variable i j Entier debut Pour i amp 1 jusqu 5 Ecrire i i Pour j lt 1 jusq
47. oc de au m me examen et ainsi de suite On ne s arr te que lorsque la condition prend la valeur FAUX Illustration avec notre probl me de contr le de saisie Variable Rep en Caract re Ecrire Voulez vous un caf O N TantQue Rep O ET Rep N Lire Rep Si Rep O ET Rep N Alors Ecrire Saisi rron e Recommencez FinsSi FinTantQue La boucle R p ter jusqu Le sch ma de la boucle r p ter est R p ter Instructions jusqu conditions Le principe est simple toutes les instructions crites entre R p ter et jusqu sont ex cut es au moins une fois et leur ex cution est r p t e jusqu ce que la condition plac e derri re jusqu soit satisfaite Illustration avec notre probl me de contr le de saisie M El Marraki 25 31 03 2013 Algorithmique SMIA module M E2 Variable Rep en Caract re Ecrire Voulez vous un caf O N R p ter Lire Rep Si Rep O ET Rep N Alors Ecrire Saisi rron e Recommencez FinsSi Jusqu Rep O OU Rep N La boucle Pour jusqu Cette boucle est utile surtout quand on conna t le nombre d it rations effectuer Le sch ma de la boucle Pour est Pour i allant de d but jusqu fin Instructions FinPour Le principe est simple a oninitialise i par d but a on test si on a pas d pass fin a on ex cute les instructions a onincr mente i i amp i 1 a on test s
48. on Entr e AetB Sortie C variables B C entiers D but crire entrer la valeur de A lire A crire entrer la valeur de B lire B C CE Arsip crire le produit de A et B est C Fin Ex cution entrer la valeur de A 12 entrer la valeur de B 11 le produit de 12 est de 11 est 132 3 2 5 Exercices Exercice 1 Quelles seront les valeurs des variables A B et C apr s ex cution des instructions suivantes Variables A B C Entier D but ACB B 2 C lt A 8B A 4 C lt B 2A Fin Exercice 2 Quelles seront les valeurs des variables A et B apr s ex cution des instructions suivantes Variables B Entier D but A 2 B lt A S A lt A B B B 2 A lt B A Fin M El Marraki 18 31 03 2013 Algorithmique SMIA module M E2 Exercice 3 Que produit l algorithme suivant Variables B Entier D but crire entrer la valeur de A lire A crire entrer la valeur deB lirei B A lt A B B lt A B A lt B crire A A crire B B Fin Exercice 4 Que produit l algorithme suivant Variables A B C cha ne de caract res D but A amp 423 B 12 CEARB crire C C Fin Exercice 5 1 Ecrire un algorithme permettant d changer les valeurs de deux variables A et B et ce quel que soit leur contenu pr alable 2 On dispose de trois vari
49. on au tableau T 2 crivez un algorithme qui permet de d terminer si les l ments d un tableau d entiers sont tous cons cutifs ou non Par exemple si le tableau est 7 8 9 10 ses l ments sont tous cons cutifs Si le tableau est 7 9 10 11 ses l ments ne sont pas tous cons cutifs 5 4 Correction de l examen d informatique 12 session juillet 2004 Exercice 1 1 version Variables note r el D but Ecrire Entrez la note du module Lire note Si note lt 5 alors Ecrire l tudiant est limin Sinon Si note lt 10 alors Ecrire l tudiant passe en rattrapage Sinon Ecrire l tudiant a valid le module Finsi Finsi Fin 2 version Variables note r el D but Ecrire Entrez la note du module Lire note Si note lt 5 alors Ecrire l tudiant est limin Finsi Si note gt 5 et note lt 10 alors Ecrire l tudiant passe en rattrapage Finsi Si note gt 10 alors Ecrire l tudiant a valid le module Finsi Fin Exercice 2 1 Le nombre 28 est parfait puisque 28 14 4 7 2 1 2 solution Variables n d S entier D but Ecrire Entrez la valeur de n Lire n S lt 1 M El Marraki 48 31 03 2013 Algorithmique SMIA module M E2 da 2 TantQue d d lt n Si n d 0 alors S S d n d finsi d amp d Fin
50. on diff rent du langage machine Il faut donc le traduire pour le rendre intelligible du point de vue du processeur Un programme crit dans un langage interpr t a besoin d un programme auxiliaire l interpr teur pour traduire au fur et mesure les instructions du programme Exemples de langages interpr t s Le langage HTML les pages web le langage Maple calcul math matique Prolog Intelligence artificielle etc Langage compil Un programme crit dans un langage dit compil va tre traduit une fois pour toutes par un programme annexe le compilateur afin de g n rer un nouveau fichier qui sera autonome c est dire qui n aura plus besoin d un programme autre que lui pour s ex cuter on dit d ailleurs que ce fichier est ex cutable Un programme crit dans un langage compil a comme avantage de ne plus avoir besoin une fois compil de programme annexe pour s ex cuter De plus la traduction tant faite une fois pour toute il est plus rapide l ex cution Toutefois il est moins souple qu un programme crit avec un langage interpr t car chaque modification du fichier source il faudra recompiler le programme pour que les modifications prennent effet D autre part un programme compil a pour avantage de garantir la s curit du code source En effet un langage interpr t tant directement intelligible lisible permet n importe qui de conna tre les secrets de fabrication d un programme et
51. orithmique SMIA module M E2 Exercice 22 1 Ecrivez un algorithme qui permet l utilisateur de saisir les notes d une classe ensuite il renvoie le nombre de ces notes sup rieures la moyenne de la classe 2 Ecrivez un algorithme qui permet l utilisateur de saisir un tableau de taille n et d afficher le plus grand et le plus petit l ment du tableau Exercice 23 Que produit l algorithme suivant Variable Tableau F 10 i entier d but F 0 1 F 1 1 crire F 0 F 1 pour i allant de 2 10 faire Fi F i 1 F i 2 crire F il finpour fin 4 1 4 Les tableaux dynamiques Il arrive fr quemment que l on ne connaisse pas l avance le nombre d l ments que devra comporter un tableau Bien s r une solution consisterait d clarer un tableau gigantesque 10 000 l ments pour tre s r que a rentre Mais d une part on n en sera jamais parfaitement s r si le nombre n des l ments du tableau d passe 10 000 a provoquera une erreur d autre part en raison de l immensit de la place m moire r serv e la plupart du temps non utilis e c est un g chis qui affectera la taille de notre algorithme ainsi que sa rapidit Pour r soudre ce probl me on a la possibilit de d clarer le tableau sans pr ciser au d part son nombre d l ments Ce n est que dans un second temps au cours du programme que l on va fixer ce nombre via une instruction d allocation
52. ors Ecrire C est de la vapeur finsi Fin Exercice 2 sur 7 points 1 Variables i n poids entiers Debut Ecrire Entrer la valeur de n lire n in poids 0 M El Marraki 44 31 03 2013 Algorithmique SMIA module M E2 TantQue i lt gt 0 faire si i mod 2 1 alors poids poids 1 finsi i i 2 FinTantQue Ecrire poids Fin 2 variables Tableau Tab 100 i n min max Entier debut ecrire donner la taille du tableau lire n ecrire donner les l ments du tableaux Pour i allant de 1 n faire lire Tab i FinPour min Tabl1 max Tabl1 Pour i allant de 2 n faire si min gt Tabli l alors min Tabli finsi si max lt Tabli l alors max Tabli finsi FinPour Ecrire le minimum est min Ecrire le maximum est max fin Exercice 3 sur 6 5 points 1 mystere 8 X 8 4 2 J i 2 2 2 2 liste 2 DD 22 mystere 90 X 90 45 45 15 5 5 5 1 i 2 2 3 3 5 4 5 5 liste 2 2 2 3 23 3 PAPE ee PRES 2r Pere mystere 210 X 210 105 105 35 35 35 7 J T 1 i 2 2 3 3 4 5 5 6 7 7 liste 2 2 2 311 2 841n2 8411023875 142 3 5 1112 35 12 8 54 2 Ce programme donne la liste des diviseurs premiers d un entier n M El Marraki 45 31 03 2013 Algorithmique SMIA module M E2 3 En rempla ant l instruction i 2 par l instruction i
53. pel e parfois instruction de branchement qui lui indique d aller un endroit pr cis du programme Il s agit donc d une sorte de jeu de piste dans lequel la machine doit suivre le fil conducteur et ex cuter les instructions qu elle rencontre jusqu ce qu elle arrive la fin du programme et celui ci s arr te Historique des langages e Langage de bas niveau proche du langage machine Jusqu en 1945 langage binaire 1950 langage assembleur e Langage de haut niveau proche des langages naturels Depuis 1955 Programmation proc durale Fortran Cobol Basic Pascal C Ada Programmation orient objet SmallTalk C Delphi Java Programmation logique Prolog Et beaucoup d autres e Evolution o Programmation imp rative fonction Exemples Pascal C o Programmation orient e objet POO Exemples SmallTalk Java C M El Marraki 6 31 03 2013 Algorithmique SMIA module M E2 1 3 3 La notion de fichier Dans un programme les instructions et donn es r sident en m moire centrale pour tre ex cut es Les programmes et les donn es sont sauvegard es dans des fichiers qui portent des extensions sp cifiques du langage o Les donn es et les programmes sont stock s dans des fichiers o Un fichier est identifi par un nom et une extension fichier doc pgcd c texte tex etc o Un fichier est caract ris par des attributs taille date de cr ation date de mod
54. peut pas faire un mixage de types diff rents de valeurs au sein d un m me tableau L norme avantage des tableaux c est qu on va pouvoir les traiter en faisant des boucles Par exemple pour effectuer notre calcul de moyenne cela donnera par exemple 4 1 2 Exemple Voici un programme qui comporte la d claration d un tableau de 25 r els les notes d une classe on commence par effectuer la saisie des notes et en suite on calcul la moyenne des 25 notes et on affiche la moyenne M El Marraki 33 31 03 2013 Algorithmique SMIA module M E2 variables tableau Note 25 i somme entier moyenne r el d but saisir les notes pour i allant de 0 24 faire ecrire entrer une note lire Note i finpour effectuer la moyenne des notes somme 0 pour i allant de 0 24 faire somme somme Noteli finPour moyenne somme 25 affichage de la moyenne ecrire la moyenne des notes est moyenne fin Ex cution ntrer une not T2 ntrer une not 10 5 ntrer une not 14 ntrer une note 08 la moyenne des notes est 11 75 Une am lioration Constante Max 200 variables tableau Note Max i somme n entier moyenne r el d but crire entrer le nombre de notes lire n saisir les notes ecrire entrer les n notes pour i allant de 0 n 1 faire lire Notelil finpour effectuer la moyenne des notes somme 0 pour i allan
55. programme 3 On remarque que pour calculer s i on besoin que de s i 1 et s i 2 comment am liorer cette fonction crire une fonction qui n utilise pas de liste s Correction 1 surlpoint mystere 10 0 1 1 2 3 5 8 13 21 34 2 sur 0 5 point cette proc dure calcule les termes de la suite de Fibonacci 3 fonction Fibo n entier variables i n u v w entiers d but si n 1 alors crire 0 si n 2 alors crire 1 i 3 TantQue i lt n faire crire u w lt v v u y u w i i 1 FinTantQue Fin Exercice 4 3 points On d sire crire un algorithme qui affiche l image miroir n d un nombre entier n Exemple l image miroir du nombre n 54321 est n 12345 1 Analyse expliquer comment extraire partir de l entier n les chiffres qui le compose 2 Ecrire une conception de l algorithme qui lit un entier n et affiche son image miroir Correction 1 Pour extraire les chiffres qui composent un entier n il suffit de r p ter les deux instructions suivantes r n mod 10 n n 10 2 nom miroir r les affichage de l image miroir d un entier entr e n entier sortie les chiffres qui composent n variables n i r entier d but crire Entrer un entier lire n tanque n lt gt 0 faire r n mod 10 crirei r n n 10 fintantque fin M El Marraki 54 31 03 2013 Algorithmique SMIA module M
56. ques nombres ou caract res x et y ayant respectivement comme valeur a et b quelles sont les affectations qui donneront x la valeur b et y la valeur a Analyse la premi re id e est d crire x y y x Mais a ne marche pas les deux variables se retrouvent avec la m me valeur b Il faut mettre la valeur de x de cot pour ne pas la perdre on utilise une variable auxiliaire z et on crit les instructions suivantes re DRE A Ey yE Le programme complet avec notre pseudo langage est Nom change R le changer deux valeurs Entr e x et y Sortie x et y Variables x y z quelconques Debut x E3 initialisation de x et y y 6 AE ee lt on stocke la valeur de x dans z x y on peut maintenant crire dans x y z on remet l ancien contenu de x dans y Fin M El Marraki 13 31 03 2013 Algorithmique SMIA module M E2 V rification 1l s agit de v rifier que l algorithme donne bien la solution voulu Ecrivant apr s chaque instruction les valeurs des variables X Y et Z x 3 Mg 3 y 2 u y 6 x 3 y 6 zZ n z x Yox 3 y 6 Z 3T x y x 6 y 6 z 3 y z x 6 y 3 z 3 donc tout va bien Autre m thode s il s agit de nombres entiers nous pouvons nous passer d une variable auxiliaire mais en utilisant les primitives additionner et soustraire x a x a y j y amp b
57. r debut fe ici tantque i lt n faire ECExi i amp i 1 fintantque retourne f fin b 2 points nom somme factorielle r le calcule de gt entr e n entier sortie S entier variable n S i entiers debut crire donner n lire n M El Marraki 52 31 03 2013 Algorithmique SMIA module M E2 s amp o i 1 tanque i lt n faire s amp sS fact i i amp i 1 fintanque crire la somme est S fin 2 sur3points fonction poids n ntier ntier variables i n poids entiers d but i tn poids 0 TantQue i lt gt 0 faire si i mod 2 1 alors poids poids 1 i i 2 FinTantQue Ecrire poids Fin 3 sur 3 points variables Tablea debut i u Tab 100 ecrire donn lirein ecrire donn r les l m er la taille du tableau Fo ap Ry E entier se Pour i allan lire Tab i nts du tableaux son t de 1 n faire finsi FinPour ecrire donner x lire x c o Pour i allant de 0 n 1 faire si x Tabli l alors c 1 FinPour Ecrire le mombre de x fin Exercice 3 4 points est T Soit la fonction mystere crite en Maple suivante gt mystere proc n local s 13 s 0 1 1 3 while i lt n do S s sfi 1 s i 2 i itl od s end 1 Que valent mystere 10 M El Marraki 53 31 03 2013 Algorithmique SMIA module M E2 2 Que fait ce
58. r l action avant de tester ou l inverse si tester d abord alors boucle TantQue si action puis tester alors R p ter jusqu gt crire l action r p titive et l instruction de boucle choisie Question Faut il pr parer les donn es l it ration suivante si oui compl ter le corps de boucle gt initialiser les variables utilis es si n cessaires gt crire les conditions d arr t voire l incr mentation de la variable de contr le gt ex cuter pour les cas extr mes et au moins un cas normal 3 6 Exemple Ecrire l algorithme qui compte le nombre de bits n cessaires pour coder en binaire un entier n Le nombre de bits n cessaire pour coder l entier n est Ig n l entier juste au dessus du M El Marraki 29 31 03 2013 Algorithmique SMIA module M E2 logarithme base 2 de l entier n Analyse on initialise une variable nb 0 et chaque fois que l on divise n par 2 on augment de 1 la valeur de nb on r p te ce proc d jusqu ce que le quotient obtenu est nul L algorithme Variables i n nb entiers Debut Ecrire Entrer la valeur de n lire n En nb 0 TantQue i lt gt 0 faire i i 2 nb nb 1 FinTantQue Ecrire Pour coder n en binaire il faut nb bits Fin Ex cution Entrer la valeur de n 13 Pour coder 13 en binaire il faut 4 bits Entrer la valeur de n 1750 Pour coder 1750 en binaire il faut 11 bits E
59. riables 2 Que fait ce programme M El Marraki 43 31 03 2013 Algorithmique SMIA module M E2 3 Que se passera t il si on remplace l instruction i 2 par i 1 7 N B la fonction Maple irem x y retourne le reste de la division de x par y et x y d signe la division enti re de x par y Exercice 4 Deux nombres entiers n et m sont qualifi s d amis si la somme des diviseurs de n est gale m et la somme des diviseurs de m est gale n on ne compte pas comme diviseur le nombre lui m me et 1 Exemple les nombres 48 et 75 sont deux nombres amis puisque Les diviseurs de 48 sont 2 3 4 6 8 12 16 24 et 2 3 4 6 8 12 16 24 75 Les diviseurs de 75 sont 3 5 15 25 et 3 5 15 25 48 Ecrire un algorithme qui permet de d terminer si deux entiers n et m sont amis ou non 5 2 Correction de l examen d informatique 1 session Juin 2004 Exercice 1 sur 4 points Variable Temp Entier D but Ecrire Entrez la temp rature de l eau Lire Temp Si Temp lt 0 Alors Ecrire C est de la glace Sinon Si Temp lt 100 Alors Ecrire C est du liquide Sinon Ecrire C est de la vapeur finsi finsi Fin 2 solution mauvaise Variable Temp Entier D but Ecrire Entrez la temp rature de l eau Lire Temp Si Temp lt 0 Alors Ecrire C est de la glace finsi Si Temp gt 0 Et Temp lt 100 Alors Ecrire C est du liquide finsi Si Temp gt 100 Al
60. t d une machine pour fonctionner aussi bien sur toutes les machines ou presque Ainsi ce n est pas le programme mais la m thode qu il faut tudier pour comprendre comment traiter le probl me Le terme algorithme est employ en informatique pour d crire une m thode de r solution de probl me programmable sur machine Les algorithmes sont la mati re de l informatique et sont l un des centres d int r t de la plupart sinon la totalit des domaines de cette science 1 2 L algorithmique Principe D finition Un algorithme est une s quence bien d finie d op rations calcul manipulation de donn es etc permettant d accomplir une tache en un nombre fini de pas En principe un algorithme est ind pendant de toute implantation Cependant dans la pratique de la programmation il s av re indispensable de tenir compte des capacit s du langage de programmation utilis La conception d un algorithme passe par plusieurs tapes Analyse d finition du probl me en terme de s quences d op rations de calcul de stockage de donn es etc Conception d finition pr cise des donn es des traitements et de leur s quencement Implantation traduction et r alisation de l algorithme dans un langage pr cis Test V rification du bon fonctionnement de l algorithme Remarque Les programmes sont souvent sur optimis s Il n est pas toujours indispensable de se donner la peine de trouver l i
61. t de 0 n 1 faire somme somme Noteli finPour moyenne somme 25 affichage de la moyenne ecrire la moyenne des n notes est moyenne fin Remarque A la compilation la constante Max sera remplac e par le nombre 200 Ici le nombre de note n est pas fix 25 mais il est seulement inf rieur 200 M El Marraki 34 31 03 2013 Algorithmique SMIA module M E2 M me si on donne n la valeur 10 l ordinateur r server quand m me la place pour 200 variables de types r els La saisie des notes est aussi am lior e puisque on rentre sur la m me ligne toutes les notes Attention si n 10 il faut rentrer 10 valeurs r elles s parer par un espace si vous rentrez moins de dix valeurs l ordinateur restera bloquer et attend que vous rentrer les dix valeurs attendues Si au contraire vous rentrez 11 valeurs au lieu de 10 l ordinateur affectera les10 premi res valeurs au tableau Note et gardera la 11 i me valeur pour une prochaine lecture ce qui provoquera peut tre une erreur 4 1 3 Les caract ristiques de l indice d un tableau L indice qui sert parcourir les l ments d un tableau peut tre exprim directement comme un nombre ou une variable La valeur d un indice doit toujours tre gale au moins 0 dans le langage Pascal le premier l ment d un tableau porte l indice 1 Mais nous avons choisi ici de commencer la num rotation des indices z ro
62. u 3 Ecrire le produit de i et j est i j FinPour FinPour Fin 2 Ex cuter le programme suivant Variable i j Entier debut Pour i lt 1 jusqu 5 Ecrire i i FinPour Pour j lt 1 jusqu 3 Ecrire le produit de i et est 1i FinPour Fin Exercice 18 1 crivez un algorithme qui calcule la somme S suivante Se I 224 32 4 n 1 nn L algorithme demandera l utilisateur d entrer la valeur de n M El Marraki 31 31 03 2013 Algorithmique SMIA module M E2 2 crivez un algorithme qui calcule le factoriel de n n 1x2x3x x n 1 x n L algorithme demandera l utilisateur d entrer la valeur de n Exercice 19 Soit l algorithme suivant variables a b r entiers d but crire donner les valeurs de a et b lire a b TantQue b gt 0 faire r asb a b reste de la division de a par b a b b r FinTanQue crire a Fin 1 Ex cuter l algorithme afficher dans un tableau les valeurs de a b et r pour a a 50 et b 45 bi a 21 et b 13 on a 96 et b 81 2 Que fait l algorithme pr c dant Exercice 20 1 Un nombre entier p diff rent de 1 est dit premier si ses seuls diviseurs positifs sont 1 et p Ecrivez un algorithme qui effectue la lecture d un entier p et d termine si cet entier est premier ou non 2 Deux nombres entiers n et m sont qualifi s d amis si la somme des diviseurs de n est gal
63. u u t E E E od u end 1 Que valent mystere 1 1 0 2 3 mystere 1 0 1 1 1 2 et mystere a b c x donner la valeur de u chaque tapes de la boucle 2 Que fait ce programme 3 Que calcule la proc dure mystere L t si les l ments de la liste L sont tous strictement inf rieur t Exercice 4 Soit T un tableau qui contient n valeurs r elles tri s dans l ordre croissant Ecrire une proc dure qui prend comme param tre le Tableau T l entier n la taille de T et un nombre r el x et elle effectue l insertion de x dans le tableau T de telle mani re que le tableau T reste tri Exemple Soit le tableau T de 8 nombres tri s dans lequel on d sire ins rer le nombre 40 417118112123 56 891 112 Le r sultat est un tableau T de 9 nombres toujours tri s 41718 12123 40 56 89 112 5 6 Examen d informatique L session de Juin 2006 Exercice 1 3 points Dans le championnat de foot marocain qui comporte 16 quipes les deux premi res quipes sont qualifi es pour la ligue des champions africaine les deux suivants le troisi me et le quatri me sont qualifi s pour la ligue des champions arabes les trois derni res quipes descendent en deuxi me division et les autres restent en premi re division Ecrire un algorithme qui demande le classement d une quipe du championnat de foot marocain Ensuite il nous informe de sa situation pour l a
64. ue SMIA module M E2 1 G n ralit s sur l Algorithmique 1 1 Introduction L algorithmique est un terme d origine arabe hommage Al Khawarizmi 780 850 auteur d un ouvrage d crivant des m thodes de calculs alg briques Un algorithme est une m thode de r solution de probl me nonc e sous la forme d une s rie d op rations effectuer La mise en uvre de l algorithme consiste en l criture de ces op rations dans un langage de programmation et constitue alors la brique de base d un programme informatique 1 Une recette de cuisine est un algorithme 2 Le mode d emploi d un magn toscope est aussi un algorithme 3 Indiqu un chemin un touriste gar ou faire chercher un objet quelqu un par t l phone c est fabriquer et faire ex cuter des algorithmes Un algorithme c est une suite d instructions qui une fois ex cut e correctement conduit un r sultat donn 1 Si l algorithme est juste le r sultat est le r sultat voulu et le touriste se retrouve l o il voulait aller 2 Si l algorithme est faux le r sultat est disons al atoire et d cid ment ce magn toscope ne marche pas Pour fonctionner un algorithme doit donc contenir uniquement des instructions compr hensibles par celui qui devra l ex cuter l ordinateur L ADN qui est en quelque sorte le programme g n tique l algorithme la base de construction des tres vivants est une cha ne construite
65. usqu au bout mais en produisant des r sultats faux Alors dans tout programme on met en place ce qu on appelle un contr le de saisie pour v rifier que les donn es entr es au clavier correspondent bien celles attendues par l algorithme On pourrait essayer avec un si Voyons voir ce que a donne Variable Rep Caract re crire Voulez vous un caf O N lire Rep si Rep O et Rep N alors crire Saisie erronn e Recommencez Lire Rep finsi a marche tant que l utilisateur ne se tromper qu une seule fois et il rentre une valeur correcte la deuxi me demande Si l on veut galement viter une deuxi me erreur il faudrait rajouter un SI Et ainsi de suite on peut rajouter des centaines de SI Mais cela ne r sout pas le probl me La seule issue est l utilisation d une boucle M El Marraki 24 31 03 2013 Algorithmique SMIA module M E2 Il existe trois fa ons d exprimer algorithmiquement l it ration a TantQue a R p ter jusqu a Pour jusqu La boucle TantQue Le sch ma de la boucle TantQue est TantQue conditions Instructions FinTantQue Le principe est simple le programme arrive sur la ligne du TantQue Il examine alors la valeur de la condition Si cette valeur est VRAI le programme ex cute les instructions qui suivent jusqu ce qu il rencontre la ligne FinTantQue Il retourne ensuite sur la ligne du TantQue pr
66. xt rieur de la machine et pour cela l algorithme doit contenir l instruction qui commande la machine de lire la donn e Si un algorithme contenant l instruction X A 2 la machine ne peut ex cuter cette instruction que si elle conna t la valeur de A en supposant que la valeur de A en ce moment n est pas connu alors l algorithme doit contenir l instruction lire A qui signifie mettre dans la case A la valeur donn e par le clavier organe d entr e de la machine D s que le programme rencontre une instruction lire l ex cution s interrompt attendant l arriver d une valeur par l interm diaire du clavier D s que la touche Entr e Enter a t frapp e l ex cution reprend Si on veut conna tre le r sultat d un calcul ou le contenu d une variable X l algorithme doit contenir l instruction qui commande la machine de fournir ce r sultat Cette instruction est crire X quisignifie mettre sur l cran organe de sortie de la machine le contenu de la case X Cette action ne modifie pas le contenu de X Exemple soit le morceau d algorithme suivant A tant une donn e X un r sultat lire A K AN crire X Sch ma des actions effectu es par l utilisateur et la machine Utilisateur Machine A X lecture L utilisateur donne 12 12 calcul 12 144 criture L utilisateur lit 144 4 La machine lit sur le clavier et crit sur l cran l utilisateur
67. ype cha ne ou en anglais le type string Dans une variable de ce type on stocke des caract res qu il s agisse de lettres de signes de ponctuation d espaces ou m me de chiffres Le nombre maximal de caract res pouvant tre stock s dans une seule variable string d pend du langage utilis e Un groupe de caract res est appel cha ne de caract res En pseudo code une cha ne de caract res est toujours not e entre guillemets car il peut y avoir une confusion entre des nombres et des suites de chiffres Par exemple 423 peut repr senter e le nombre 423 quatre cent vingt trois e ou la suite de caract res 4 2 et 3 not e 423 LA La syntaxe d une d claration de variable de type alphanum rique en pseudo langage aura la forme Variable nom cha ne Variables x y caract re Type bool en Le dernier type de variables est le type bool en on y stocke uniquement les valeurs logiques VRAI et FAUX On peut repr senter ces notions abstraites de VRAI et de FAUX par tout ce qu on veut de l anglais TRUE et FALSE ou des nombres 0 et 1 Le type bool en est tr s conomique en termes de place m moire occup e un seul bit suffit M El Marraki 11 31 03 2013 Algorithmique SMIA module M E2 En g n ral dans un algorithme on trouve des d clarations de variables de la forme Variables a b c delta x y nombres nom prenom chaines de caract res ok booleen 3 Primitives 3

d`Algorithmique - Faculté des Sciences Rabat

Contents

Download Pdf Manuals

Related Search

Related Contents

d`Algorithmique - Facult&eacute; des Sciences Rabat

Contents

Download Pdf Manuals

Related Search

Related Contents

d`Algorithmique - Faculté des Sciences Rabat