Logo FST

Algorithmique

Introduction et concepts élémentaires



Faculté des sciences
  1. Bases de l'Algorithmique
    • Introduction
    • Types, variables et opérateurs
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

  3. Les fonctions
  1. Bases de l'Algorithmique
    • Introduction
    • Types, variables et opérateurs
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

  3. Les fonctions

Les instructions structurées

Qu'avons nous appris ?

  • Lire/écrire des données dans la mémoire de la machine
  • Lui ordonner de faire des calculs (avec des opérateurs)


Le tout s'effectue séquentiellement. Les instructions structurées vont nous permettre :

  • Définir des blocs d'instructions
  • Casser l'exécution séquentielle d'un algorithme

Les instructions conditionnelles

Elles permettent d'exécuter un bloc d'instructions si et seulement si une condition choisie est satisfaite.


Supposons par exemple devoir diviser un nombre a par un nombre b. La division par zéro étant impossible, ce calcul ne peut être réalisé que si b est différent de 0.


Bloc Conditionnel :
"Si (expression booléenne) alors" ? Dire

Instruction conditionnelle simple

Syntaxe :

if ( /* expression booléenne */ ) // l'expression se place entre parenthèses
{ // l'accolade ouvrante indique le début du bloc d'instructions
	
	/* bloc d'instructions */

} // l'accolade fermante indique la fin du bloc d'instructions

Principe :
  • si l'expression vaut true, les instructions du bloc seront exécutées
  • si l'expression vaut false, le bloc est ignoré
  • Attention, le si.... n'est pas une instruction : pas de ; à la fin

Instruction conditionnelle simple

Revenons à la problématique suivante : Comment dire à la machine "Si b est différent de 0, alors calcule a/b" ?



// Déclaration des variables
int a, b, division;

// Instructions du programme
std::cout << "Saisir les valeurs de a et de b " << std::endl;
std::cin >> a >> b ;
if ( b != 0 )
{
	division = a / b;
	std::cout << "La division de a par b est " << division  << std::endl;
}

Instruction conditionnelle complète

Dire
Principe :
  • si l'expression vaut true, les instructions du premier bloc seront exécutées
  • sinon ce sont les instructions du second bloc qu'on exécute

Instruction conditionnelle complète

Syntaxe :

					

if ( /* expression booléenne */ )
{ // l'accolade ouvrante 
	
/* bloc d'instructions à exécuter
   si l'expression booléenne vaut true */

} // l'accolade fermante 
else
{
/* autre bloc d'instructions à exécuter
   si l'expression booléenne vaut false */
}
Principe :
  • si l'expression vaut true, les instructions du premier bloc seront exécutées
  • sinon ce sont les instructions du second bloc qu'on exécute

Instruction conditionnelle complète

Exercice :

Même exercice que le précédent mais on vous demande de faire afficher "division par zéro interdite" si le cas se produit.


// Déclaration des variables
int a, b, division;


// Instructions du programme
std::cout << "Saisir les valeurs de a et de b " << std::endl;
std::cin >> a >> b ;
if ( b != 0 )
{
    division = a / b;
    std::cout << " La division de " << a << " par " << b << " est égale à "  << division << std::endl;
}
else
{
     std::cout << " La division par zéro est interdite" << std::endl;
}
 

Instructions conditionnelles
imbriquées

Un bloc d'instructions peut contenir d'autres instructions conditionnelles.


if ( ... ) 
{ 
	if (...)
	{
	    ...
	}
	else
	{
	    ...
	}	
} 
else
{
	if (...)
	{
	    ...
	}
	else
	{
	    ...
	}	
}

Instructions conditionnelles
imbriquées

Exercice :

Ecrire un algorithme qui demande à l'utilisateur de saisir un nombre entre 1 et 7
On ne demande pas de vérifier que le nombre entier saisi est bien compris entre 1 et 7, on supposera que c'esr toujours le cas.
Puis en fonction du nombre saisi, le programme affiche le nom du jour de la semaine correspondant. Par exemple "lundi" pour 1, "mardi" pour 2 etc...

Instructions conditionnelles
imbriquées

Solution :

// Déclaration des variables
int jour;

// Instructions du programme
std::cout << "Saisir un nombre entier entre 1 et 7 \n";
std::cin >> jour ;
if ( jour == 1 ) 
    std::cout << "lundi";
else
{
    if ( jour==2 )
        std::cout <<"mardi";
    else
    {
        if ( jour==3 )
            std::cout <<"mercredi";
        else
        {
            if ( jour==4 )
               std::cout <<"jeudi";
            else
            {
                if ( jour==5 )
                    std::cout <<"vendredi";
                else
                {
                    if ( jour==6 )
                        std::cout <<"samedi";
                    else
                        std::cout <<"dimanche";
                }
            }
        }
    }	
}

