Programmation Impérative2006-2007

Licence PhysiqueUniversité Jean Monnet

Ruggero G. PENSA

Eléments d’algorithmique

Introduction

Variables

Opérateurs et expressions

Actions

Entrée/Sortie

Définitions

Algorithmedescription d’un ensemble d’étapes (instructions) à effectuer dans un ordre donné pour parvenir à un résultat

Langage de programmationlangage dans lequel un algorithme peut être traduit pour être compris par l’ordinateur

Programmedescription d’un algorithme dans un langage de programmation

Exemples Guide de montage d’un meuble IKEA/Conforama… Recette de cuisine

Types de langage

Pour vos algorithmes Langage naturel : français, anglais, italien… Langages formels : pseudo-code

Pour vos programmes Langages évolués : C, Pascal, Visual Basic, Delphi, Java…

Utile à savoir Langages assembleurs : mnémoniques Langages machines : ensemble de bits

Langages interprétés : Visual Basic, Matlab, Pearl… Langages compilés : C, Pascal, Cobol, ADA

Langage de programmation

Un langage de programmation est un langage formel avec une syntaxe bien définie, qui sert à coder des algorithmes et des structures de données dans une forme compréhensible par l’ordinateur

Un programme informatique est constitué d’une suite d’instructions (ou ordres) exécutées par l’ordinateur pour accomplir une tâche particulière

Dans un langage il est important à la fois Le contenu (le sens) La forme (la syntaxe, la grammaire)

Méthodologie de programmation

Problème

Algorithme

Programme(langage évolué)

Programme(langage machine)

Résultats

Analyse

Débogage

Révision Débogage

Conception

Exécution

Traduction (Compilation)

TD

TP

Qualités d’un algorithme

Correctbien faire ce qui est prévu

Completfaire tout ce qui est prévu

Efficaceexécution rapideavec peu d’occupation mémoire

Clairdoit être facilement lisible et évolutif

Introduction au formalisme

Un algorithme doit être compréhensible par plusieurs personnes

Exemple

Nom : addDeuxEntiersRôle : Additionner deux entiers Entrée : a, b : entierSortie : entierDéclaration :

débutretourner (a + b)

fin

Entête

Corps

Variable

Entité qui contient une information

Possède un nom (identifiant)

Possède une valeur

Possède un type (qui caractérise l’ensemble des valeurs que peut prendre la variable)

Est stockée dans la mémoire centrale de l’ordinateur

Variable

Analogie avec une armoire d’archive qui contiendrait des tiroirs étiquetés

Armoire Mémoire de l’ordinateur Tiroirs Variables Etiquettes Identifiants Contenu Valeur Couleur Type

Exemple : bleu pour les factures, rouge pour les bons de commande…

Type d’une variable

Caractérise L’ensemble des valeurs que peut prendre la variable L’ensemble des actions que l’on peut effectuer sur une variable

Toute variable doit être déclarée avant son utilisation (partie Déclaration) en lui associant un Type

Identifiant : Type Exemples

age : Naturel nom : Chaîne de Caractères sexe : Caractère moyenne : Réel

Une fois qu’un type est associé à une variable, on peut pas le changer

Une fois qu’un type est associé à une variable le contenu de cette variable doit être obligatoirement du même type

Types de données

Types simples Dénombrables (nombre d’éléments fini) Indénombrables (nombre d’éléments infini)

Types complexes Exemples

- nombre complexe (partie réelle + partie imaginaire)- etudiant (nom + prénom + moyenne)

Types de données simples

Dénombrables

Booléen : { VRAI, FAUX }les variables ne peuvent prendre que ces deux valeurs

Intervalle, ex, : [1..10]les variables ne peuvent prendre que les valeurs entières définies dans cet intervalle

Énuméré, ex : {rouge, vert, jaune}les variables ne peuvent prendre que les valeurs explicitées

Caractères : table ASCII

Dénombrables

Exemples célibataire : booléen mois : 1..12 minuscules : ‘a’..‘z’ jour : JoursDeLaSemaine

