Logo FST

Algorithmique

Introduction et concepts élémentaires



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

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

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

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

  3. Les fonctions

Les fonctions

Qu'est ce qu'une fonction ?

  • Contient, équivaut à un algorithme précis!
  • Qui effectue une action précise, calcule quelque chose...
  • Exemple : En TP, on écrit le code de la fonction void setup()

Pourquoi utiliser une fonction ?

  • Décomposer un programme complexe en sous-programmes plus simples
  • Réutiliser le code !
  • Structurer et clarifier le code

Les fonctions

Utiliser une fonction

  • Connaître l'utilité de la fonction (Que fait elle ?)
  • Connaître les entrées et sorties
    • La fonction calcule-t-elle un entier ? un réel ? rien du tout ?
    • La fonction a besoin d'un ou plusieurs paramètres ? de quels types ?
  • Pas besoin de connaître le code exact de la fonction (Comment fait elle ?)
  • Exemple : println("AAAAAAAAAAAAAH")
  • Exemple : void setup()

Un exemple

Fonction f(x) calcule un entier : la valeur au carré de l'entier x

D'un point de vue de l'éxecution,l'expression f(x) est évaluée et remplacée par la valeur calculée


int y = f(3);
			

14 - Quelle est la valeur de y ?

  • 9
  • 3
  • 12
  • Erreur

Un exemple

				
int x = 4;
int y = f(x);
				
			

15 - Quelle est la valeur de y ?

  • 9
  • 4
  • 16
  • Erreur

Un exemple

				
int x = 2;
int y = f;
				
			

16 - Quelle est la valeur de y ?

  • 4
  • 16
  • 0
  • Erreur

Un exemple

				
int y = 2;
y = f(y+3);
				
			

17 - Quelle est la valeur de y ?

  • 25
  • 4
  • 7
  • Erreur

Un exemple

				
int x = 2;
int y = f()+x;
				
			

18 - Quelle est la valeur de y ?

  • 4
  • 6
  • 0
  • Erreur

Un exemple

				
int x = 2;
int y = f(f(x+1));
			
		

19 - Quelle est la valeur de y ?

  • 9
  • 81
  • 25
  • Erreur

Un exemple

					
int y = 2;
y = f(y)+y;
					
				

20 - Quelle est la valeur de y ?

  • 11
  • 6
  • 18
  • Erreur

Les fonctions

Du point de vue de la machine

  • Execution du code contenu contenu dans la fonction
  • Eventuellement, remplacement par la valeur calculée
  • Retour à la suite du code et poursuite de l'execution

Les fonctions

Déclaration d'une fonction


type nom(typeParametre1 nomParametre1, typeParametre2 nomParametre2,...)
{
	// bloc d'instructions
	
}
			

Les fonctions

Création d'une fonction : la fonction f


int f(int x)
{
	int r = x * x;
	return r;
}
			
  • Ce qu'on calcule : le type de donnée calculée
    • Des type classiques : int, float, double, char, boolean, string...
    • Un type void(vide): on ne renvoie rien à la fonction principale
    • ici, un entier

Les fonctions

Création d'une fonction : la fonction f


int f(int x)
{
	int r = x * x;
	return r;
}
			
  • Le nom de la fonction : ici f
  • Identique au choix du nom des variables
  • Le nom doit refléter l'utilité de la fonction
  • Ici, l'exemple à ne pas suivre

Les fonctions

Création d'une fonction : la fonction f


int f(int x)
{
	int r = x * x;
	return r;
}
			
Les paramètres
  • Pour chaque paramètre
    • Son type
    • Son nom à l'intérieur de la fonction
    • Ce nom est valable uniquement à l'intérieur de la fonction
  • Chaque paramètre est séparé par une virgule
  • L'ordre des paramètre est important

Les fonctions

Création d'une fonction : la fonction f


int f(int x)
{
	int r = x * x;
	return r;
}
			
  • Le corps de la fonction
  • Un bloc d'instructions
  • Le mot clé return
    • renvoie la valeur calculée à la fonction appelante