Instructions conditionnelles
imbriquées

Notons au passage :

  • pour un block qui ne contient qu'une seule instruction, on n'est pas obligé de le délimiter par une accolade ouvrante et une accolade fermante.
  • le grand nombre d'imbrications rend le code moins évident à lire. Ce qui le garde lisible, c'est l'indentation ! Chaque fois que l'on commence un nouveau bloc, on augmente la marge d'une tabulation ou de 4 espaces. C'est primordial pour la lisibilité et donc la compréhension du code.
  • Vous ne me croyez ? Voyez plutôt la diapo suivante qui vous présente le même code mais non indenté.

Instructions conditionnelles
imbriquées


/* Même solution mais non indenté...
   Notez que je ne corrigerai pas vos programmes s'ils sont mal indentés. */
// Déclaration des variables
int jour;

// Instructions du programme
std::cout << "Saisir un nombre entier entre 1 et 7 \n";
std::cin >> jour ;
if ( jour == 1 ) 
std::cout << "lundi";
else
{
if ( jour==2 )
std::cout <<"mardi";
else
{
if ( jour==3 )
std::cout <<"mercredi";
else
{
if ( jour==4 )
std::cout <<"jeudi";
else
{
if ( jour==5 )
std::cout <<"vendredi";
else
{
if ( jour==6 )
std::cout <<"samedi";
else
std::cout <<"dimanche";
}
}
}
}	
}

Instructions conditionnelles
imbriquées

Dans le cas d'un "Si, sinon si, sinon si, .... sinon", et seulement dans ce cas, on peut utiliser la syntaxe équivalente suivante pour une meilleure lisibilité :


if (...) 
{ 
	...
} 
else if (...)
{
	...
}
else if (...)
{
	...
}
...
else
{
	...	
}

Instructions conditionnelles
à choix multiple

L'exercice précédent peut s'écrire d'une manière plus efficace

En utilisant l'instruction switch

Syntaxe :


				
switch (variable) 
{ 
   case valeur1 :
      instruction1;
      break;
   case valeur2,valeur3 : 
      instruction2;
      instruction2bis;
      break;
   .
   .
   .
   default:
      instructionDefaut;
      break;	
}


if (variable == valeur1)
   instruction1;
else if (variable == valeur1 || variable == valeur2)  
{
    instruction2;
    instruction2bis;
}  
.
.
.
else {
   instructionDefaut;
}
}

Instructions conditionnelles
à choix multiple

L'exercice précédent peut s'écrire :


// Déclaration des variables
int jour;

// Instructions du programme
std::cout << "Saisir un nombre entier entre 1 et 7 \n";
std::cin >> jour ;
switch (jour)
{
case 1:
  std::cout << "Lundi";
  break;
case 2:
  std::cout << "Mardi";
  break;
case 3:
  std::cout << "Mercredi";
  break;
case 4:
  std::cout << "Jeudi";
  break;
case 5:
  std::cout << "Vendredi";
  break;
case 6:
  std::cout << "Samedi";
  break;
case 7:
  std::cout << "Dimanche";
  break;
default:
  std::cout << "Erreur";
  break;

}




Instructions conditionnelles
à choix multiple

Précisions sur l'instruction switch

  • Ne fonctionne qu'avec des variables de type int et char
  • En C++, le système, après avoir reconnu une valeur, continue a effectuer les instructions suivantes
  • L'instruction break sert a briser l'execution du programme et a passer directement a l'instruction suivant l'accolade fermante
  • L'instruction break est donc indispensable lors d'un switch

Instructions de répétition :
Les boucles

Nous sommes encore limités...

Par exemple, pouvez-vous écrire un programme qui affiche 6 fois la chaîne "Bonjour" ?


On ne vous fera pas l'offense de penser le contraire ! Mais pouvez vous en écrire un qui affiche 1 million de fois la chaîne "Bonjour" ? Surtout en avez vous le temps (et l'envie !) ?


Il faut utiliser l' instruction : Dire

La boucle for

Syntaxe :

int i; // déclaration d'une variable entière qui sera l'indice de la boucle

for ( i=n; i<=m; i++ ) // n et m sont deux entiers
{ 
    /* bloc d'instructions à répéter */
}
Principe :
  • la boucle for permet de répéter le bloc d'instructions qui la suit un certain nombre de fois
  • le nombre de répétitions (ou tours de boucle) est choisi grâce à l'indice de boucle, ici la variable i. L'indice de boucle est le "compteur" de la boucle.
    • i=n; fixe la valeur initiale de i, la variable "compteur"
    • i<=m; fixe la valeur maximale de i. La boucle tourne tant que i<=m est vrai
    • i++ est la contraction de i=i+1. Indique que i augmente de 1 à chaque tour