Déclaration : type JourDeLaSemaine = énuméré {lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche}

Types de données simples

Indénombrables

Entier (positifs et négatifs)

Naturel (entiers positifs)

Réel

Chaîne de caractéresExemple ’’cours’’ ou ’’TD d’algorithmique’’

Indénombrables

Exemples

age : naturel

taille : réel

nom : chaîne de caractères

Constante

Variable dont la valeur est fixée tout au début de l’algorithme et ne change pas lors de l’exécution de l’algorithme

Possède Un nom Un type Une valeur (fixe)

Exemples Pi : Réel 3.14159 Euro : Réel 6.55957 Répétitions : Entier 10

Opérateurs, opérande et expression

Opérateur : symbole d’opération qui permet d’agir sur des variables ou de faire des calculs

Opérande : entité (variable, constante ou expression) utilisée par un opérateur

Expression : combinaisons d’opérateur(s) et d’opérande(s), evaluée durant l’exécution de l’algorithme.Possède une valeur (son interprétation) un type

Opérateur, opérande et expression

Exemple : a + b

a : opérande gauche + : opérateur b : opérande droite a + b : expression

Si a vaut 2 et b vaut 3, l’expression a + b vaut 5 Si a et b sont des entiers, l’expression a + b est de

type entier

Type d’opérateurs

Unaire : un seul opérande(Exemple : non)

Binaire : deux opérandes(Exemple : +)

L’expression possède un seul type dans une expression chaque opérateur doit être associé au type de l’expression(Exemple : "J’ai" + 2 + "chats")

Seule exception tolérée : types arithmétiques(Exemple : 2 + 3.5)

Signification des opérateurs

Peut changer en fonction du type des opérandes

Par exemple

opérateur + avec des entiers aura pour sens l'addition2 + 3 vaut 5

Opérateur + avec des chaînes de caractères aura pour sens la concaténation"bonjour" + " tout le monde" vaut"bonjour tout le monde"

Opérateurs sur les booléens

Quatre opérateurs

vraifauxfauxvrainon aa

fauxfauxfauxvraifauxvraivraivraifauxvraivraivraia ou bba

fauxfauxfauxfauxfauxvraifauxvraifauxvraivraivraia et bba

fauxfauxfauxvraifauxvraivraivraifauxfauxvraivrai

a ouExclusif bba

Opérateurs sur les énumérés

Trois opérateurs succ : permet d'obtenir le successeur pred : permet d'obtenir le prédecesseur ord : permet d'obtenir le naturel de correspondant à la

position de l'élément dans la liste de l'énuméré

Exemplestype JoursDeLaSemaine succ Lundi vaut Mardisucc Dimanche vaut Lundi

pred Mardi vaut Lundipred Lundi vaut Dimanche

ord Lundi vaut 0ord Dimanche vaut 6

Opérateurs sur les caractères

Quatre opérateurs (les trois des énumérés + car)

On considère la position dans la table ASCII

Exemples ord 'A' vaut 65 car 65 vaut 'A' pred 'A' vaut '@' succ 'b' vaut 'c'

Cf. man ascii

Opérateurs arithmetiques

Pour les entiers : +, -, *, / Pour les réels : +, -, *, / Pour les naturels et les entières :div : division entièremod : reste de la division

Exemples 11 div 2 vaut 5 11 mod 2 vaut 1

Opérateurs sur les chaînes de caractères

Concatenation : +

Exemple :"bonjour" + " tout le monde" vaut "bonjour tout le monde"

Opérateurs de comparaison

= : opérateur d'égalitéon le retrouve chez tous les types simples et permet de savoir si deux opérandes sont égales

≠ : opérateur d'inégalité

<, >, ≤, ≥ : opérateurs de comparaisons pour les types possédant un ordre

Une expression de comparaison contenant un opérateur de comparaisons est de type booléenExemples 12 < 14 vaut VRAI "marco" = "zizou" vaut FAUX