Les fonctions

Exemple d'execution

En processing : on commence par executer la fonction setup()


int f(int x)
{
	int r = x * x;
	return r;
}

void setup()
{
	int r = 3;
	int x = f(r) + r;
	println(x);
}
			

Les fonctions

Exemple d'execution


int f(int x)
{
	int r = x * x;
	return r;
}

void setup()
{
	int r = 3;
	int x = f(r) + r;
	println(x);
}
			

Les fonctions

Exemple d'execution


int f(int x)
{
	int r = x * x;
	return r;
}

void setup()
{
	int r = 3;
	int x = f(r) + r;
	println(x);
}
			

Les fonctions

Exemple d'execution

Evaluation de f(r)


int f(int x)
{
	int r = x * x;
	return r;
}

void setup()
{
	int r = 3;
	int x =  f(r) + r;
	println(x);
}
			

Les fonctions

Exemple d'execution

On évalue r


int f(int x)
{
	int r = x * x;
	return r;
}

void setup()
{
	int r = 3;
	int x = f(3) + r;
	println(x);
}
			

Les fonctions

Exemple d'execution

Execution du bloc d'instructions de f avec x=3


int f(int x = 3)
{
	int r = x * x;
	return r;
}

void setup()
{
	int r = 3;
	int x = f(3) + r;
	println(x);
}
			

Les fonctions

Exemple d'execution


int f(int x)
{
	int r = 3 * 3;
	return r;
}

void setup()
{
	int r = 3;
	int x = f(3) + r;
	println(x);
}
			

Les fonctions

Exemple d'execution

On retourne la valeur 9 à la fonction appelante


int f(int x)
{
	int r = x * x;
	return 9;
}

void setup()
{
	int r = 3;
	int x = f(3) + r;
	println(x);
}
			

Les fonctions

Exemple d'execution

On reprends l'execution du code de la fonction setup()


int f(int x)
{
	int r = x * x;
	return r;
}

void setup()
{
	int r = 3;
	int x = 9 + r;
	println(x);
}
			

Les fonctions

Exemple d'execution

On évalue la variable r de la fonction setup()


int f(int x)
{
	int r = x * x;
	return r;
}

void setup()
{
	int r = 3;
	int x = 9 + 3;
	println(x);
}
			

Plusieurs paramètres

				
float monCalcul(float x,float y)
{
	float z = x/y;
	return z;
}
void setup()
{
	float x = 6;
	float y = 3;
	float z = monCalcul(x,y)+2.0;
}
				
			

21 - Quelle est la valeur de z ?

  • 2.0
  • 4.0
  • 2.5
  • Erreur

Plusieurs paramètres

				
float monCalcul(float x,float y)
{
	float z = x/y;
	return z;
}
void setup()
{
	float x = 6;
	float y = 3;
	float z = monCalcul(y,x)+2.0;
}
				
			

22 - Quelle est la valeur de z ?

  • 2.0
  • 4.0
  • 2.5
  • Erreur

Plusieurs paramètres

				
void afficheMonCalcul(float x,float y,String message)
{
	float z = x/y;
	print(message + z);
	
}
void setup()
{
	float x = 6;
	float y = 3;
	afficheMonCalcul("Le résultat est : ",x,2.0);
}
				
			

23 - Que voit on à l'écran ?

  • Le résultat est : 3.0
  • Le résultat est : 6.0
  • Le résultat est : 0
  • Erreur

Plusieurs paramètres

				
void afficheMonCalcul(float x,float y,String message)
{
	float z = x/y;
	print(message + z);
	
}
void setup()
{
	float x = 6;
	float y = 3;
	float z = afficheMonCalcul(x,2.0,"Le résultat est : ");
	print(". z = " + z);
}
				
			

24 - Que voit on à l'écran ?

  • Le résultat est : 3.0. z = 3.0
  • Le résultat est : 3.0.z=3.0
  • . z = 3.0
  • Erreur

