M09 Techniques D Programmation Structuree

BIGSOFT INSTITUT PRIVE D’ENSEIGNEMENT PROFESSIONNEL

U F 1-09 : TECHNIQUES DE PROGRAMMATION STRUCTUREE TSDI 1 2008/2009 1

ANALYSE d'un problème en vue de sa résolution informatique.

2

1. On effectue une analyse descendante. Décomposition en modules : • On découpe le problème en modules de difficulté moindre( si nécessaire ). • Et l'on assemble les modules à la fin. 3

2. Description de l'enchaînement des actions ( algorithme ) : • Il faut réfléchir à la façon de résoudre le problème. • Décrire l'enchaînement des actions en utilisant une écriture algorithmique ou à l'aide d'un organigramme.

4

3. Faire une liste des données, avec leurs caractéristiques. N.B. On regroupe sous le nom de DONNEES ( ou VARIABLES ) : les données, au sens strict : ENTREES. • les résultats : SORTIES. • les variables intermédiaires : variables INTERNES. 5

Une donnée est caractérisée par son nom, son type, son usage, sa valeur.

6

. Le nom : ( ou identificateur ) c'est le mnémonique qui permet de désigner une donnée. - En général, il doit commencer par une lettre. - le nombre de caractères est limité. - Certains mots sont réservés, et aussi certains caractères. N.B. Il est bon de choisir un nom qui indique à quoi va servir la variable ( ex : cumul, position, ... )

7

Le type : variable numérique ( entier signé, non signé, booléen, réel,...) variable caractère, ou chaîne de caractères, variables indicées ( vecteurs, tableaux d'entiers, ...) 8

l' usage : entrée, sortie, entrée/sortie, interne. Avec un commentaire sur l'utilisation de la variable.

9

C’EST QUOI UN ALGORITHME Avez-vous déjà ouvert un livre de recettes de cuisine ? Avez vous déjà déchiffré un mode d’emploi d’un appareil? Si oui, sans le savoir,vous avez déjà exécuté

des algorithmes. Avez-vous déjà indiqué un chemin à quelqu’un ? Avez vous fait chercher un objet à quelqu’un par téléphone ? Si oui, vous avez déjà fabriqué – et fait exécuter – des algorithmes. 10

DEFINITION: Un algorithme, c’est une suite d’instructions, qui une fois exécutée correctement, conduit à un résultat donné. Le terme algorithme est issu du nom du mathématicien arabe ALKHAWARIZMI(820 après JC). 11

FONCTIONNEMENT Pour fonctionner, un algorithme doit donc contenir uniquement des instructions compréhensibles par celui qui devra l’exécuter.

12

COMMENT MAITRISER LE LANGAGE ALGORITHMIQUE? 13

DEUX QUALITES SONT REQUISES:

14

1) Il faut avoir une certaine intuition, car aucune recette ne permet de savoir a priori quelles instructions permettront d’obtenir le résultat voulu. 15

2) Il faut être méthodique et rigoureux. En effet, chaque fois qu’on écrit une série d’instructions qu’on croit justes, il faut systématiquement se mettre mentalement à la place de la machine qui va les exécuter, armé d'un papier et d'un crayon, afin de vérifier si le résultat obtenu est bien celui que l’on voulait.

16

cet apprentissage est long, et demande des heures de travail patient. Aussi, dans un premier temps, évitez de sauter les étapes : la vérification méthodique, pas à pas, de chacun de vos algorithmes représente plus de la moitié du travail à accomplir 17

Enfin, les ordinateurs, ne sont fondamentalement capables de comprendre que quatre catégories d'ordres (d'instructions). Ces quatre familles d'instructions sont : l’affectation de variables la lecture / écriture les tests les boucles

18

CONVENTIONS DE REDACTION D’UN ALGORITHME 2 MODELES DE REPRESENTATION

19

1°une représentation graphique, avec des carrés, des losanges, etc. qu’on appelait des organigrammes. Aujourd’hui, cette représentation est quasiment abandonnée.

20

1) Une représentation graphique, avec des carrés, des losanges, etc. qu’on appelait des organigrammes. Aujourd’hui, cette représentation est quasiment abandonnée.

21