Priorité des opérateurs

Tout comme en arithmétique, les opérateurs ont des prioritésExemple : * / + - (du plus prioritaire au moins prioritaire)

Pour les booléen :non, et, ouExclusif, ou

En cas de doute : utiliser les parenthèses

Actions sur les variables

Lecture d'une variable obtenir son contenu Il suffit de nommer la variable

Exemple : écrire(a)

Écriture d'une variable affecter un (nouveau) contenu à la variable en utilisant la procédure lire (a) en utilisant l'opérateur d'affectation ""

Syntaxe : identifiant expressionl'expression ne contient pas d'opérateur d'affectation

Opérateur d'affectation

Qu'est-ce que ça veut dire c a + b ? On prend la valeur contenue dans la variable a On prend la valeur contenue dans la variable b On additionne ces deux valeurs On met ce résultat dans la variable c Si c avait auparavant une valeur, cette dernière est perdue

Exemple :- x 1 (on affecte la valeur 1 à la variable x)- x x + 1 (on ajoute 1 à la valeur contenue dans x, on

stocke le résultat dans x)- Résultat : incrémentation de la variable x d'une unité (x vaut 2)

Les entrées/sorties

Un algorithme a souvent des interactions avec l'utilisateur. Il peut Afficher un résultat (texte ou contenu d'une variable) Demander à l'utilisateur de saisir une information afin de la stocker

dans une variable

Affichage Commande écrire suivie entre parenthèses de la chaîne de

caractères entre guillemets et/ou des variables de type simple à afficher (séparées par des virgules)

Exemple :écrire("La valeur de la variable prix est ", prix, " Euros")

Saisie Commande lire suivie entre parenthèses de la variable de type

simple qui va recevoir la valeur saisie par l'utilisateur Exemple : lire(b)

Exemple d'algorithme

Nom : euroVersFrancRôle : Convertisseur des sommes en euros vers le franc, avec sisie de la

somme en euro et affichage de la somme en franc.Entrée : -Sortie : -Déclaration : constante tauxConversion : Réel 6.55957 variable valeurEnEuro, valeurEnFranc : Réeldébut écrire("Entrer votre valeur en euro : ") lire(valeurEnEuro) valeurEnFranc valeurEnEuro * tauxConversion écrire(valeurEnEuro, "euros = ", valeurEnFranc, " Fra")fin

Langage C

Introduction

Variables

Opérateurs et expressions

Instructions

Entrée/Sortie

Histoire

Développé en 1971 par Dennis Ritchie au sein des laboratoires Bell pour écrire le système UNIX

Spécifications publiées en 1978 dans l'ouvrage de Kerninghan et Ritchie : "The C Programming Language" (K&R C)

Norme AINSI C publiée en 1989 (ANSI C)

Compilation

.c

.h

.s .o

compilateur

assembleur

éditeur de liens

gcc –o exécutable source.c

fichier.cfichier.o

fichier exécutable

Compilation 2

.c

.h

.s .o

compilateur

assembleur

éditeur de liens

.c

.s .o

vert.c

bleu.c

vert.o

bleu.o

common.h

fichier exécutable

Séparateurs et commentaires

Espace, tab et retour à la ligne sont ignorées (mais utiles pour la mise en forme du fichier .c)

/* */ : commentaires (ignorés)/* ceci est un commentairesur plusieurs lignes */

; termine une déclaration ou une instruction simple , sépare deux éléments dans une liste (…) liste d'arguments {…} bloc ou liste d'initialisations […] dimension/sélection d'élements de tableaux

Structure d'un programme C