La boucle for

Exercice :

Ecrire un algorithme qui affiche 1 million de fois "Bonjour".


int i; 

for ( i=1; i<=1000000; i++ ) 
{ 
    std::cout << "Bonjour" << std::endl;
}
Principe :
  • i vaut 1, donc i<=1000000 est vrai, donc le bloc est exécuté une première fois et i augmente de 1
  • i vaut 2, donc i<=1000000 est vrai, donc le bloc est exécuté une seconde fois et i augmente de 1
  • ...
  • i vaut 1 million, donc i<=1000000 est vrai, donc le bloc est exécuté une millionième fois et i augmente de 1
  • i<1000000 est maintenant faux ! La boucle s'arrête et le programme continue

La boucle for

Exercice :

Variante : Ecrire un algorithme qui affiche "Bonjour" Autant de fois qu'un nombre entier préalablement saisi par l'utilisateur.


int i, nb; 

std::cout << "Saisir le nombre de bonjour " ;
std::cin >> nb;
std::cout << std::endl;
for ( i=1; i<=nb; i++ ) 
   std::cout << "Bonjour" << std::endl;

std::cout << "Saisir le nombre de bonjour " ;
std::cin >> nb;
std::cout << std::endl;
for ( i=0; i<nb; i++ ) 
   std::cout << "Bonjour" << std::endl;

Notes :

  • les accolades délimitant le bloc sont optionnelles s'il ne contient qu'une instruction
  • ces deux solutions sont équivalentes, le nombre de tour est toujours le même.

La boucle for

Exercice :

Ecrire un algorithme qui demande la saisie d'un nombre entier n et qui affiche ensuite tous les nombres de 1 à n.


int i, n; 
std::cout << "Saisir un entier positif " ;
std::cin >> nb;
for ( i=1; i<=n; i++ ) 
    std::cout << i << " ";

Note :

  • utiliser l'indice de boucle dans le bloc de la boucle est très fréquent et très pratique !

La boucle for

Quand l'utiliser ?

Utiliser une boucle for suppose de connaître par avance le nombre de tours à effectuer.


Limitation

On peut avoir besoin de répéter des instructions sans pour autant savoir combien de fois par avance !

Les instructions de répétition

Exemple

Un programme doit poser une question à l'utilisateur qui doit y répondre par oui ou par non en frappant sur le caractère 'o' ou 'n'. Dans le cas contraire la question doit lui être posée à nouveau.


Ici on ne peut pas prédire le nombre de tentatives dont l'utilisateur aura besoin. Par conséquent une boucle for est inutilisable. Mais ce n'est pas le seule type de boucle qui existe :

Dire
Attention, l'instruction scratch est "inversée" par rapport au C++ !

La boucle while

Syntaxe :

while ( /* expression booléenne */ )
{ 
    /* bloc d'instructions à répéter */
} 
Principe :
  • la boucle while permet de répéter le bloc d'instructions qui la suit jusqu'à ce qu'une expression booléenne devienne fausse
  • lorsque l'expression devient fausse, la boucle s'arrête et le programme continue
  • attention, il faut être certain que l'expression booléenne puisse devenir fausse à un moment donné si l'on ne veut pas rester "coincé" dans la boucle

La boucle while

Exercice :

Poser la question "Avez-vous compris ?" jusqu'à ce que l'utilisateur réponde oui en frappant sur la lettre 'o'.


char reponse='n';

while ( reponse!='o' )
{ 
    std::cout << "Avez-vous compris ?" ;
    std::cin >> reponse;
} 

Notes :

  • Quelle est l'importance de l'initialisation de la variable reponse ici ?
  • Que se passera-t-il si reponse est initialisée avec le caractère 'o' ?

La boucle do while

Syntaxe :

do
{ 
    /* bloc d'instructions à répéter */
}
while  ( /* expression booléenne */ );
Principe :
  • comme la boucle while, sauf que le bloc est forcément exécuté au moins une fois !
  • attention à ne pas oublier le point-virgule dans ce cas

La boucle do while

Exercice :

Poser à l'utilisateur la question "Avez-vous compris ?" jusqu'à ce qu'il réponde oui en frappant sur la lettre 'o'.


char reponse;

do
{ 
  std::cout << "Avez-vous compris ?" ;
    std::cin >> reponse;
}
while ( reponse!='o' ); 

Notes :

  • même exercice que précédemment mais une solution avec une boucle do while
  • reponse n'est pas initialisée à sa déclaration, est-ce toujours un problème ?