2) Une série de conventions appelée « pseudo-code », qui ressemble à un langage de programmation authentique. C’est un langage humain, aucune machine n’est censée le reconnaître. C’est pourquoi on admettra des différences de syntaxe. 22

les étapes de travail et les outils conceptuels à utiliser lors d’un processus de programmation descendante. ETAPES PRATIQUES

Matériel et moyens techniques à disposition.

Analyse

Papier, Crayon, Intelligence, Habitude. Détermination des données d’entrées et les résultats de sorties.

Mise en forme de l’algorithme

C’est l’aboutissement de l’analyse, esprit logique et rationnel.

Description

Utilisation pratique des outils d’une méthode de programmation, ici la prog. structurée.

Traduction

Transfert des écritures algorithmiques en langage de Programmation.

Tests et mise au point .

Mise au point du programme sur des valeurs tests ou à partir de programmes spécialisés.

Exécution .

Phase finale : le programme s’exécute sans erreur 23

Partie 1 Les Variables

24

On utilise une variable dés qu’on a besoin de stocker une information au cours d’un programme. Physiquement, sur l’ordinateur il y a un emplacement mémoire repérée par une adresse binaire. Ce qui revient à créer une boîte (espace mémoire) et lui attaché une étiquette(adresse).

25

1. Déclaration des variables

26

La première chose à faire tout au début de l’algorithme, avant de pouvoir utiliser des variables, c’estde faire la déclaration des variables. Lorsqu’on déclare une variable, on lui attribue un nom et on lui réserve un emplacement mémoire. La taille de cet emplacement mémoire dépend du type de variable. C’est pour cette raison qu’on doit préciser lors de la déclaration le type du variable. 27

La syntaxe d’une déclaration de variable est la suivante: VARIABLE nom : TYPE OU VARIABLES nom1, nom2,… : TYPE

28

1.1 Types numériques classiques : Type Numérique

Plage

Byte (octet)

0 à 255

Entier simple

-32 768 à 32 767

Entier long

-2 147 483 648 à 2 147 483 647

Réel simple

-3,40x1038 à -1,40x1045 pour les valeurs négatives 1,40x10-45 à 3,40x1038 pour les valeurs positives

Réel double

1,79x10308 à -4,94x10-324 pour les valeurs négatives 4,94x10-324 à 1,79x10308 pour les valeurs positives

29

Quelqu’un peut se demander pourquoi pas déclarer toutes les variables en réel double? Un bon algorithme ne se contente pas de « marcher » ; il marche en évitant de gaspiller les ressources de la machine. Sur certains programmes de grande taille, l’abus de variables surdimensionnées peut entraîner des ralentissements notables à l’exécution, voire un plantage pur et simple de l’ordinateur. 30

En pseudo-code, une déclaration de variables aura la forme suivante : Variable g en Numérique ou encore Variables PrixHT, TauxTVA, PrixTTC en Numérique

31

1.2 Types alphanumériques 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. ATTENTION: En pseudo-code, une chaîne de caractères est toujours notée entre guillemets.

32

1.3 Autres types numériques Certains langages autorisent d’autres types numériques, notamment : le type monétaire (avec strictement deux chiffres après la virgule) le type date (jour/mois/année).

33

1.4 Type booléen Le dernier type de variables est le type booléen : on y stocke uniquement les valeurs logiques VRAI et FAUX (ou 0 et 1).

34

2. L’instruction d’affectation: 2.1 syntaxe: Après avoir créer une variable on peut faire une et une seule chose: C’est qu’on puisse l’affecter, c’est-à-dire lui attribuer une valeur. C à d , on peut remplir la boîte.

35

En pseudo-code, l'instruction d'affectation se note avec le signe

36

Exemples d’affectation: A

10; on attribue à la variable A la valeur 10.

A

B ;on attribue à la variable A la valeur B.

A

10+B; la somme 10+B est attribuée à A. 37

2.2 ordre des instructions: L’ordre de succession des instructions affecte le résultat généré par un algorithme. Exemple1: Variable A en Numérique Début A ← 34 A ← 12 Fin Exemple 2 Variable A en Numérique Début A ← 12 A ← 34 Fin

38

Partie 2 Lecture et Ecriture

39