fin du bloc}corps du programme… ;variables… ;début du bloc{fonction principaleint main(int argc, char*argv[])fonctions… ;variables… ;prépocesseur#include <stdio.h>

Directives du procésseur

Commencent toujours par #Exemples : #include #define #ifdef

Quatre utilisations principales1. Inclusion de fichiers2. Constantes symboliques3. Macros4. Compilation conditionnelle

Variables

En C les variables sont caractérisées par

un identifiant

une portée

un type

une valeur

Identifiants

L'identifiant d'une variable est son nom

En C il est composé d'une suite de caractères parmi les lettres minuscules les lettres majuscules les chiffres "_" (underscore)

Le premier caractère est toujours "_" ou une lettre

Exemples (nom corrects)x x2 _x LePoint c_est_bon

Exemples (non incorrects)2x non' le.point hara-kiri

Identifiants 2

Distinction entre majuscules et minusculestoto ≠ Toto ≠ TOTO

Les mots réservés du langage C ne sont pas redéfinissables par le programmeur

caseswitchwhile

doforelseifcontinuebreak

returngotovolatilestaticregisterextern

autoconstsizeoftypedefunionstruct

enumunsigneddefaultsignedshortlong

voidasmdoublefloatcharint

Déclaration

On prévient le compilateur en début de bloc que l'on va utiliser une variable et le type d'éléments qui y seront stockés

Forme : <type> <identifiant> Exemple : int ma_variable

Affectation

On stocke une valeur dans la variable

Forme : <identifiant> = <contenu> ; Exemple : a = 3 ; (si a est une variable entière)

Initialisation

Déclaration + Affectation

Forme : <type> <identifiant> = <contenu> ; Exemple : int a = 3 ; (si a est une variable

èntiere)

Utilisation

On récupère la valeur qui est stockée dans la variable

Forme : <identifiant>Exemple : a + 2.5 (si a est une variable réelle)

Portée

La portée d'une variable définit où la variable peut être utilisée

En C une variable peut être utilisée à partir du moment où elle a été définie et jusqu'à la fin du bloc de déclaration

Portée Exemple

Variable a#include…int a ;… ;void test(int b){ if (a > b) { int c = b ; b = a ; a = b ; } ecrire(b) ;}void test2…

Portée Exemple

Variable b#include…int a ;… ;void test(int b){ if (a > b) { int c = b ; b = a ; a = b ; } ecrire(b) ;}void test2…

Portée Exemple

Variable c#include…int a ;… ;void test(int b){ if (a > b) { int c = b ; b = a ; a = b ; } ecrire(b) ;}void test2…

Types de base

void : type vide char : 'a' … 'b' … 'B' … '\n' … '\t' … '\014' int : 120 … -10 … 0123 … 0xfc … 0xFC float : 1.23 … -1.23 … 1.2345e+12 … 1. double : 1.23 … -1.23 … 1.23456789012345e+12 pas de type booléen en C Utiliser les entier

FAUX : 0, VRAI : tous les autres valeurs pas de type intervalle

Le type int possède 3 sous-typesshort, long et unsigned

Constantes

Les constantes sont des variables dont la valeur ne peut pas changer

Elles se déclarent comme des variables et sont affectées définitivement à ce moment là

Elles sont précédées du mot-clef constExemples const double Pi = 3.141592654 ; const int BufSize = 1024 ; const int VRAI = 1, FAUX = 0 ;

Elles ne peuvent pas être modifiées

Expressions

Une expression est un ensemble d'une ou de plusieurs opérations

Une expression a une valeur Types d'opérations :

arithmétiques logiques affectation et in/de-crémentation relations conversion de type

L'ordre d'évaluation dans une expression est déterminé par des règles de priorité et d'associativité

Le type de donné du résultat est déterminé par le type des opérandes

Opérateurs arithmétiques

Pour les entiers et les réels

expr % exprmodulo (binaire)%

expr / exprdivision (binaire)/

expr * exprmultiplication (binaire)

*

expr – exprsoustraction (binaire)-

-exprsoustraction (unaire)-

expr + expr + …addition (binaire)+UsageFonctionOpérateur

Opérateur d'affectation

Permettent de donner une valeur à une variable

int i, j ;i = 0 ;j = 1 ;

Attention : retourne la valeur affectéeint x, y ;x = y = -1 ; /* se lit : x = (y = -1) ; */

Combinaison possible avec un opérateur arithmétiquea = a + 2 ; a += 2 ;y = y / 4 ; y /= 4 ;x = x * (y + z) x *= y + z ;

Opérateurs d'in/de-crémentation

L'opérateur ++ et l'opérateur – fournissent un moyen efficace pour compacter les écritures x++ ; post-incrémentation x-- ; post-décrémentation ++x ; pré-incrémentation --x ; pré-décrémentation

Significationx++ ; équivaut à x = x + 1 ;x-- ; équivaut à x = x – 1 ;

Opérateurs relationnels

Le résultat est une expression booléenne vraie ou fausse Lors de l'évaluation : arrêt de l'évaluation dès que la première

opérande est fausse, dans le cas de &&, ou vraie, dans le cas de ||

expr || exprou logique||expr && expret logique&&

!exprnon logique!expr <= exprinférieur ou égal<=expr < exprinférieur<

expr >= exprsupérieur ou égal>=expr > exprsupérieur>expr != exprinégalité!=expr == exprégalité==

UsageFonctionOpérateur

Instruction

Il existe deux types d'instruction

Instructions simples terminées par un ';'Exemple : a = 4 ; b++ ;

Instructions composées utilisant un bloc {…} Instructions conditionnelles Instructions d'itération

Instruction conditionnelle (exemple)

if (a < b){ c = b – a ; ecrire("Négatif") ;}else{ c = a – b ; ecrire("Positif ou zéro") ;}

Instructions d'itération

while (a < b){ a++ ; b-- ;}

for (i=1 ; i <= 10 ; i++) { somme += i ; produit *= i;}

Entrées

Entrées : scanf()

scanf("%c", &c) ;char c ;scanf("%f", &f) ;float f ;scanf("%lf", &d) ;double d ;scanf("%i", &i) ;int i ;instructionVariable

!!!

Sorties

Entrées : printf()

printf("%c", c) ;char c ;

printf("%lf", d) ;printf("%f", f) ;printf("%e", f) ; exponentielle

double d ;float f ;

printf("%i", i) ;printf("%d", i) ;printf("%x", i) ; héxadecimal

int i ;instructionVariable

Exemple d'algorithme

Nom : euroVersFrancRôle : Convertisseur des sommes en euros vers le franc, avec sisie de la

somme en euro et affichage de la somme en franc.Entrée : -Sortie : -Déclaration : constante tauxConversion : Réel 6.55957 variable valeurEnEuro, valeurEnFranc : Réeldébut écrire("Entrer votre valeur en euro : ") lire(valeurEnEuro) valeurEnFranc valeurEnEuro * tauxConversion écrire(valeurEnEuro, "euros = ", valeurEnFranc, " Fra")fin

Traduction en Langage C

#include <stdio.h>

const float tauxDeConversion = 6.55957 ;

int main(int argc, char *argv[]){

float valeurEnEuro, valeurEnFranc;printf("Entrer votre valeur en euros :") ;scanf("%f", &valeurEnEuros) ;valeurEnFranc = valeurEnEuro * tauxDeConversion ;printf("%f euros = %f Fra\n", valeurEnEuros,

valeurEnFranc) ;return 0 ;

}

Récapitulatif

scanfprintf

lireécrire

EntréeSortie

E/S

a++ ;a-- ;+ - / * %! && ||== != < > <= >=

a a + 1a a – 1+ - / * mod et +. -. *. /.non et ou= ≠ < > ≤ ≥

incrémentationdécrémentationarithmétiquelogiquerelation

Opérateurs

int a ;a = 3 ;a

a : Entiera 3a

déclarationaffectationutilisationportée

Variables

void--intfloat / doublechar

-Booléen[1..10]EntierRéelCaractère

videbooléenintervalleentierréelcaractère

Types

Langage de programmationLangage C

Langage algorithmiquePseudo-code

Instruction

Depuis la déclaration jusqu'à la fin du bloc de déclaration