Les boucles : Exercice

Le jeu du nombre mystère

Le but est de faire deviner à l'utilisateur un nombre entier choisi aléatoirement entre 0 et 99. A chaque proposition du joueur, la machine indique si le nombre proposé est plus petit ou plus grand que le nombre à deviner. Lorsque le bon nombre est trouvé, la machine affiche un message de félicitations.

On utilisera l'instruction rand() qui génère aléatoirement (ou presque) un nombre compris entre 0 (inclus) et RAND_MAX(exclu).
Par exemple float nb_alea = (float)rand() / (1.0 + RAND_MAX); initalisera nb_alea avec une valeur entre 0 et 1.0.
Aussi int adeviner = (int) (100.0 * rand() / (1.0 + RAND_MAX)); initialisera adeviner avec une valeur entre 0 et 99.
L'écriture (int)(...) commande à la machine de convertir l'expression entre parenthèse en nombre entier. Dans le cas d'un nombre réel, seule la partie entière sera conservée. Par exemple (int)( 73.234 ) donnera 73.

Les boucles : Exercice

Le jeu du nombre mystère

int proposition, adeviner = (int)(100.0 * rand()/(1.0 + MAX_RAND));

do
{ 
    std::cout << "Proposer un nombre entre 0 et 99 :"<< std::endl;
    std::cin >> proposition;

    if ( proposition < adeviner )
    	std::cout << "Trop petit !" << std::endl;
    else if ( proposition > adeviner )
    	std::cout << "Trop grand"<< std::endl;
    else
    	std::cout << "Félicitations ! C'était bien " << adeviner<< std::endl;
}
while ( proposition != adeviner ); 

Notons au passage :

  • quelle est la façon la plus rapide pour gagner ? Enumérer les nombres de 0 à 99 ? Ou bien avez-vous une meilleure idée ?
  • la stratégie à laquelle vous avez probablement pensée très rapidement s'appelle la recherche par dichotomie ! Un grand classique en algorithmique !

Les boucles imbriquées

Principe

Le bloc d'instructions d'une boucle peut contenir d'autres boucles bien sûr ! On parle alors de boucles imbriquées



Attention

Des boucles imbriquées ne sont pas indépendantes les unes des autres. De fait, il faudra faire attention à utiliser un indice de boucle différent pour chacune !

Les boucles imbriquées

Exercice

Afficher à l'écran les tables de multiplication de 1 à 10. Au besoin, afficher d'abord la table de 1, puis modifier votre code pour afficher les tables de 1 à 10.


int i, j;

for( i=1; i<=10; i++)
{
    std::cout << "Table de multiplication de " << i << std::endl;
    for( j=1; j<=10; j++)
    {
        std::cout << i << " x " << j << " = " << i*j << std::endl;
    }
}

Erreurs :
Les grands classiques

L'infini existe, et vous allez vous y perdre !

int x;

do
{
	x = 1;
	x = x + 1;
}
while( x<10 );
  • le risque avec une boucle, c'est de ne jamais en sortir
  • pour en savoir un peu plus, clic
  1. Bases de l'Algorithmique
    • Introduction
    • Types, variables et opérateurs
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

  3. Les fonctions

Limites des données élémentaires

Comment regrouper des données de même type ?

Supposons devoir saisir les noms d'une promotion d'étudiants. En l'état de nos connaissance, il faut :

  • déclarer une variable de type string par étudiant
  • affecter chaque variable une par une


Oui mais...

De la sorte, on ne matérialise pas du tout l'appartenance à un même ensemble (la promotion)

Limites des données élémentaires

Exemple

On souhaite saisir 6 notes et les afficher de la plus petite à la plus grande



C'est faisable mais...

... ce n'est pas extensible. Avec 16 notes il faudra 10 variables de plus et le code pour les ordonner va très vite devenir illisible. De plus si on ne connait pas par avance le nombre de notes à saisir, on ne sait pas faire.

Limites des données élémentaires

L'origine de ces problèmes, c'est notre incapacité à définir un ensemble de données homogènes



Solution

Regrouper des éléments de même type au sein d'une collection d'éléments. Pouvoir parcourir cette collection et si besoin accéder facilement à chaque élément.

Tableaux unidimensionels

Description

Un tableau regroupe un nombre n d'éléments de même type. Chaque case du tableau est identifiée par un indice allant de 0 jusqu'à n-1. n est aussi appelé la taille du tableau


Illustration
illustration de la structure de tableau

Tableaux unidimensionels

Déclaration d'un tableau

// déclaration d'un tableau d'entiers de taille 8
int int_tab[8];

// déclaration d'un tableau de caractères de taille 1024
char car_tab[1024] ;