1.Introduction Soit l’algorithme suivant: Variable A en Numérique Début A ← 12^2 Fin D’une part, ce programme nous donne le carré de 12. C’est bon. Mais si l’on veut le carré d’un autre nombre que 12, il faut réécrire le programme. Casse tête!!! 40

D’autre part, le résultat est calculé par la machine. Mais elle le garde pour elle, l’utilisateur qui fait exécuter ce programme, lui, ne saura jamais quel est le carré de 12.

41

De là vient l’utilité des instructions qui permettent à l’utilisateur de dialoguer avec la machine. 42

Dans un sens, ces instructions permettent à l’utilisateur de rentrer des valeurs au clavier pour qu’elles soient utilisées par le programme.

Cette opération est la lecture. 43

Dans l’autre sens, d’autres instructions permettent au programme de communiquer des valeurs à l’utilisateur en les affichant à l’écran.

Cette opération est l’écriture. 44

2. Les instructions de lecture et d’écriture Pour que l’utilisateur entre la(nouvelle)valeur de A, on mettra :

Lire A Dès que le programme rencontre une instruction Lire, l’exécution s’interrompt, attendant la frappe d’une valeur au clavier. Dès lors, aussitôt que la touche Entrée a été frappée, l’exécution reprend. 45

Dans le sens inverse, pour écrire quelque chose à l’écran, c’est aussi simple que : Ecrire A 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.

46

EXEMPLE:

Ecrire "Entrez votre nom : " Lire Nom

47

Partie 3 Expressions et opérateurs

48

Expressions et opérateurs • Une expression peut être une valeur, une variable ou une opération constituée de variables reliées par des opérateurs exemples: 1, b, a*2, a+ 3*b-c, … • L'évaluation de l'expression fournit une valeur unique qui est le résultat de l'opération • Les opérateurs dépendent du type de l'opération, ils peuvent être : – – – –

des opérateurs arithmétiques: +, -, *, /, % (modulo), ^ (puissance) des opérateurs logiques: NON, OU, ET des opérateurs relationnels: =, , <, >, <=, >= des opérateurs sur les chaînes: & (concaténation)

≠ à droite mais en tenant • Une expression est évaluée de gauche compte de priorités 49

Priorité des opérateurs • Pour les opérateurs arithmétiques donnés ci-dessus, l'ordre de priorité est le suivant (du plus prioritaire au moins prioritaire) : – ^ : (élévation à la puissance) – * , / (multiplication, division) – % (modulo) on désigne par modulo l'opération de calcul du reste de la division euclidienne. Si a est un entier quelconque et n un entier strictement positif, on écrira a mod n pour représenter le reste dans {0, …, n−1} de la division de a par n. Par exemple, 26 mod 12 = 2. – + , - (addition, soustraction)

exemple:

2+3*7

vaut 23

• En cas de besoin (ou de doute), on utilise les parenthèses pour indiquer les opérations à effectuer en priorité exemple: (2 + 3) * 7 vaut 35 3

50

Partie 4 Les Fonctions Prédéfinies

51

» Structure générale des fonctions Une fonction est donc constituée de trois parties : » le nom proprement dit de la fonction. Exemple:SIN(sinus). » deux parenthèses, une ouvrante, une fermante. Ces parenthèses sont toujours obligatoires, même lorsqu'on n'écrit rien à l'intérieur. » une liste de valeurs, indispensables à la bonne exécution de la fonction. Ces valeurs s’appellent des arguments, ou des paramètres. Certaines fonctions exigent un seul argument, d’autres deux, etc. et d’autres encore aucun. 52

2. Les fonctions de texte

53

Une catégorie privilégiée de fonctions est celle qui nous permet de manipuler des chaînes de caractères.

54

Tous les langages presque, proposent peu ou prou les fonctions suivantes, même si le nom et la syntaxe peuvent varier d’un langage à l’autre :

55

•Len(chaîne) : renvoie le nombre de caractères d’une chaîne •Mid(chaîne,n1,n2) : renvoie un extrait de la chaîne, commençant au caractère n1 et faisant n2 caractères de long. Ce sont les deux seules fonctions de chaînes réellement indispensables. Mais il y a d’autres: •Left(chaîne,n) : renvoie les n caractères les plus à gauche dans chaîne. •Right(chaîne,n) : renvoie les n caractères les plus à droite dans chaîne •Trouve(chaîne1,chaîne2) : renvoie un nombre correspondant à la position de chaîne2 dans chaîne1. Si chaîne2 n’est pas comprise dans chaîne1, la fonction renvoie zéro. 56

