Cours Algorithme -Notions de base-

Objectif : - Définir l'algorithme.

                 - Les structures de traitement(itératif, alternatif ...).

                 - Les structures de données ( tableaux, chaînes de caractères).  

Création d’un algorithme

Principe de résolution d’un problème informatique

Cahier des charges
¯
Analyse
¯
Algorithme
¯
Traduction
¯
Execution
¯
Test/validation

Le cahier des charges

Il contient :
-    l’énoncé du problème
-    la spécification des données
-    les conditions de fonctionnement

analyse

Elle permet d’avoir une idée claire des étapes à réaliser pour la résolution du problème donné, elle est rédigée en français.

Algorithme

On détaille à l’aide d’un langage adapté les différents traitements (ou étapes)

Traduction

Il s’agit de traduire les étapes précédentes en langage de programmation (C ou C++, voir JAVA)

Exécution

Elle doit permettre de vérifier que le programme fonctionne correctement

Tests/validation

Il s’agit de valider le respect du cahier des charges. Les tests permettent de valider le programme dans les conditions limites


Variable

Intro

Dans nos programmes informatiques, les instructions manipulent des objets ou des informations. Chaque objet possède trois qualificatifs.

 Identificateur

C’est le nom de l’objet.
    Ex : a, b, z, étudiant, nombre, …

* Toujours donner un identificateur en rapport  avec l’objet manipulé.

Le type
Il détermine l’ensemble de définitions dans lequel l’objet prend ses valeurs.
    Ex : entier, réel, caractère, …

La valeur

C’est un élément quelconque de l’ensemble de définition ou de l’objet.
    Ex : 5, 12, (entiers…)
    Ex : 3.8, 5.6, (réels…)
    Ex : a, r, (caractère…)

Cet objet est appelé variable quand sa valeur n’est pas constante.
Les variables peuvent être multidimensionnelles, elles sont alors déclarées sous forme de tableau.

* Un tableau est un ensemble de variables du même type.

    Ex : 1 dimension
V(N)=(v(0), v(1), v(2), …, v(n-1))

    Ex : 2 dimensions

Matrice [M][N] :
Mat(0)(0)………………………………….. Mat(n-1)(0)
    .                             .
    .                             .
Mat(0)(m-1)………………………………. Mat(n-1)(m-1)

 Exemple de calcul de moyenne

1ère étape : Cahier des charges. Réaliser un programme qui calcule la moyenne de 3 notes de partiels d’un étudiant. Les notes seront saisies au clavier. Le résultat sera affiché à l’écran.

2ème étape :
/*initialisation*/
saisie des trois notes
/*traitement*/
calcul de la moyenne des trois notes
moyenne=(note1+note2+note3)/3
/*résultat*/
afficher la moyenne à écran

3ème étape : algorithme
-    définition des variables utilisées données :
note1 : type réel
note2 : type réel
note3 : type réel
résultat : moyenne : type réel
-    algorithme et métalangage

Début    {
/*initialisation*/
Écrire (‘donner la 1ère note’)    Printf(« … »)
Lire (note1)    scanf(« %d », &note1)
Écrire (‘donner la 2ème note’)
Lire (note2)
Écrire (‘donner la 3ème note’)
Lire (note3)
/*traitement*/
moyenne¬(note1+note2+note3)/3
/*résultat*/
Écrire (‘la moyenne de l’élève est :’, moyenne)
Fin    }

Outils

Opérations logiques et mathématiques

Addition    +
Soustraction    -
Multiplication    *
Division    /          (a¬b a prend la valeur de b)
Affectation    <=       (a¬3 a prend la valeur de 3)
Égalité    =         (a=b vrai si a=b, faux si a¹b)
Différent    # (même principe que pour le =)
Supérieur    >
Supérieur ou égal   >=
Inférieur    <
Inférieur ou égal    <=
Et logique    ET    &
Ou logique    OU

Entrées/sorties

Écriture :

Écrire (‘…’)    affiche à l’écran
Écrire (‘…’, variable)

Lecture

Lire (variable)                    saisie au clavier, valeur mise dans ‘variable’

Algèbre de Boole

Conventions :

Soit a un interrupteur. Il peut être ouvert ou fermé
Par convention :
-    a ouvert =>a=0, FAUX
-    a fermé  =>a=1, VRAI

a est une variable booléenne
Soit l une lampe. Elle peut être allumée ou éteinte.
-    l allumée l=1 =>VRAI
-    l éteinte   l=0 =>FAUX
Soit a, b, et l. la lampe est allumée si a et b sont fermés. Table de vérité :

Structure de contrôle

Structures conditionnelles

Appelées aussi structures alternatives,, elles permettent un choix d l’action à exécuter suivant qu’une condition soit remplie ou non.

Branchement simple

Si (condition) alors        If(…)
    Début            réalisé si la condition est vraie
      .
      .
    Fin
Sinon                else


Début            réalisé si la condition est faux (optionnel)
      .
      .
    Fin

Branchement multiple

Suivant (variable)
Si valeur1 faire        réalisé si variable=Valeur1
    Début
      .
    Fin
Si valeur2 faire
    Début
      .
    Fin
Si valeurn faire
    Début
      .
    Fin
Par défaut faire        optionnel
    Début
      .
    Fin

Structures répétitives

Aussi appelée structure interactive, elles permettent d’exécuter une suite d’instructions ou d’actions un certains nombre de fois (boucle). Nous distinguons 3 types :
-    tant que (condition de maintient) faire
-    répéter tant que (condition de maintient)
-    pour (variable) variation de Vini à Vfinal

métalangage :
1.    Tant que (condition de maintient) faire
    début            réalisé tant que la condition est vraie
    .            while(…){…}
    fin
2.    Répéter
    début            do {…} while(…)
    .
    fin
tant que (condition de maintient)
3.    Pour variable allant de Vi à Vf avec un pas de Ic faire
    début
    .
    fin

Nb : ces trois structures sont très proches et interchangeables.

Les tableaux

Ils peuvent être à une dimension, sous la forme d’une colonne ou d’une ligne, et s’écrivent comme suit :

Nom_du_tableau[X]
X représente le nombre de cases du tableau.
Pour entrer des nombre dans un tableau, il faut définir sur quelle case on veut écrire. On utilise pour cela un FOR :
For (i=0 ; i<X ; I++)
{scanf(“%d”, &tab[I]);}
cela signifie que pour toutes les cases du tableau allant de 0 à I, la valeur rentrée sera affectée a la case i.
pour un tableau à deux dimensions, la déclaration se fait nom_du_tableau[X][Y]. compter deux FOR, avec un saut de ligne entre les deux :
For(i=0 ; i<X ; i++)
{printf(« \n ») ;
for (j=0; j<Y; j++)
{scanf (« %d », &tab[i][j]);}}
cela affichera un tableau standard avec X colonnes, et Y lignes.

Les structures

Elles permettent de regrouper plusieurs éléments dans une mémoire. Exemple : une structure qui retiens le jour, la date et le mois d’anniversaire pour plusieurs personnes. Elle a un peu la même fonction qu’un tableau mais en plus simplifiée.

Le sous programme (ou fonction)

Il permet de faire appel à une partie de programme que l’on va réutiliser plusieurs fois, ou alors pour éviter de surcharger le programme principal. Par exemple : on fait un programme qui demande la date, puis qui la réutilise plusieurs fois après.
La fonction peut retourner une information au programme principal (comme pour la date), ou ne rien renvoyer (affichage)