Partie 1

Cours dInformatique
1re anne SM/SMI 2007/2008, Info2 Dpartement de Mathmatiques et dInformatique, Universit Mohammed V [email protected] [email protected]
2007/2008
Info2, 1re anne SM/SMI
Objectif et plan du cours

Objectif :
Apprendre les concepts de base de l'algorithmique et de la programmation tre capable de mettre en oeuvre ces concepts pour analyser des problmes simples et crire les programmes correspondants
Plan : introduction lalgorithmique et la programmation
Gnralits sur lalgorithmique et les langages de programmation Notion de variable, affectation, lecture et criture Instructions conditionnels et instructions itratives Les Tableaux, les fonctions et procdures, la rcursivit Introduction la complexit des algorithmes Donnes structures
Initiation au Langage C (Travaux pratiques)

Info2, 1re anne SM/SMI 2
2007/2008
Programme
Un programme correspond la description dune mthode de rsolution pour un problme donn. Cette description est effectue par une suite dinstructions dun langage de programmation Ces instructions permettent de traiter et de transformer les donnes (entres) du problme rsoudre pour aboutir des rsultats (sorties). Un programme nest pas une solution en soi mais une mthode suivre pour trouver les solutions.
2007/2008
Langages informatiques
Un langage informatique est un code de communication, permettant un tre humain de dialoguer avec une machine en lui soumettant des instructions et en analysant les donnes matrielles fournies par le systme. Le langage informatique est lintermdiaire entre le programmeur et la machine. Il permet dcrire des programmes (suite conscutive dinstructions) destins effectuer une tache donne
Exemple : un programme de rsolution dune quation du second degr
Programmation : ensemble des activits orientes vers la conception, la ralisation, le test et la maintenance de programmes.
2007/2008
Langages de programmation
Deux types de langages:
Langages procduraux : Fortran, Cobol,