Exemples : Len("Bonjour, ça va ?") vaut 16 Len("") vaut 0 Mid("Zorro is back", 4, 7) vaut "ro is b" Mid("Zorro is back", 12, 1) vaut "c" Left("Et pourtant…", 8) vaut "Et pourt" Right("Et pourtant…", 4) vaut "t…" Trouve("Un pur bonheur", "pur") vaut 4 Trouve("Un pur bonheur", "techno") vaut 0

57

Il existe aussi dans tous les langages une fonction qui renvoie le caractère correspondant à un code Ascii donné (fonction Asc), et (fonction Chr) : Asc("N") Chr(63)

vaut vaut

78 "?"

58

Partie 5 Les tests 59

1.INTRODUCTION Soit l’algorithmique du touriste égaré : « Allez tout droit jusqu’au prochain carrefour, puis prenez à droite et ensuite la deuxième à gauche, et vous y êtes ».Mais en cas de doute, cela pourrait devenir : « Allez tout droit jusqu’au prochain carrefour et là regardez à droite. Si la rue est autorisée à la circulation, alors prenez la et ensuite c’est la deuxième à gauche. Mais si en revanche elle est en sens interdit, alors continuez jusqu’à la prochaine à droite, prenez celle-là, et ensuite la première à droite ». Cela suppose que l’interlocuteur (le touriste) sache analyser la condition que nous avons fixée à son 60 comportement (« la rue est-elle en sens interdit ? »)

Mais les ordinateurs possèdent cette aptitude, sans laquelle d’ailleurs nous aurions bien du mal à les programmer. Nous allons donc pouvoir donner des séries d’instructions à effectuer selon que la situation se présente d’une manière ou d’une autre. Cette structure logique répond au nom de test. On parle aussi de structure

alternative.

61

2. Structure d’un test Il n’y a que deux formes possibles pour un test ; la première est la plus simple, la seconde la plus complexe. 1.structure simple Si booléen Alors Instructions Finsi

2.structure complexe Si booléen Alors Instructions 1 Sinon Instructions 2 Finsi 62

Explication Un booléen est une expression dont la valeur est VRAI ou FAUX. Deux cas de figures se présentent: • •

une variable (ou une expression) de type booléen une condition

1. Variable booléen:

Dans la forme simple, arrivé à la première ligne (Si… Alors) la machine examine la valeur du booléen. Si ce booléen a pour valeur VRAI, elle exécute la série d’instructions. En revanche, dans le cas où le booléen est faux, l'ordinateur saute directement aux instructions situées après le FinSi. 63

2. Condition: Une condition est une comparaison Cette définition est essentielle ! Elle signifie qu’une condition est composée de trois éléments : • une valeur • un opérateur de comparaison • une autre valeur Les valeurs peuvent être a priori de n’importe quel type (numériques, caractères…). Mais si l’on veut que la comparaison ait un sens, il faut que les deux valeurs de la comparaison soient du même type !

64

Les opérateurs de comparaison sont : •égal à… •différent de… •strictement plus petit que… •strictement plus grand que… •plus petit ou égal à… •plus grand ou égal à… NB: la comparaison concerne aussi les caractères: “t” < “w” VRAI “Maman” > “Papa“ FAUX “maman” > “Papa” VRAI (vérifier) 65

3. Conditions composées Certains problèmes exigent parfois de formuler des conditions qui ne peuvent pas être exprimées sous la forme simple. Soit le cas « X est compris entre 5 et 8 ». En fait cette phrase a deux conditions. Car elle revient à dire que « X est supérieur à 5 ET X est inférieur à 8 ». Il y a donc bien là deux conditions, reliées par ce qu’on appelle un opérateur logique(ET). Il existe opérateurs logiques : ET, OU,NON et XOR. 66

Ces opérateurs logiques peuvent être regroupés dans des tables de vérité (C1 et C2 représentent deux conditions, et on envisage à chaque fois les quatre cas possibles) C1 ET C2 C1 VRAI C1 FAUX C2 VRAI VRAI FAUX C2 FAUX FAUX FAUX C1 OU C2 C2 VRAI C2 FAUX NON C1 C1 VRAI C1 FAUX