// déclaration d'un tableau de booléens de taille 256
bool b_tab[256] ;

// déclaration d'un tableau de 28 chaînes
string chaine_tab[25] ;
  • De manière générale, la syntaxe est : nom_du_type nom_du_tableau[taille (constante)];
  • côté machine, le type des éléments du tableau lui permet de définir combien d'octets occupera une case
  • ensuite, fixer la taille du tableau à n lui permet de réserver n places/cases consécutives en mémoire pour y ranger des valeurs du type indiqué
  • c'est important car c'est parce que les éléments se suivent en mémoire que l'on peut les manipuler par leur indice de tableau
  • Les réservations sont ici faites de manière statique, c.a.d. lors de la phase de compilation

Tableaux unidimensionels

(Apparté) Dimensionner un tableau dynamiquement

// déclaration d'un tableau d'entiers de taille 8 
int* int_tab = new int[8]:

// déclaration d'un tableau de 1024 caractères
char* car_tab = new char[1024];

// déclaration d'un tableau de booléens de taille 256
bool* b_tab = new boolean[256];

// déclaration d'un tableau de 28 chaînes
string* chaine_tab= new string[28];
  • Les reservations de places sont ici crées de manière dynamique (lors de l'éxecution du programme)

Tableaux unidimensionels

Accès aux éléments d'un tableau

Pour accéder (en lecture ou écriture) à un élément dans un tableau, on utilise l'indice de la case qui le contient.
Syntaxe : nom_du_tableau[ indice_de_la case ]



int sum;
int tab[4]; // tableau de taille 4 

tab[0] = 10; // affecte 10 à la case d'indice 0
tab[1] = 2;  // affecte  2 à la case d'indice 1
tab[2] = 23; // affecte 23 à la case d'indice 2
tab[3] = 99; // affecte 99 à la case d'indice 3

sum = tab[0] + tab[3]; // sum vaut 109
  • Attention, l'indice doit obligatoirement être compris entre 0(inclus) et la taille du tableau (exclue)

Tableaux unidimensionels

Exercice

Ecrire un algorithme qui initialise toutes les cases d'un tableau de 1024 entiers à -1


int i;
int tab[1024]; 

for(i=0; i<1024; i++)
    tab[i] = -1;

Même question mais en remplissant chaque case avec les entiers de 1 à 1024


int i;
int tab[1024]; 

for(i=0; i<1024; i++)
    tab[i] = i+1;
  • Boucles et tableaux font bon ménage. Utiliser l'indice d'une boucle for pour parcourir les indices d'un tableau est incontournable

Tableaux unidimensionels

Exercice

Ecrire un algorithme pour saisir 28 notes dans un tableau.



const int nb_notes = 28;
double notes[nb_notes];  // le tableau
int i; // indice de boucle pour le parcours du tableau

std::cout << "Saisir les " << nb_notes << " notes\n";
// saisie des notes dans le tableau
for(i=0; i<nb_notes; i++)
    std::cin >> notes[i] ;

  • On utilise ici la constante nb_notes pour conserver la longueur du tableau
  • Cela évite de modifier à la main le programme en entier si on souhaite changer la taille du tableau

Tableaux unidimensionels

Exercice

Modifier le programme précédent pour en plus calculer la moyenne des 28 notes


const int nb_notes = 28;
double notes[nb_notes];  // le tableau
int i; // indice de boucle pour le parcours du tableau
double avg = 0.0; // pour calculer la moyenne

std::cout << "Saisir les " << nb_notes << " notes\n";
// saisie des notes dans le tableau
for(i=0; i<nb_notes; i++)
    std::cin >> notes[i] ;

// calcul de la somme de toutes les notes
for(i=0; i<nb_notes; i++)
    avg = avg + notes[i];

std::cout << " La moyenne est : " << avg/(float)nb_notes << std::endl;
  • chaque tour de boucle ajoute à avg une note de plus
  • on pourrait n'utiliser qu'une boucle en cumulant les notes au fur et à mesure ou elles sont saisies

Tableaux unidimensionels

Exercice

Pour finir, faites en sorte de demander à l'utilisateur le nombre de notes à saisir pour ne plus être restreint à 28 notes


double* notes;  // le tableau non dimensionné
int i; // indice de boucle pour le parcours du tableau
int nb_notes; // nombre de notes à saisir
double avg = 0.0; // pour calculer la moyenne

std::cout << "Combien de notre à saisir ?" << std::endl;
std::cin >> nb_notes ;
notes = new double[ nb_notes ];

std::cout << "Saisir les " << nb_notes << " notes\n";
// saisie des notes dans le tableau
for(i=0; i<nb_notes; i++)
    std::cin >> notes[i];

// calcul de la somme de toutes les notes
for(i=0; i<nb_notes; i++)
	avg = avg + notes[i];

std::cout << "La moyenne est : " << avg/(float)nb_notes << std::endl;

Tableaux unidimensionels

Limite des tableaux unidimensionels

Les données sont souvent structurées. Par exemple un chevalet de scrabble possède une structure qui correspond à un tableau 1D. Mais le plateau de jeu du scrabble possède une structure difficile à représenter avec un tableau 1D.

Autre exemple : une image bitmap possède une structure 2D. Nous aurons du mal à la représenter avec un tableau 1D. Car la dimension de la structure des données ne correspond pas !

Tableaux unidimensionels

Moralité

Pour bien représenter des données, pouvoir les manipuler efficacement, il faut utiliser des structures capables de reproduirent l'organisation intrinsèque de ces données.

  1. Les tableaux
    • Introduction
    • Types, variables et opérateurs
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

  3. Les fonctions

Tableaux bidimensionels

Description

Un tableau 2D est une structure de grille caractérisée par son nombre l de lignes et sont nombre c de colonnes, respectivement numérotées de 0 à l-1 et de 0 à c-1.

Un tableau 2D stocke l x c éléments de même type. L'emplacement d'un élément est identifié par les indices de ligne et de colonne à l'intersection desquelles il se trouve.


Tableaux bidimensionels

Illustration
illustration de la structure de tableau 2D

Tableaux bidimensionels

Déclaration d'un tableau 2D

// déclaration d'un tableau 2D d'entiers
int int_tab[10][10];

// déclaration d'un tableau 2D de caractères
char car_tab[10][10];

// déclaration d'un tableau 2D de booléens
bool b_tab[10][10];

// déclaration d'un tableau 2D de chaînes
string chaine_tab[10][10];
  • De manière générale, la syntaxe est : nom_du_type nom_du_tableau[ligne][colonne];
  • Attention, définir la taille des tableaux de manière dynamique requiert en C++ une mécanique plus complexe. Nous nous contenterons pour ce semestre de tableaux 2D statiques (de taille connue lors de la compilation)

Tableaux bidimensionels

Notez au passage

// type entier
int value;

// type tableau 1D de valeurs de type entier
int tab1D[l] ;

//  type tableau 2D de valeurs de type entier
int tab2D[l][c];

// valable quelque soit le type de départ bien sûr

// type tableau 3D de valeurs de type entier !
int tab3D[l][c][z];

// et ainsi de suite... mais on s'arrêtera à la 2D.

Tableaux bidimensionels

Accès aux éléments d'un tableau 2D

Pour accéder à un élément dans un tableau 2D, on utilise l'indice de la ligne et de la colonne qui identifient la case qui le contient. Syntaxe :
nom_du_tableau[ indice_de_la_ligne ][indice_de_la_colonne]


int sum;
int tab[4][8]; // tableau 2D de 4 lignes et 8 colonnes
 
tab[0][7] = 10; // affecte 10 à la case de coordonnées (0, 7)
tab[1][0] = 2;  // affecte  2 à la case de coordonnées (1, 0)
tab[3][3] = 99; // affecte 99 à la case de coordonnées (3, 3)

sum = tab[0][7] + tab[3][3]; // sum vaut 109
  • Attention, les indices de lignes et colonnes doivent obligatoirement être compris entre 0(inclus) et respectivement le nombre de lignes (exclu) et le nombre de colonnes (exclu)

Tableaux bidimensionnels

Exercice

Ecrire un programme qui permet de saisir case par case le contenu d'un tableau 2D représentant les notes dans 12 modules obtenu par 28 étudiants


int l, c;
double notes[28][12];

for( l=0; l<28; l++)
{
    for( c=0; c<12; c++)
    {
    std::cout << "Note de l'étudiant" << l << " pour le module " << c << std::endl;
    	std::cin >> notes[l][c] ;
    }
}
  1. Bases de l'Algorithmique
    • Introduction
    • Types, variables et opérateurs
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

  3. Les fonctions

L'analyse globale

C'est à dire ?

L'analyse globale est une approche qui consiste à appréhender un problème dans sa totalité pour écrire un programme qui va le résoudre



Pas toujours envisageable...

Si le problème devient complexe, il devient aussi difficile de l'appréhender dans sa globalité :

  • calculer la somme des nombres de 1 à n : ça va.
  • réaliser un simulateur de formule 1 : moins évident.

Notez que...

Ce n'est pas spécifique à l'algorithmique !
  • cuire des pâtes / feuilleté de tartare et émultion de foie gras
  • faire un avion en papier / faire une fusée Ariane 5



La solution : diviser pour mieux règner

Un problème trop complexe doit être décomposé en sous problèmes moins complexes.

L'analyse descendante

Subdiviser un problème en sous-problèmes de sorte que
  • chaque problème est indépendant des autres
  • chaque problème est plus simple à résoudre



Un sous-problème peut lui-même être re-subdivisé
  • on descend à un niveau d'analyse inférieur

Fonction

Définition
  • une fonction est un sous-programme
  • elle possède ses propres entrées et sortie
  • on peut y faire appel chaque fois qu'on en a besoin



Intérêts d'une fonction
  • décomposer un programme complexe en sous-programmes élémentaires
  • réutiliser le code !
  • structurer et clarifier le code

Analyse descendante et fonctions

Analyse descendante
  • Problème global
    • sous-problèmes
      • sous-problèmes



Décomposition d'un programme
  • Fonction principale (main)
    • fonctions
      • fonctions

Communiquer avec des fonctions

Question

Une fonction traite un problème et donc en général, elle aura besoin qu'on lui fournisse des données à traiter. Eventuellement nous aurons aussi besoin de récupérer le résultat de ce traitement.



Notion de paramètre et valeur de retour

Ces notions permettent de communiquer avec une fonction

  • les paramètres permettent de transmettre des données existantes à une fonctions
  • la valeur de retour permet de récupérer une nouvelle donnée créée par une fonction
  1. Bases de l'Algorithmique
    • Introduction
    • Types, variables et opérateurs
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

  3. Les fonctions

Déclarer une fonction

C'est-à-dire ?

Déclarer une fonction c'est :

  • l'identifier par un nom
  • identifier les types des données dont elle a besoin (ses paramètres)
  • identifier le type de donnée qu'elle produit (sa valeur de retour)
  • écrire le code qu'elle réalisera si on l'appelle


Notez bien
  • une fonction non déclarée n'existe pas
  • une fonction jamais appelée ne sert à rien

Déclarer une fonction

Syntaxe

rtype function_name ( ptype1 pname1, ptype2 pname2...)
{
    // code de la fonction
}

  • function_name est le nom de la fonction
  • rtype est le type de la valeur retournée par la fonction
  • ptype1, ptype2... sont les types ses paramètres
  • pname1, pname2... sont les noms ses paramètres


Déclarer et appeler une fonction

Fonction sans paramètre, sans valeur de retour

// fonction sans paramètre, sans valeur de retour (void = rien)
void doSomething()
{
    // ici le code de la fonction doSomething
    ...
}

// fonction principale main (elle aussi sans paramètre mais avec une valeur de retour)
int main()
{
    // appel à la fonction doSomething depuis la fonction main
    doSomething();
}
  • void signifie "rien" : rien n'est retourné par la fonction
  • doSomething est la fonction appelée, main est la fonction appelante
  • la machine exécute toujours en premier le code de la fonction principale.
  • l'appel à doSomething provoque l'exécution de son code.
  • puis l'exécution du code de la fonction main se poursuit.
  • En C/C++, la fonction principale retourne un entier (un code d'erreur/execution)

Déclarer et appeler une fonction

Exercice

Ecrire une fonction qui affiche un smiley dessiné en ASCII. Puis écrire un programme qui permet de l'afficher autant de fois que l'utilisateur le souhaite.


void smiley()
{
    std::cout << " (\___/) " << std::endl;
    std::cout << " (='.'=) "<< std::endl;
    std::cout << " (¨)_(¨) "<< std::endl;
}

void main()
{
    int i, nb;
    std::cout << "Nombre de fois : " << std::endl;
    std::cin >> nb;

    for(i=1; i<=nb; i++)
        smiley();
}

Déclarer et appeler une fonction

Exercice

Ecrire une fonction qui affiche la table de multiplication par 7 et une autre fonction qui affiche la table de 5. Faites un programme qui affiche ces 2 tables.


void tableDe5()
{
    int i;

    for(i=0; i<=10; i++){
        std::cout << "5 x " << i << " = " << 5*i << std::endl;
    }
}

void tableDe7()
{
    int i;

    for(i=0; i<=10; i++){
        std::cout << "7 x " << i << " = " << 7*i << std::endl;
    }
}

int main()
{
    tableDe5();
    tableDe7();
}

Portée d'une variable locale

Dans l'exercice précédent, deux variables i sont déclarées :

  • l'une dans tableDe5
  • l'autre dans tableDe7


Elles sont sans aucun rapport !

L'existence d'une variable déclarée à l'intérieur d'une fonction est limitée à cette fonction. On dit que la variable est locale à la fonction et que sa portée est restreinte à la fonction.

Il y a la variable i de la fonction tableDe5 et la variable i de la fonction tableDe7.

Une fonction n'a aucune connaissance des variables d'une autre fonction et réciproquement.

Déclarer et appeler une fonction

Fonction avec paramètre(s), sans valeur de retour

// fonction avec un paramètre de type int nommé toto
void doSomething( int toto )
{
   // code de la fonction doSomething utilisant toto (sa valeur)
}

// fonction principale main (elle aussi sans paramètre ni valeur de retour)
int main()
{
    // appel à la fonction doSomething en transmettant une valeur entière
    doSomething(10);
}
  • le paramètre toto permet de transmettre une valeur entière à la fonction lorsqu'on l'appelle
  • doSomething(10) signifie que le code de la fonction s'exécutera avec toto valant 10

Déclarer et appeler une fonction

Exercice

Ecrire une fonction pour chaque table de multiplication est pénible. A la place, écrire plutôt une fonction qui affiche la table de multiplication de l'entier fourni en paramètre.


void tableDe( int n )
{
    int i;

    for(i=0; i<=10; i++)
       std::cout <<  n  <<" x " << i << " = " << n*i << std::endl;
}

int main()
{
    int nb ;
    std::cout << "Quelle table voulez vous ?" << std::endl;
    std::cin >> nb ;
    
    tableDe(nb);
}

Fonctionnement d'un paramètre

  • Le paramètre permet à la fonction appelante de transmettre une donnée à la fonction appelée
  • Le type de la donnée transmise doit correspondre au type du paramètre


Un paramètre peut être vu comme une variable spéciale qui sert de zone d'échange entre la fonction appelante et la fonction appelée.

Dans l'exercice précédent, lors de l'appel tableDe(nb), la valeur de la variable nb est recopiée dans le paramètre n. De fait tableDe s'exécute pour la valeur saisie par l'utilisateur.

Une conséquence non négligeable pour la suite, c'est qu'une fonction n'utilise jamais les valeurs qu'on lui transmet, mais des copies de ces valeurs.

Déclarer et appeler une fonction

Exercice

Ecrire une fonction possédant 2 paramètres, un de type String l'autre de type char. La fonction affichera le mot transmis via le premier paramètre mais encadré d'un rectangle dessiné avec le caractère transmis via le second paramètre.


void frame( string word, char c, int longueur ) // longeur du cadre = taille du mot + 2
{
    int i;

    for(i=1; i<=longueur; i++) // haut du cadre
        std::cout << c;
    std::cout << std::endl; // retour à la ligne
    std::cout << c << word << c << std::endl; // le mot encadré de 2 caractères c
    for(i=1; i<=longueur; i++) // bas du cadre
        std::cout << c;
    std::cout << std::endl;

}

void main()
{
    frame("Hello World !", '*', 15);
}

Lorsqu'une fonction présente plusieurs paramètres, l'ordre dans lequel on transmet les données doit être cohérent avec l'ordre dans lequel les paramètres de la fonction sont déclarés.

Ici le paramètre de type string est déclaré avant le paramètre de type char donc on transmettra lors de l'appel d'abord une chaîne suivie d'un caractère et non le contraire.

Déclarer et appeler une fonction

Déclarer une fonction avec valeur de retour

Toute valeur générée par le code d'une fonction à une portée locale. Une valeur locale est toujours détruite à la fin de l'exécution de la fonction. A moins de la "retourner"...


// fonction qui prend en paramètre un entier et retourne un entier
int auCarre( int n )
{
   int res;
   res = n * n;
   return res; // l'entier retourné est le carré du paramètre n
}
  • int avant le nom de la fonction signifie qu'elle retournera une valeur de type entier
  • l'instruction return provoque la fin de l'appel de la fonction et le retour de la valeur qui suit
  • le type de la valeur retournée doit être le même que le type indiqué par le prototype de la fonction

Déclarer et appeler une fonction

Appeler une fonction avec valeur de retour

Une fonction avec valeur de retour ne s'appelle pas comme une fonction sans valeur de retour. Puisque la fonction appelée retourne une valeur, il est nécessaire de récupérer cette valeur dans la fonction appelante. Il faut déclarer une variable de même type que la valeur retournée afin de l'y stocker.


// fonction qui prend en paramètre un entier et retourne un entier
int auCarre( int n )
{
   int res;
   res = n * n;
   return res; // l'entier retourné est le carré du paramètre n
}
// fonction principale main 
void main()
{
    int value;
    value = auCarre(4);
}
  • l'évaluation par la machine de l'appel auCarre(4) donnera 16
  • et donc 16 sera affecté à la variable value
  • ainsi, on a récupéré dans une variable locale de la fonction main une valeur initalement calculée dans une variable locale de la fonction auCarre