Pascal, C, Langages orients objets : C++, Java, C#,
Le choix d'un langage de programmation n'est pas facile, chacun a ses spcificits et correspond mieux certains types d'utilisations
2007/2008
Notion dalgorithme
Un programme informatique permet lordinateur de rsoudre un problme
Avant de communiquer lordinateur comment rsoudre ce problme, il faut en premier lieu pouvoir le rsoudre nous mme Le rsultat cest comme le plat cuisiner Les donnes sont lanalogues des ingrdients de la recette Les rgles de transformations se comparent aux directives ou instructions de la recette
Un algorithme peut se comparer une recette de cuisine
2007/2008
Algorithme informatique
Un algorithme est une suite dinstructions ayant pour but de rsoudre un problme donn. Ces instructions doivent tre excutes de faon automatique par un ordinateur.
Exemples:
prparer une recette de cuisine montrer le chemin un touriste programmer un magntoscope etc ...
2007/2008
Algorithme : exemple
Pour trouver une valeur approximative de la racine carre de x: prendre une approximation initiale arbitraire G amliorer cette approximation en calculant la moyenne arithmtique entre G et x/G continuer jusqu' atteindre la prcision souhaite Exemple : x pour x=2 X=2 G=1 X/G = 2 G = (1+ 2) = 1.5 X/G = 4/3 G = (3/2 + 4/3) = 17/12 = 1.416666 X/G = 24/17 G = (17/12 + 24/17) = 577/408 = 1.4142156
2007/2008
Algorithme et programme
Llaboration dun algorithme prcde ltape de programmation
Un programme est un algorithme Un langage de programmation est un langage compris par l'ordinateur
Llaboration dun algorithme est une dmarche de rsolution de problme exigeante La rdaction dun algorithme est un exercice de rflexion qui se fait sur papier
L'algorithme est indpendant du langage de programmation Par exemple, on utilisera le mme algorithme pour une implantation en Java, ou bien en C++ ou en Visual Basic Lalgorithme est la rsolution brute dun problme informatique
2007/2008
Algorithmique
algorithme = mthode de rsolution algorithme vient du nom du clbre mathmaticien
arabe Al Khawarizmi (Abu Ja'far Mohammed Ben Mussa Al-Khwarismi)
http ://trucsmaths.free.fr/alkhwarizmi.htm http://publimath.irem.univ-mrs.fr/glossaire/AL016.htm
Lalgorithmique dsigne aussi la discipline qui tudie les algorithmes et leurs applications en Informatique Une bonne connaissance de lalgorithmique permet dcrire des algorithmes exacts et efficaces
2007/2008 Info2, 1re anne SM/SMI 10
algorithmique
Conception
comment dvelopper un algorithme? quelles techniques produisent de bons algorithmes?
Analyse
tant donn un algorithme, quelles sont ses qualits? est-il adapt au problme? est-il efficace? comment mesurer ses performances?
tant donn un problme sans solution vidente, comment peut on le rsoudre?

en considrant les problmes similaires connus, en considrant les solutions analogues - algorithmes - connues, en faisant marcher son imagination !!!
Processus de dveloppement : codage analyse

dcouverte derreurs demandes damliorations 2007/2008 Info2, 1re anne SM/SMI
test
fin
11
Proprits dun algorithme

Un algorithme doit:
avoir un nombre fini dtapes, avoir un nombre fini doprations par tape, se terminer aprs un nombre fini doprations, fournir un rsultat.
Chaque opration doit tre:

dfinie rigoureusement et sans ambigut effective, c--d ralisable par une machine
Le comportement d'un algorithme est dterministe.
2007/2008
12
Repr d Reprsentation dun algorithme

Historiquement, deux faons pour reprsenter un algorithme: LOrganigramme: reprsentation graphique avec des symboles (carrs, losanges, etc.)
offre une vue densemble de lalgorithme reprsentation quasiment abandonne aujourdhui
Le pseudo-code: reprsentation textuelle avec une srie de conventions ressemblant un langage de programmation
plus pratique pour crire un algorithme reprsentation largement utilise
2007/2008
13
Algorithmique
Notions et Instructions de base
2007/2008
14
instructions de base
Un programme informatique est form de quatre types dinstructions considres comme des petites briques de base :
laffectation de variables la lecture et/ou lcriture les tests les boucles
2007/2008
15
Notion de variable
Une variable sert stocker la valeur dune donne dans un langage de programmation Une variable dsigne un emplacement mmoire dont le contenu peut changer au cours dun programme (do le nom de variable) Chaque emplacement mmoire a un numro qui permet d'y faire rfrence de faon unique : c'est l'adresse mmoire de cette cellule. Rgle : La variable doit tre dclare avant dtre utilise, elle doit tre caractrise par :
un nom (Identificateur) un type qui indique lensemble des valeurs que peut prendre la variable (entier, rel, boolen, caractre, chane de caractres, ) Une valeur
2007/2008
16
r Identificateurs : rgles
Le choix du nom dune variable est soumis quelques rgles qui varient selon le langage, mais en gnral: Un nom doit commencer par une lettre alphabtique
exemple : E1 (1E nest pas valide)
doit tre constitu uniquement de lettres, de chiffres et du soulignement ( _ ) (viter les caractres de ponctuation et les espaces)
Exemples : SMI2008, SMI_2008 (SMP 2008, SMP-2008, SMP;2008 : sont non valides)
doit tre diffrent des mots rservs du langage (par exemple en C: int, float, double, switch, case, for, main, return, ) La longueur du nom doit tre infrieure la taille maximale spcifie par le langage utilis
2007/2008
17
Identificateurs : conseils
Conseil: pour la lisibilit du code choisir des noms significatifs qui dcrivent les donnes manipules exemples: NoteEtudiant, Prix_TTC, Prix_HT Remarque: en pseudo-code algorithmique, on va respecter les rgles cites, mme si on est libre dans la syntaxe
2007/2008
18
Types des variables

Le type dune variable dtermine lensemble des valeurs quelle peut prendre. Les types offerts par la plus part des langages sont: Type numrique (entier ou rel)
Byte (cod sur 1octet): de [-27,27[ ou [0, 28[ Entier court (cod sur 2 octets) : [-215,215[ Entier long (cod sur 4 octets): [-231,231[ Rel simple prcision (cod sur 4 octets) : prcision dordre 10-7 Rel double prcision (cod sur 8 octets) : prcision dordre 10-14
Type logique ou boolen: deux valeurs VRAI ou FAUX Type caractre: lettres majuscules, minuscules, chiffres, symboles,..
Exemples : A, b, 1, ?,
Type chane de caractre: toute suite de caractres Exemples: " " , " Nom, Prnom", "code postale: 1000",
2007/2008
Dclaration des variables

Rappel: toute variable utilise dans un programme doit avoir fait lobjet dune dclaration pralable En pseudo-code, la dclaration de variables est effectue par la forme suivante : Variables liste d'identificateurs : type
Exemple: Variables i, j, k : entier x, y : rel OK: boolen Ch1, ch2 : chane de caractres
Variables : remarques
pour le type numrique, on va se limiter aux entiers et rels sans considrer les sous types Pour chaque type de variables, il existe un ensemble d'oprations correspondant. Une variable est l'association d'un nom avec un type, permettant de mmoriser une valeur de ce type.
2007/2008
21
Constante
Une constante est une variable dont la valeur ne change pas au cours de l'excution du programme, elle peut tre un nombre, un caractre, ou une chaine de caractres. En pseudo-code, Constante identificateur=valeur : type, (par convention, les noms de constantes sont en majuscules) Exemple : pour calculer la surface des cercles, la valeur de pi est une constante mais le rayon est une variable. Constante PI=3.14 : rel, MAXI=32 : entier Une constante doit toujours recevoir une valeur ds sa dclaration.
2007/2008
22
Affectation
Laffectation consiste attribuer une valeur une variable (cest--dire remplir ou modifier le contenu d'une zone mmoire) En pseudo-code, l'affectation est note par le signe Var e : attribue la valeur de e la variable Var - e peut tre une valeur, une autre variable ou une expression - Var et e doivent tre de mme type ou de types compatibles - laffectation ne modifie que ce qui est gauche de la flche
Exemples : i 1 j i k i+j
x 10.3 OK FAUX ch1 "SMI" ch2 ch1 x 4 x j

(avec i, j, k : entier; x :rel; ok :boolen; ch1,ch2 :chaine de caractres) Exemples non valides: i 10.3 OK "SMI" j x
2007/2008
23
Affectation
Les langages de programmation C, C++, Java, utilisent le signe gal = pour laffectation . Remarques : Lors dune affectation, lexpression de droite est value et la valeur trouve est affecte la variable de gauche. Ainsi, AB est diffrente de BA l'affectation est diffrente d'une quation mathmatique :
Les oprations x x+1 et x x-1 ont un sens en programmation et se nomment respectivement incrmentation et dcrmentation. A+1 3 n'est pas possible en langages de programmation et n'est pas quivalente A 2
Certains langages donnent des valeurs par dfaut aux variables dclares. Pour viter tout problme il est prfrable d'initialiser les variables dclares.
2007/2008
Syntaxe gnrale de lalgorithme

Algo exemple /* La partie dclaration de lalgorithme */ Constantes // les constantes ncessitent une valeur ds leur dclaration var120 : entier var2"bonjour!" : chane Variables // les variables proprement dites var3, var4 : rels var5 : chane Dbut // corps de lalgorithme /* instructions */ Fin
la squence des instructions

Les oprations d'un algorithme sont habituellement excutes une la suite de l'autre, en squence (de haut en bas et de gauche droite). L'ordre est important. On ne peut pas changer cette squence de faon arbitraire. Par exemple, enfiler ses bas puis enfiler ses bottes nest pas quivalent enfiler ses bottes puis enfiler ses bas.
2007/2008
26
Fiche 2.6
Affectation : exercices
Donnez les valeurs des variables A, B et C aprs excution des instructions suivantes ? Variables A, B, C: Entier Dbut A7 B 17 AB B A+5 CA+B CBA Fin
2007/2008
27
Affection : exercices
Donnez les valeurs des variables A et B aprs excution des instructions suivantes ?
Variables A, B : Entier Dbut A6 B2 AB BA Fin
Les deux dernires instructions permettent-elles dchanger les valeurs de A et B ?
2007/2008
28
l change Affectation : lchange des chandails
0.
1.
A 2.
B 3.
A
2007/2008
B
29
Fiche 2.6
Affectation : changes
crire un algorithme permettant dchanger les valeurs de deux variables A et B ? Rponse : on utilise une variable auxiliaire C et on crit les instructions suivantes : C A; A B; B C;
2007/2008
30
Expressions et oprateurs
Une expression peut tre une valeur, une variable ou une opration constitue de variables relies par des oprateurs exemples: 1, b, a*2, a+ 3*b-c, L'valuation de l'expression fournit une valeur unique qui est le rsultat de l'opration Les oprateurs dpendent du type de l'opration, ils peuvent tre :
des oprateurs arithmtiques: +, -, *, /, % (modulo), ^(puissance) des oprateurs logiques: NON(!), OU(| |), ET (&&) des oprateurs relationnels: =, <, >, <=, >= des oprateurs sur les chanes: & (concatnation)
Une expression est value de gauche droite mais en tenant compte des priorits des oprateurs.
2007/2008
31
Expression : remarques
On ne peut pas additionner un entier et un caractre Toutefois dans certains langages on peut utiliser un oprateur avec deux oprandes de types diffrents, cest par exemple le cas avec les types arithmtiques (4 + 5.5) La signification dun oprateur peut changer en fonction du type des oprandes
loprateur + avec des entiers effectue laddition, 3+6 vaut 9 avec des chanes de caractres il effectue la concatnation "bonjour" + " tout le monde" vaut "bonjour tout le monde"
2007/2008
32
Expression : remarques
Pour le langage C, si x et y sont entiers, x/y est une division entire alors que si lun des deux ne lest pas la division est relle x+y/z : est une expression arithmtique dont le type dpend des types de x, y et z (x>y) | | !(x=y+1) : est une expression boolenne (| | dnote loprateur logique ou et ! Dnote la ngation) Avant dutiliser une variable dans une expression, il est ncessaire quune valeur lui ait t affecte. La valeur de lexpression est value au moment de laffectation
x 4 y 6 z x+y Ecrire(z) y 20 Ecrire(z)
10 10 la modification de y aprs affectation na aucun effet sur la valeur de z

2007/2008
Priorit op Priorit des oprateurs

Pour les oprateurs arithmtiques donns ci-dessus, l'ordre de priorit est le suivant (du plus prioritaire au moins prioritaire) : () : les parenthses
^ : (lvation la puissance) * , / (multiplication, division) % (modulo) + , - (addition, soustraction) exemple: 9 + 3 * 4 vaut 21

En cas de besoin, on utilise les parenthses pour indiquer les oprations effectuer en priorit
exemple: (9 + 3) * 4 vaut 48
priorit gale, lvaluation de lexpression se fait de gauche droite
Les oprateurs boolens

Associativit des oprateurs et et ou a et (b et c) = (a et b) et c Commutativit des oprateurs et et ou a et b = b et a a ou b = b ou a Distributivit des oprateurs et et ou a ou (b et c) = (a ou b) et (a ou c) a et (b ou c) = (a et b) ou (a et c) Involution (homographie rciproque) : non non a = a Loi de Morgan : non (a ou b) = non a et non b non (a et b) = non a ou non b Exemple : soient a, b, c et d quatre entiers quelconques : (a<b)| |((a>=b)&&(c==d)) (a<b)| |(c==d) car (a<b)| |(!(a<b)) est toujours vraie
vrit Tables de vrit

C1 Vrai Vrai Faux Faux C2 Vrai Faux Vrai Faux C1 Vrai
2007/2008
C1 et C2 Vrai Faux Faux Faux Non C1 Faux
C1 ou C2 C1 XOR C2 Vrai Vrai Vrai Faux Faux Vrai Vrai Faux
Faux Vrai
dentr Les instructions dentres et sorties : lecture et criture

Les instructions de lecture et d'criture permettent la machine de communiquer avec l'utilisateur La lecture permet d'entrer des donns partir du clavier En pseudo-code, on note: lire (var) la machine met la valeur entre au clavier dans la zone mmoire nomme var Remarque: Le programme s'arrte lorsqu'il rencontre une instruction Lire et ne se poursuit qu'aprs la saisie de lentre attendue par le clavier et de la touche Entre (cette touche signale la fin de lentre) Conseil: Avant de lire une variable, il est fortement conseill dcrire des messages lcran, afin de prvenir lutilisateur de ce quil doit frapper
2007/2008
37
dentr Les instructions dentres et sorties : lecture et criture

L'criture permet d'afficher des rsultats l'cran (ou de les crire dans un fichier) En pseudo-code, on note: crire (liste dexpressions) la machine affiche les valeurs des expressions dcrite dans la liste. Ces instructions peuvent tre des variables ayant des valeurs, des nombres ou des commentaires sous forme de chaines de caractres. Exemple : crire(a, b+2, "Message")
2007/2008
38
Exemple : lecture et criture

crire un algorithme qui demande un nombre entier l'utilisateur, puis qui calcule et affiche le carr de ce nombre
Algorithme Calcul_du_Carre Rle : calcul du carre Donnes : un entier Rsultats : le carre du nombre variables A, B : entier Dbut crire("entrer la valeur de A ") lire(A) B A*A crire("le carre de ", A, "est :", B) Fin
Exercice : lecture et criture

crire un algorithme qui permet deffectuer la saisie dun nom, dun prnom et affiche ensuite le nom complet Algorithme AffichageNomComplet variables Nom, Prenom, Nom_Complet : chane de caractres Dbut crire("entrez le nom") lire(Nom) crire("entrez le prnom") lire(Prenom) Nom_Complet Nom & " " & Prenom crire("Votre nom complet est : ", Nom_Complet) Fin
2007/2008
40
Tests: instructions conditionnelles

Dfinition : une condition est une expression crite entre parenthse valeur boolenne. Les instructions conditionnelles servent n'excuter une instruction ou une squence d'instructions que si une condition est vrifie. En pseudo-code : Si condition alors instruction ou suite d'instructions1 Sinon instruction ou suite d'instructions2 Finsi
2007/2008
41
instructions conditionnelles
test
Faux
Vraie
Suite dinstructions 1
Suite dinstructions 2
2007/2008
42
Instructions conditionnelles

Remarques :
la condition ne peut tre que vraie ou fausse si la condition est vraie alors seules les instructions1 sont excutes si la condition est fausse seules les instructions2 sont excutes la condition peut tre une expression boolenne simple ou une suite compose dexpressions boolennes
La partie Sinon est optionnelle, on peut avoir la forme simplifie suivante: Si condition alors instruction ou suite d'instructions1 Finsi
2007/2008
43
SiAlors SiAlorsSinon : exemple

Algorithme ValeurAbsolue1 Rle : affiche la valeur absolue dun entier Donnes : la valeur calculer Rsultat : la valeur absolue Variable x : rel Dbut Ecrire (" Entrez un rel : ") Lire (x) Si x < 0 alors Ecrire ("la valeur absolue de ", x, "est:",-x) Sinon Ecrire ("la valeur absolue de ", x, "est:",x) Finsi Fin
Si SiAlors : exemple
Algorithme ValeurAbsolue2 Variable x, y : rel Dbut Ecrire (" Entrez un rel : " ) Lire (x) y x Si x < 0 alors y -x Finsi Ecrire ("la valeur absolue de ", x, "est:",y) Fin
Exercice (tests)
crire un algorithme qui demande un nombre entier l'utilisateur, puis qui teste et affiche s'il est divisible par 7 ou non Algorithme Divsible_par7 Variable n : entier Dbut Ecrire (" Entrez un entier : ") Lire (n) Si (n%7=0) alors Ecrire (n," est divisible par 7") Sinon Ecrire (n," n'est pas divisible par 7") Finsi Fin
compos Conditions composes

Une condition compose est une condition forme de plusieurs conditions simples relies par des oprateurs logiques: ET, OU, OU exclusif (XOR) et NON Exemples : x compris entre 2 et 6 : (x >= 2) ET (x < =6) n divisible par 3 ou par 2 : (n%3=0) OU (n%2=0) deux valeurs et deux seulement sont identiques parmi a, b et c : (a=b) XOR (a=c) XOR (b=c) L'valuation d'une condition compose se fait selon des rgles prsentes gnralement dans ce qu'on appelle tables de vrit
2007/2008
47
imbriqu Tests imbriqus

Les tests peuvent avoir un degr quelconque d'imbrications Si condition1 alors Si condition2 alors instructionsA Sinon instructionsB Finsi Sinon Si condition3 alors instructionsC Finsi Finsi
imbriqu Tests imbriqus : exemple 1

Variable n : entier Dbut Ecrire ("entrez un nombre : ") Lire (n) Si n < 0 alors Ecrire ("Ce nombre est ngatif") Sinon Si n = 0 alors Ecrire ("Ce nombre est nul") Sinon Ecrire ("Ce nombre est positif") Finsi Finsi Fin
imbriqu Tests imbriqus : exemple 2

Variable n : entier Dbut Ecrire ("entrez un nombre : ") Lire (n) Si n < 0 alors Ecrire ("Ce nombre est ngatif") Finsi Si n = 0 alors Ecrire ("Ce nombre est nul") Finsi Si n > 0 alors Ecrire ("Ce nombre est positif") Finsi Fin Remarque : dans lexemple 2 on fait trois tests systmatiquement alors que dans lexemple 1, si le nombre est ngatif on ne fait qu'un seul test Conseil : utiliser les tests imbriqus pour limiter le nombre de tests et placer d'abord les conditions les plus probables
2007/2008
50
imbriqu Tests imbriqus : exercice

Le prix de disques compacts (CDs) dans espace de vente varie selon le nombre acheter: 5 DH lunit si le nombre de CDs acheter est infrieur 10, 4 DH lunit si le nombre de CDS acheter est compris entre 10 et 20 et 3 DH lunit si le nombre de CDs acheter est au-del de 20. crivez un algorithme qui demande lutilisateur le nombre de CDs acheter, qui calcule et affiche le prix payer
2007/2008
51
imbriqu corrig Tests imbriqus : corrig

Variables unites : entier prix : rel Dbut Ecrire ("Nombre dunits : ") Lire (unites) Si unites < 10 Alors prix unites*5 Sinon Si unites < 20 alors prix unites*4 Sinon prix unites*3 Finsi Finsi Ecrire (Le prix payer est : , prix) Fin
Tests : remarques
Un sinon se rapporte toujours au dernier si qui na pas encore de sinon associ Il est recommand de structurer le bloc associ si et celui associ sinon Exemple :
Lire(a) x 1 Si (a>= 0) alors si (a==0) alors x 2 sinon x 3 finsi finsi ecrire(x) a : -1 affichage : 1
0 2
1 3
2007/2008
53
L'instruction cas
Lorsque lon doit comparer une mme variable avec plusieurs valeurs, comme par exemple : si a=1 alors instruction1 sinon si a=2 alors instruction2 sinon si a=4 alors instruction4 sinon . . . finsi finsi finsi On peut remplacer cette suite de si par linstruction cas
2007/2008
54
L'instruction cas
Sa syntaxe en pseudo-code est : cas o v vaut v1 : action1 v2 : action2 ... vn : actionn autre : action autre fincas v1,. . . ,vn sont des constantes de type scalaire (entier, naturel, numr, ou caractre) action i est excute si v = vi (on quitte ensuite linstruction cas) action autre est excute si quelque soit i, v vi
L'instruction cas : exemple

Variables c : caractre Dbut Ecrire(entrer un caractre) Lire (c) Si((c>=A) et (c<=Z)) alors cas o c vaut A,E, I, O, U, Y : ecrire(c,est une voyelle majuscule) autre : ecrire(c, est une consonne majuscule ) fincas sinon ecrire(c,nest pas une lettre majuscule) Finsi Fin
it Instructions itratives : les boucles

Les boucles servent rpter l'excution d'un groupe d'instructions un certain nombre de fois On distingue trois sortes de boucles en langages de programmation : Les boucles tant que : on y rpte des instructions tant qu'une certaine condition est ralise Les boucles jusqu' : on y rpte des instructions jusqu' ce qu'une certaine condition soit ralise Les boucles pour ou avec compteur : on y rpte des instructions en faisant voluer un compteur (variable particulire) entre une valeur initiale et une valeur finale
2007/2008
57
Les boucles Tant que

TantQue (condition) instructions FinTantQue
condition
Vrai
instructions
Faux
la condition (dite condition de contrle de la boucle) est value avant chaque itration si la condition est vraie, on excute les instructions (corps de la boucle), puis, on retourne tester la condition. Si elle est encore vraie, on rpte l'excution, si la condition est fausse, on sort de la boucle et on excute l'instruction qui est aprs FinTantQue Il est possible que les instructions rpter ne soient jamais excutes.
Les boucles Tant que : remarques

Le nombre d'itrations dans une boucle TantQue n'est pas connu au moment d'entre dans la boucle. Il dpend de l'volution de la valeur de la condition Une des instructions du corps de la boucle doit absolument changer la valeur de la condition de vrai faux (aprs un certain nombre d'itrations), sinon le programme va tourner indfiniment Attention aux boucles infinies
Exemple de boucle infinie : i1 TantQue i > 0 i i+1 FinTantQue
2007/2008
correction i1 TantQue i <100 i i+1 FinTantQue

Boucle Tant que : exemple1

Contrle de saisie d'une lettre alphabtique jusqu ce que le caractre entr soit valable Variable C : caractre Debut crire (" Entrez une lettre majuscule ") Lire (C) TantQue (C < 'A' ou C > 'Z') Ecrire ("Saisie errone. Recommencez") Lire (C) FinTantQue Ecrire ("Saisie valable") Fin
Tant que : exemple2

En investissant chaque anne 10000DH intrts composs de 7%, aprs combien dannes serons nous millionnaire ? Variables capital :rel nbAnnees : entier Debut capital 0.0 nbAnnes 0 Tantque (Capital < 1000000)
Debut capital capital+10000; nbAnnees++; capital (1+0.07)*capital;
FinTantque Fin
2007/2008
61

Un algorithme qui dtermine le premier nombre entier N tel que la somme de 1 N dpasse strictement 100 version 1 Variables som, i : entier Debut i0 som 0 TantQue (som <=100) i i+1 som som+i FinTantQue Ecrire (" La valeur cherche est N= ", i) Fin

Un algorithme qui dtermine le premier nombre entier N tel que la somme de 1 N dpasse strictement 100
forme 2: attention l'ordre des instructions et aux valeurs initiales Variables som, i : entier Debut som 0 i1 TantQue (som <=100) som som + i i i+1 FinTantQue crire (" La valeur cherche est N= ", i-1) Fin
2007/2008
63
Les boucles Rpter jusqu jusqu

Rpter instructions Jusqu' condition
instructions Faux
condition Vrai
Condition est value aprs chaque itration les instructions entre Rpter et jusqu sont excutes au moins une fois et leur excution est rpte jusqu ce que la condition soit vraie (tant qu'elle est fausse)
Boucle Rpter jusqu : exemple 1 jusqu

Un algorithme qui dtermine le premier nombre entier N tel que la somme de 1 N dpasse strictement 100 (version avec rpter jusqu') Variables som, i : entier Debut som 0 i0 Rpter i i+1 som som+i Jusqu' ( som > 100) Ecrire (" La valeur cherche est N= ", i) Fin
2007/2008
65
Boucle Rpter jusqu : exemple 2 jusqu

Ecrire un algorithme qui compte le nombre de bits ncessaires pour coder en binaire un entier n. Solution : Variables i, n, nb : entiers Debut Ecrire(" Entrer la valeur de n :") lire(n) i n nb 0 Rpter i i/2 nb nb + 1 jusqu (i=0) Ecrire("Pour coder ",n," en binaire il faut ",nb, "bits") Fin
2007/2008
66
Les boucles Tant que et Rpter jusqu

Diffrences entre les boucles Tant que et Rpter jusqu' : - la squence d'instructions est excute au moins une fois dans la boucle Rpter jusqu', alors qu'elle peut ne pas tre excute dans le cas du Tant que. - la squence d'instructions est excute si la condition est vraie pour Tant que et si la condition est fausse pour Rpter jusqu'. - Dans les deux cas, la squence d'instructions doit ncessairement faire voluer la condition, faute de quoi on obtient une boucle infinie.
Les boucles Pour

Pour compteur allant de initiale finale par pas valeur du pas instructions FinPour
iinitiale
i na pas atteint finale
Vrai
instructions
ii+pas
Faux
2007/2008
68
Les boucles Pour

Remarque : le nombre d'itrations dans une boucle Pour est connu avant le dbut de la boucle Compteur est une variable de type entier (ou caractre). Elle doit tre dclare Pas est un entier qui peut tre positif ou ngatif. Pas peut ne pas tre mentionn, car par dfaut sa valeur est gal 1. Dans ce cas, le nombre d'itrations est gal finale - initiale+ 1 Initiale et finale peuvent tre des valeurs, des variables dfinies avant le dbut de la boucle ou des expressions de mme type que compteur
2007/2008
69
Droulement des boucles Pour

1) La valeur initiale est affecte la variable compteur 2) On compare la valeur du compteur et la valeur de finale : a) Si la valeur du compteur est > la valeur finale dans le cas d'un pas positif (ou si compteur est < finale pour un pas ngatif), on sort de la boucle et on continue avec l'instruction qui suit FinPour b) Si compteur est <= finale dans le cas d'un pas positif (ou si compteur est >= finale pour un pas ngatif), instructions seront excutes
i. Ensuite, la valeur du compteur est incrmente de la valeur du pas si pas est positif (ou dcrment si pas est ngatif) ii. On recommence l'tape 2 : La comparaison entre compteur et finale est de nouveau effectue, et ainsi de suite
Boucle Pour : exemple 1 (forme 1)

Calcul de x la puissance n o x est un rel non nul et n un entier positif ou nul Variables x, puiss : rel n, i : entier Debut Ecrire (" Entrez respectivement les valeurs de x et n ") Lire (x, n) puiss 1 Pour i allant de 1 n puiss puiss*x FinPour Ecrire (x, " la puissance ", n, " est gal ", puiss) Fin
Boucle Pour : exemple1 (forme 2)

Calcul de x la puissance n o x est un rel non nul et n un entier positif ou nul (forme 2 avec un pas ngatif) Variables x, puiss : rel n, i : entier Debut Ecrire (" Entrez respectivement les valeurs de x et n ") Lire (x, n) puiss 1 Pour i allant de n 1 par pas -1 puiss puiss*x FinPour Ecrire (x, " la puissance ", n, " est gal ", puiss) Fin
Boucle Pour : remarques

Il faut viter de modifier la valeur du compteur (et de finale) l'intrieur de la boucle. En effet, une telle action : perturbe le nombre d'itrations prvu par la boucle Pour rend difficile la lecture de l'algorithme prsente le risque d'aboutir une boucle infinie Exemple : Pour i allant de 1 5 i i -1 crire(" i = ", i) Finpour
2007/2008
73
Lien entre Pour et TantQue

La boucle Pour est un cas particulier de Tant Que (cas o le nombre d'itrations est connu et fix) . Tout ce qu'on peut crire avec Pour peut tre remplac avec TantQue (la rciproque est fausse) Pour compteur allant de initiale finale par pas valeur du pas instructions FinPour peut tre remplac par : compteur initiale (cas d'un pas positif) TantQue compteur <= finale instructions compteur compteur+pas FinTantQue
TantQue: Lien entre Pour et TantQue: exemple 1

Calcul de x la puissance n o x est un rel non nul et n un entier positif ou nul (forme avec TantQue) Variables x, puiss : rel n, i : entier Debut Ecrire (" Entrez respectivement les valeurs de x et n ") Lire (x, n) puiss 1, i 1 TantQue (i<=n) puiss puiss*x i i+1 FinTantQue Ecrire (x, " la puissance ", n, " est gal ", puiss) Fin 2007/2008 Info2, 1re anne SM/SMI
75
Boucles : exercice
Ecrire un algorithme qui compte le nombre de 1 dans la reprsentation binaire de lentier n. Solution : Variables i, n, poids : entiers Debut Ecrire(" Entrer la valeur de n :") lire(n) i n nbits 0 TantQue(i<>0) faire si (i mod 2 = 1) alors poids poids + 1 i i/2 FinTantQue Ecrire("Pour lentier",n," le poids est : ",poids) Fin
2007/2008
76
imbriqu Boucles imbriques

Les instructions d'une boucle peuvent tre des instructions itratives. Dans ce cas, on aboutit des boucles imbriques Exemple: Pour i allant de 1 5 Pour j allant de 1 i crire("O") FinPour crire("K") FinPour Excution OK OOK OOOK OOOOK OOOOOK
2007/2008
77
Choix d'un type de boucle

Si on peut dterminer le nombre d'itrations avant l'excution de la boucle, il est plus naturel d'utiliser la boucle Pour S'il n'est pas possible de connatre le nombre d'itrations avant l'excution de la boucle, on fera appel l'une des boucles TantQue ou rpter jusqu' Pour le choix entre TantQue et jusqu' :

2007/2008
Si on doit tester la condition de contrle avant de commencer les instructions de la boucle, on utilisera TantQue Si la valeur de la condition de contrle dpend d'une premire excution des instructions de la boucle, on utilisera rpter jusqu'

Partie 1

Transféré par

Droits d'auteur :

Formats disponibles

Partie 1

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Partie 1

Transféré par

Droits d'auteur :

Formats disponibles

Cours dInformatique

Info2, 1re anne SM/SMI

Objectif et plan du cours

Plan : introduction lalgorithmique et la programmation

Initiation au Langage C (Travaux pratiques)

Info2, 1re anne SM/SMI

Exemple : un programme de rsolution dune quation du second degr

Info2, 1re anne SM/SMI

Langages procduraux : Fortran, Cobol,

Info2, 1re anne SM/SMI

Un algorithme peut se comparer une recette de cuisine

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

http ://trucsmaths.free.fr/alkhwarizmi.htm http://publimath.irem.univ-mrs.fr/glossaire/AL016.htm

tant donn un problme sans solution vidente, comment peut on le rsoudre?

Processus de dveloppement : codage analyse

Proprits dun algorithme

Chaque opration doit tre:

Le comportement d'un algorithme est dterministe.

Info2, 1re anne SM/SMI

Repr d Reprsentation dun algorithme

offre une vue densemble de lalgorithme reprsentation quasiment abandonne aujourdhui

Info2, 1re anne SM/SMI

Notions et Instructions de base

Info2, 1re anne SM/SMI

laffectation de variables la lecture et/ou lcriture les tests les boucles

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

Types des variables

Dclaration des variables

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

x 10.3 OK FAUX ch1 "SMI" ch2 ch1 x 4 x j

Info2, 1re anne SM/SMI

Syntaxe gnrale de lalgorithme

la squence des instructions

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

Les deux dernires instructions permettent-elles dchanger les valeurs de A et B ?

Info2, 1re anne SM/SMI

l change Affectation : lchange des chandails

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

Info2, 1re anne SM/SMI

x 4 y 6 z x+y Ecrire(z) y 20 Ecrire(z)

10 10 la modification de y aprs affectation na aucun effet sur la valeur de z

Priorit op Priorit des oprateurs

^ : (lvation la puissance) * , / (multiplication, division) % (modulo) + , - (addition, soustraction) exemple: 9 + 3 * 4 vaut 21

Les oprateurs boolens

vrit Tables de vrit

C1 et C2 Vrai Faux Faux Faux Non C1 Faux

C1 ou C2 C1 XOR C2 Vrai Vrai Vrai Faux Faux Vrai Vrai Faux

dentr Les instructions dentres et sorties : lecture et criture

Info2, 1re anne SM/SMI

dentr Les instructions dentres et sorties : lecture et criture

Info2, 1re anne SM/SMI