C1 VRAI VRAI VRAI FAUX VRAI

C1 FAUX VRAI FAUX

67

4.Tests imbriqués EXEMPLE 1:

Variable Temp en Entier Début Ecrire "Entrez la température de l’eau :" Lire Temp Si Temp =< 0 Alors Ecrire "C’est de la glace" FinSi Si Temp > 0 Et Temp < 100 Alors Ecrire "C’est du liquide" Finsi Si Temp > 100 Alors Ecrire "C’est de la vapeur" Finsi Fin On test la même valeur 3 fois. C’est lourd!!! 68

EXEMPLE 2: Variable Temp en Entier Début Ecrire "Entrez la température de l’eau :" Lire Temp Si Temp =< 0 Alors Ecrire "C’est de la glace" Sinon Si Temp < 100 Alors Ecrire "C’est du liquide" Sinon Ecrire "C’est de la vapeur" Finsi Finsi Fin 69

Nous avons fait des économies : 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 « 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. 70

Partie 7 Les Tableaux

71

1. Utilité des tableaux Imaginons que dans un programme, nous ayons besoin simultanément de 12 valeurs (par exemple, des notes pour calculer une moyenne). Evidemment, la solution dont on dispose consiste à déclarer douze variables, après une succession de douze instructions « Lire » distinctes, cela donnera obligatoirement une atrocité du genre : Moy ← (N1+N2+N3+N4+N5+N6+N7+N8+N9+N10+N11+N12)/12

Ce n’est pas pratique et c’est laborieux. Et si nous somme devant dans un programme de gestion avec quelques centaines ou quelques milliers de valeurs à traiter!!! 72

SOLUTION C’est pourquoi la programmation nous permet de rassembler toutes ces variables en une seule, au sein de laquelle chaque valeur sera désignée par un numéro. Un ensemble de valeurs de même type et repérées par un nombre, s’appelle un tableau, ou encore une variable indicée. Le nombre qui, au sein d’un tableau, sert à repérer chaque valeur s’appelle l’indice. Chaque fois que l’on doit désigner un élément du tableau, on fait figurer le nom du tableau, suivi de 73 l’indice de l’élément, entre parenthèses.

2. Notation et utilisation algorithmique on crée donc un tableau appelé Note. Chaque note individuelle (chaque élément du tableau Note) sera donc désignée Note(0), Note(1), etc. Attention, les indices des tableaux commencent généralement à 0, et non à 1. Un tableau doit être déclaré comme tel, en précisant le nombre et le type de valeurs qu’il contiendra. Certains langages réclament le nombre d'éléments, d'autre le plus grand indice... C'est donc une affaire de conventions.

74

On décide arbitrairement et une fois pour toutes que : •les "cases" sont numérotées à partir de zéro, autrement dit que le plus petit indice est zéro (Tabl(0)). •lors de la déclaration d'un tableau, on précise le nombre de cases. Exemple:

Tableau Note(12) en Entier 75

L’énorme avantage des tableaux, c’est qu’on va pouvoir les traiter en faisant des boucles. Pour effectuer notre calcul de moyenne, cela donnera : Tableau Note(12) en Numérique Variables Moy, Som en Numérique Début Pour i ← 0 à 11 Ecrire "Entrez la note n°", i Lire Note(i) i Suivant Som ← 0 Pour i ← 0 à 11 Som ← Som + Note(i) i Suivant Moy ← Som / 12 76 Fin

3. Tableaux dynamiques Il arrive fréquemment que l’on ne connaisse pas à l’avance le nombre d’éléments que devra comporter un tableau. On a la possibilité de déclarer le tableau sans préciser au départ son nombre d’éléments. Ce n’est qu’au cours du programme, que l’on va fixer ce nombre via une instruction de redimensionnement : Redim.

77

Exemple : on veut faire saisir des notes pour un calcul de moyenne, mais on ne sait pas combien il y aura de notes à saisir. Le début de l’algorithme sera : Tableau Notes() en Numérique Variable nb en Numérique Début Ecrire "Combien y a-t-il de notes à saisir ?" Lire nb Redim Notes(nb) 78