Les fonctions

A retenir

  • Vérifier la cohérence des types
    • Le type de retour ET le type des paramètres
    • Différencier le type de retour et les paramètres
  • De quoi a besoin la fonction ?
  • Que retourne-t-elle ?
  • Attention à l'ordre des paramètres
  1. Bases de l'Algorithmique
    • Introduction
    • Types, variables et opérateurs
    • Les fonctions
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

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 if.... 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
println("Saisir les valeurs de a et de b ");
a = askInteger() ; 
b = askInteger() ; 
if ( b != 0 )
{
	division = a / b;
	println("La division de a par b est "+ division );
}

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
println("Saisir les valeurs de a et de b ");
a = askInteger() ; 
b = askInteger() ; 
if ( b != 0 )
{
    division = a / b;
    println("La division de " + a + " par " + b + " est égale à "  + division );
}
else
{
     println("La division par zéro est interdite");
}
 

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'est 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
jour = askInteger("Saisir un nombre entier entre 1 et 7");
if ( jour == 1 ) 
   println("lundi");
else
{
    if ( jour==2 )
        println("mardi");
    else
    {
        if ( jour==3 )
            println("mercredi");
        else
        {
            if ( jour==4 )
               println("jeudi");
            else
            {
                if ( jour==5 )
                    println("vendredi";)
                else
                {
                    if ( jour==6 )
                        println("samedi");
                    else
                        println("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
jour = askInteger("Saisir un nombre entier entre 1 et 7") ;
if ( jour == 1 ) 
println("lundi");
else
{
if ( jour==2 )
println("mardi");
else
{
if ( jour==3 )
println("mercredi");
else
{
if ( jour==4 )
println("jeudi");
else
{
if ( jour==5 )
println("vendredi");
else
{
if ( jour==6 )
println("samedi");
else
println("dimanche");
}
}
}
}	
}

Par exemple

								
void setup()
{
    int ecrit1 = 12;
    int ecrit2 = 15;
    int tp = 8;
    if (0.25*ecrit1 + 0.25*tp + 0.5*ecrit2 >= 10)
        println("vous avez validé info1");
}
					
				

25 - Que voit on à l'écran ?

  • vous avez validé info1
  • rien
  • Erreur

Par exemple

                        
float calculDeMoyenne(int ecrit1,int ecrit2,int tp)
{
     return(0.25*ecrit1 + 0.25*tp + 0.5*ecrit2);
}					
void setup()
{
    if (calculDeMoyenne(4,5,6) >= 10);
         println("vous avez validé info1");
}
                        
                    

26 - Que voit on à l'écran ?

  • vous avez validé info1
  • rien
  • Erreur

Par exemple

						
float calculDeMoyenne(int ecrit1,int ecrit2,int tp)
{
    return(0.25*ecrit1 + 0.25*tp + 0.5*ecrit2);
}					
void setup()
{
    float z = calculDeMoyenne(12,15,8);
    if z > 10
        println("vous avez validé info1");
    else
        println("vous n'avez pas validé");
}
						
					

27 - Que voit on à l'écran ?

  • vous avez validé info1
  • vous n'avez pas validé
  • rien
  • Erreur

Instructions conditionnelles
imbriquées

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


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

Par exemple

							
float calculDeMoyenne(int ecrit1,int ecrit2,int tp)
{
	return(0.25*ecrit1 + 0.25*tp + 0.5*ecrit2);
}					
void setup()
{
	float z = calculDeMoyenne(4,4,5);
	if (z > 10)
	    println("vous avez validé info1");
	else if (z <= 8 )
		println("vous avez moins de 8");
	else
	    println("vous n'avez pas validé");
}
							
						

28 - Que voit on à l'écran ?

  • vous avez validé info1
  • vous n'avez pas validé
  • vous avez moins de 8
  • Erreur

Par exemple

							
float calculDeMoyenne(int ecrit1,int ecrit2,int tp)
{
	return(0.25*ecrit1 + 0.25*tp + 0.5*ecrit2);
}					
void setup()
{
	float z = calculDeMoyenne(18,18,15);
	if (z > 10)
	    println("vous avez validé info1");
	else if (z >= 12 )
		println("vous avez plus de 12");
	else
	    println("vous n'avez pas validé");
}
							
						

29 - Que voit on à l'écran ?

  • vous avez validé info1
  • vous n'avez pas validé
  • vous avez plus de 12
  • Erreur

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:
   case valeur3 : 
      instruction2;
      instruction2bis;
      break;
   .
   .
   .
   default:
      instructionDefaut;
      break;	
}


if (variable == valeur1)
   instruction1;
else if (variable == valeur2 || variable == valeur3)  
{
    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
jour = askInteger("Saisir un nombre entier entre 1 et 7");
switch (jour)
{
case 1:
  println("Lundi");
  break;
case 2:
  println("Mardi");
  break;
case 3:
  println("Mercredi");
  break;
case 4:
  println("Jeudi");
  break;
case 5:
  println("Vendredi");
  break;
case 6:
  println("Samedi");
  break;
case 7:
  println("Dimanche");
  break;
default:
  println("Erreur");
  break;

}

Instructions conditionnelles
à choix multiple

Précisions sur l'instruction switch

  • Ne fonctionne qu'avec des variables de type int, char et String
  • En Processing, le système, après avoir reconnu une valeur, continue à 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 conditionnelles

A retenir

  • Une expression booléenne entre parenthèses
  • L'évaluation n'est pas une instruction, donc pas de ;
  • Evaluation soit du bloc si, soit du bloc sinon
  1. Bases de l'Algorithmique
    • Introduction
    • Types, variables et opérateurs
    • Les fonctions
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

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++ ) 
	{ 
		println("Bonjour");
	}
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; 
	
	nb = askInteger("Saisir le nombre de bonjour ") ;
	
	for ( i=1; i<=nb; i++ ) 
	   println("Bonjour");
	

	nb = askInteger("Saisir le nombre de bonjour ") ;
	for ( i=0; i<nb; i++ ) 
	   println("Bonjour");
	

Notes :

  • les accolades délimitant le bloc sont optionnelles s'il ne contient qu'une instruction
  • ces deux solutions sont équivalentes, le nombre de tours 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; 
	n = askInteger("Saisir un entier positif ");
	for ( i=1; i<=n; i++ ) 
		print(i + " " );
	

Note :

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

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++)
		{
			println("5 x " + i + " = "+ 5*i );
		}
	}
	void tableDe7()
	{
		int i;    
		for(i=0; i<=10; i++)
		 {
			println("7 x " + i + " = "+ 7*i );
		 }
	}
		
	void setup()
	{
		tableDe5();
		tableDe7();
	}
		

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++)
		  println(n  +" x " + i + " = " + n*i );
	}
		
	void setup()
	{
		int nb = askInteger("Quelle table voulez vous ?") ;    
		tableDe(nb);
	}
		

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 Processing !

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' )
	{ 
		reponse = askChar("Avez-vous compris ?") ;
	} 

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
	{ 
	  reponse = askChar("Avez-vous compris ?") ;
	}
	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 random(0.0,10.0) qui génère aléatoirement (ou presque) un nombre compris entre 0 (inclus) et 10(exclu).
Par exemple float nb_alea = random(0.0,1.0); initalisera nb_alea avec une valeur entre 0 et 1.0.
Aussi int adeviner = int(random(0,100)); 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;
	int adeviner = int(random(0,100));
	
	do
	{ 
		proposition = askInteger("Proposer un nombre entre 0 et 99 :");
		
		if ( proposition < adeviner )
			println("Trop petit !");
		else if ( proposition > adeviner )
			println("Trop grand !");
		else
			println("Félicitations ! C'était bien " + adeviner);
	}
	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.


	
	for(int i=1; i<= 10; i++)
	{
	   println("Table de multiplication de " + i );
		for(int j=1; j<=10; j++)
		{
			println(i+" x "+j+" = "+i*j);
		}
	}
	

Des exemples en tout sens


	int x = 5;
	int i = 0;
	for(i = 3; i < 6;i++)
	{
		x += 1;
	}
	

30 - Quelle est la valeur de x à la fin de la boucle ?

  • 5
  • 8
  • 10
  • 11
  • La boucle ne s'arrete jamais
  • Erreur

Des exemples en tout sens


	int x = 1;
	for(int i = 1; i <= 5;i++)
	{
		x += 1;
		i+=1;
	}
					

31 - Quelle est la valeur de x à la fin de la boucle ?

  • 2
  • 4
  • 5
  • La boucle ne s'arrete jamais
  • Erreur

Des exemples en tout sens


	int x = 1;
	for(int i = 1; i <= 5;i++);
	{
		x += 1;
	}
					

32 - Quelle est la valeur de x à la fin de la boucle ?

  • 2
  • 7
  • 8
  • La boucle ne s'arrete jamais
  • Erreur

Des exemples en tout sens


	int x = 0;
	char reponse;
	while (reponse == 'o' || reponse == "O")
	{
		println("Hello");
		x = x + 1;
		reponse = askChar("Voulez vous continuer ? (O/N)");
	}
									

33 - Que fait cet algorithme ?

  • Il affiche "Hello" tant que l'utilisateur appuie sur o
  • Il ne fait rien
  • Il contient une erreur de syntaxe
  • Il boucle à l'infini

Des exemples en tout sens


	int x = 0;
	int i = 1;
	do
	{
		x = x + 1;
	}
	while( i<10 );
	

34 - Quelle est la valeur de x à la fin de la boucle ?

  • 1
  • 10
  • 11
  • La boucle ne s'arrete jamais
  • Erreur

Des exemples en tout sens


	int x = 0;
	int i = 1;
	while (i < 10 && x < 4 )
	{
		 x = x + 1;
		 i += 1;
	}
			

35 - Quelle est la valeur de x à la fin de la boucle ?

  • 0
  • 4
  • 10
  • 11
  • La boucle ne s'arrete jamais
  • Erreur

Des exemples en tout sens


	int x = 0;
	int i = 1;
	while (i < 10 || x < 4 )
	{
		 x = x + 1;
		 i += 1;
	}
			

36 - Quelle est la valeur de x à la fin de la boucle ?

  • 0
  • 4
  • 10
  • 11
  • La boucle ne s'arrete jamais
  • Erreur

Des exemples en tout sens


	int x = 0;
	int i = 1;
	while (i < 10 && x > 0)
	{
		 x = x + 1;
		 i += 1;
	}
			

37 - Quelle est la valeur de x à la fin de la boucle ?

  • 0
  • 1
  • 10
  • 11
  • La boucle ne s'arrete jamais
  • Erreur

Erreurs :
Les grands classiques

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

  • le risque avec une boucle, c'est de ne jamais en sortir
  • pour en savoir un peu plus, clic

A retenir

Boucles

  • La boucle for n'est pas une instruction en soit, donc pas de ;
  • Attention : les variables de la conditions doivent évoluer
  1. Bases de l'Algorithmique
    • Introduction
    • Types, variables et opérateurs
    • Les fonctions
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

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'une variable de type tableau

// déclaration d'une variable de type tableau d'entiers 
int[] monTableaudEntiers ;

// déclaration d'une variable de type tableau de caractères 
char[] monTableaudeChar;

// déclaration d'une variable de type tableau de booléens
boolean[] monTableaudeBool ;

// déclaration d'une variable de typetableau de  chaînes
String[] malistedeChaine ;
  • De manière générale, la syntaxe est : nom_du_type[] nom_du_tableau ;
  • Attention, le tableau n'est pas encore créé !
  • On a simplement créé une variable qui fera référence à un tableau un jour

Tableaux unidimensionels

Création d'un tableau

// Création d'un tableau d'entiers de taille 8
monTableaudEntiers = new int[8];

// Création d'un tableau de caractères de taille 1024
monTableaudeChar = new char[1024] ;

// Création d'un tableau de booléens de taille 256
monTableaudeBool = new boolean[256] ;

// Création d'un tableau de 25 chaînes
malistedeChaine = new String[25] ;
  • L'opérateur new permet la création du tableau
  • 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 à taille lui permet de réserver taille 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

Tableaux unidimensionels

Déclaration et création d'un tableau

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

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

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

// déclaration d'un tableau de 25 chaînes
String[] chaine_tab = new String[25] ;
  • De manière générale, la syntaxe est : nom_du_type[] nom_du_tableau = new nom_du_type[taille];
  • On peut bien entendu déclarer le tableau et créer la variable en une seul fois

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 = new int[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)
  • En informatique, pour les tableaux , on commence par l'indice 0

Tableaux unidimensionels

Exercice

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


int i;
int[] tab = new int[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 = new int[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

Un premier exemple


int[] tx = new int[10];
for (int i = 0;i < 10;i++)
    tx[i] = i+1;      
tx[0] = tx[4] + tx[9];                  

38 - Que contient la première case du tableau ?

  • 0
  • 1
  • 13
  • 15
  • Erreur

Un deuxième exemple


int[] tx = new int[10];
int a = 5;
for (int i = 0;i < 10;i++)
    tx[i] = i;  
a = a * tx[10];    
                
            

39 - Que contient la variable a?

  • 0
  • 5
  • 45
  • 50
  • Erreur

Un troisième exemple


int[] tx = new int[11];
int a = 5;
for (int i = 0;i < 10;i++)
    tx[i] = i;  
a = a * tx[10];    
                
            

40 - Que contient la variable a?

  • 0
  • 5
  • 45
  • 50
  • Aucune idée
  • Erreur

Tableaux unidimensionels

Exercice

Ecrire un algorithme pour saisir 28 notes dans un tableau.



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

println("Saisir les " + nb_notes + " notes");
// saisie des notes dans le tableau
for(i=0; i<nb_notes; i++)
    notes[i]=askDouble() ;

  • On utilise ici la variable 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


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

println("Saisir les " + nb_notes + " notes");
// saisie des notes dans le tableau
for(i=0; i<nb_notes; i++)
    notes[i] = askFloat() ;

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

println(" La moyenne est : " + avg/(float)nb_notes);
  • 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


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

nb_notes = askInteger("Combien de notre à saisir ?");
notes = new float[ nb_notes ];

println("Saisir les " + nb_notes + " notes");
// saisie des notes dans le tableau
for(i=0; i<nb_notes; i++)
   notes[i] = askFloat() ;

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

println(" La moyenne est : " + avg/(float)nb_notes);

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. Bases de l'Algorithmique
    • Introduction
    • Types, variables et opérateurs
    • Les fonctions
    • Instructions structurées

  2. Les tableaux
    • Tableaux unidimensionnels
    • Tableaux bidimensionnels

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 = new int[10][10];

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

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

// déclaration d'un tableau 2D de chaînes
String[][] chaine_tab = new String[10][10];
  • De manière générale, la syntaxe est : nom_du_type[][] nom_du_tableau = new nom_du_type[ligne][colonne];

Tableaux bidimensionels

Notez au passage

// type entier
int value;

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

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

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

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

// 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 = new int[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 = new double[28][12];

for( l=0; l<28; l++)
{
    for( c=0; c<12; c++)
    {
    	notes[l][c] = askDouble("Note de l'étudiant" + l + " pour le module " + c );
    }
}

A retenir

Tableaux

  • Initialiser la variable ne crée pas le tableaux
  • Attention aux dépassement de bornes
  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 émulsion 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