Algorithmique

(Partie 2)
Sources
[Link]

https://
[Link]/courses/concevez-votre-site-web-avec-php-et-mys
"
ql
Organiser son environnement
• Pour exécuter un programme PHP, on a besoin d’installer sur sa machine :
• Un serveur Web
• Un interpréteur PHP
• (Un serveur de base de données : pas utile pour l’instant, mais pourra servir par la
suite et souvent livré avec le serveur Web)
• Il est nécessaire d’utiliser un serveur Web et un interpréteur PHP
• Voir le cours Openclassrrom N°2 « préparer son environnement de travail » https://
[Link]/courses/concevez-votre-site-web-avec-php-et-mysql/prepare
r-son-environnement-de-travail

• Mais pour s ’exercer simplement sur des programmes simples, on peut

utiliser
[Link]
Contenu
• Sous-programmes
• Structures, enregistrement, table
• Fichiers
Les sous-programmes
Les sous-programmes
• Algorithmique :

• Diviser pour régner

• Décomposer un problème en sous problème

• Mettre chaque solution à un sous problème dans un morceau de programme,

un sous-programme
• Composer les morceaux

• On distingue les fonctions ou les procédures

Une fonction est un
(sous-)programme
• Qui porte un nom
• A des paramètres en entrées
• Retourne une valeur
 Définition d’une fonction en langage
algorithmique
Fonction nom_de_fonction (paramètre1 : type 1, … Fonction somme (a : réél, b : réél) : réel
paramètre i : type i, …) : type
Var c : réél
Début
Var
ca+b
/* Variables locales */
Début Retourne c
/*bloc d’instruction*/ FinFonc
Retourne variable
FinFonc a et b sont les paramètres formels de la fonction
somme.
Les paramètres formels d’une fonction définissent La variable c est une variable locale à la fonction
les types des valeurs à entrer pour calculer la ‘’somme’’, elle n’est pas connue (vue) à l’extérieur
valeur retournée (Retourne ) de type type. de cette fonction.
Les variables déclarées dans une fonction sont des
variables locales à la fonction.
 Définition d’une fonction en PHP
Fonction nom_de_fonction (paramètre1 : type 1, … <?php
paramètre i : type i, …) : type

Var function nom_de_fonction

/* Variables locales */ ($parametre_1, $parametre_2, ..., $
Début parametre_n)
/*bloc d’instruction*/ {
Retourne variable echo "Exemple de fonction.\n";
FinFonc return $return_value;
}
Les paramètres formels d’une fonction définissent
les types des valeurs à entrer pour calculer la
valeur retournée (Retourne ) de type type. ?>
Les variables déclarées dans une fonction sont des
variables locales à la fonction.
 Définition d’une fonction en PHP
Fonction somme (a : réél, b : réél) : réel <?php
Var c : réél
\\définition :
Début
function addition ($a, $b)
ca+b
{
Retourne c $c=$a+$b;
FinFonc return $c;
}
a et b sont les paramètres formels de la
fonction somme. \\appel :
$d = addition (2,10);
La variable c est une variable locale à la ?>
fonction ‘’somme’’, elle n’est pas connue
(vue) à l’extérieur de cette fonction.
Utilisation d’une fonction
PROGRAMME Toto • a et b dans la définition de la fonction
‘’somme’’ sont les paramètres formel
VAR
• x,y dans le programme Toto sont les
x,y,z : réels paramètres effectifs (ou réels)
DEBUT • Les paramètres formels et effectifs peuvent
z  somme(x,y) porter le même nom, mais pas
nécessairement
FIN
• A l’appel de la fonction (z  somme(x,y)), a
prend la valeur de x, b prend la valeur de y
• Au retour, la valeur retournée par la fonction
est affectée à la variable z
Une procédure est un
(sous-)programme
• Qui porte un nom
• A des paramètres en entrée (E)
• A des paramètres en sorties (S)
• A des paramètres en entrées sorties (ES)
 Définition d’une procédure en
langage algorithmique
Procédure nom_de_procédure (mode paramètre1 Procédure somme (E a : réél, E b : réél, S c :
: type 1, … , mode paramètre i : type i, …) réel)
Var
Début
/* Variables locales */
Début ca+b
/*bloc d’instruction*/ Finproc
FinProc
• a, b, c dans la définition de la procédure
mode: somme sont les paramètres formel
Entrée, Sortie, EntréeSortie
(les paramètres en sortie et en entrée/sortie sont
déclarées dans le programme appelant)
Utilisation d’une procédure
PROGRAMME Toto • a, b, c dans la définition de la procédure
‘’somme’’ sont les paramètres formel
VAR • x, y, z dans le programme Toto sont les
x,y,z : réels paramètres effectifs (ou réels)
DEBUT • A l’appel de la procédure somme(x, y,
z), a prend la valeur de x, b prend la
somme(x,y,z) valeur de y
FIN • Une procédure ne retourne pas
explicitement de valeur, mais comme c
est déclaré en sortie, c est modifié.
• Une procédure ne peut pas être
affectée à une variable
Mode de passage de paramètres
• Par valeur : • Par référence :
• La valeurs du paramètre effectif • La référence du paramètre effectif
est copiée dans le paramètre est copiée dans le paramètre
formel formel
ÞLa modification du paramètre ÞLa modification du paramètre
formel n’entraîne pas la formel entraîne la modification de
modification du paramètres la variable référencée par ce
effectif paramètre
• C’est le mode de passage des • C’est le mode de passage des
paramètres en entrée paramètres en sortie et en
entrée/sortie
En règle générale
• En théorie :
• Les paramètres d’une fonction sont passés par valeur
• Les paramètres en entrée d’une procédure sont passés par valeur
• Les paramètres en sortie et en entrée/sortie sont passés par référence
• En pratique :
• En PHP, tout est possible, mais pas conseillé
La visibilité des variables
• On peut déclarer des variables dans les programmes appelant et dans
les sous-programmes appelés ! Comment cela se passe-t-il si elle ont
le même nom ?
• Par défaut, une variable définie dans un sous-programme n’est visible
que dans ce sous programme (portée locale), sauf si elle est
explicitement déclarée comme globale.
• Deux variables locales de même nom n’ont pas de lien entre elles
Les variables globales
VAR GLOBALES
c: réél
Procédure somme (E a: réel, E b : réel)
VAR
DEBUT
ca+b
FIN
PROGRAMME Essai
VAR
x, y : réel
DEBUT
Lire(x,y)
Somme (x,y)
Ecrire c
FIN
 En PHP <?php
$myPrice="100" ;
print ("1_Prix hors taxe : $myPrice <br/>") ;
$myPrice="100" ;
• Function pour’’Fonction’’ et add_tva_val($myPrice);
‘’Procédure’’ print ("2_Après passage par valeur : $myPrice<br/>") ;
$myPrice="100" ;
• Passage par valeur par défaut : add_tva_ref($myPrice);
print ("3_Après passage par référence : $myPrice<br/>");
$var
• Passage par référence : &$var
function add_tva_val($myPrice)
{
$myPrice = .19*$myPrice + $myPrice ;
}

function add_tva_ref(&$myPrice)
{
$myPrice = .19*$myPrice + $myPrice ;
}

?>
 En PHP
<?php
$myPrice="100" ;
• Function pour’’Fonction’’ et
print ("1_Prix hors taxe : $myPrice <br/>") ; ‘’Procédure’’
$myPrice="100" ;
• Passage par valeur par défaut : $var
add_tva_val($myPrice); • Passage par référence : &$var
print ("2_Après passage par valeur : $myPrice<br/>") ;

$myPrice="100" ;
add_tva_ref($myPrice);
print ("3_Après passage par référence : $myPrice<br/>");
Résultat de l’exécution :
function add_tva_val($myPrice) 1_Prix hors taxe : 100
{
$myPrice = .19*$myPrice + $myPrice ; 2_Après passage par valeur :
} 100
function add_tva_ref(&$myPrice)
{ 3_Après passage par
}
$myPrice = .19*$myPrice + $myPrice ;
référence : 119
?>
 Fonctions prédéfinies en PHP
• Exemple : chaînes de caractères • Des centaines:
• round() : arrondi les réels
• count() : nombre d’éléments dans un
[Link]
tableau fr/[Link]
• strlen(): retourne la longueur d’une
chaîne
• strpos() : cherche la position de la
première occurrence de la chaîne en
paramètre
• substr(): découpe une portion de chaîne
• isempty(): teste si une variable a une
valeur
• …
Les structures
Un exemple de type construit à partir des types de base.
 Les structures - Exemple
Type
Structure Etudiant
no-etudiant : chaîne Structure des enregistrements
nom: chaîne
année_inscription : chaîne no-etudiant nom annee_inscription adresse
adresse : chaîne
FinStruct etudiant 1 12 Alfred 2017 Cite Haute Malgrange

n enregistrements etudiant 2
de structure ‘’Etudiant’’
…

etudiant n
Les structures – Définition
Type Type
Structure nom-type Structure Etudiant
champ1 : type no-etudiant : chaîne
champ2 : type nom: chaîne
champ3 : type année_inscription : chaîne
champ4 : type adresse : chaîne
FinStruct FinStruct
Les enregistrements : instances de
structures
• Notion d’enregistrement Exemple:
Un enregistrement est une variable etudiant1, etudiant2: Etudiant
d’un type structuré de donnée.

VAR
nom-enregistrement : nom de type
 Les structures - Utilisation
Type • Accéder à un champ d’un
Structure nom-type enregistrement
• nom_enregistrement.nom_de_champ
champ1 : type
champ2 : type • variable1 : nom-type
champ3 : type variable2  variable1.champ2
champ4 : type
• etudiant1 : type_etudiant
FinStruct variable4  [Link]
Les enregistrements dans les
structures
• Une structure peut avoir un Type
champ de type structure Structure nom-type
champ11 : type
champ22 : type
Type champ33 : type
Structure nom-type-2 champ44 : type
champ1 : type FinStruct

champ2 : nom-type
Var exemple : nom-type-2
champ3 : type Variable5  exemple.champ2.champ22
FinStruct
 Un nouveau type construit :
les tables (tableau
d’enregistrements)
• Une table est un tableau • VAR
d’enregistrements var etudiants : tableau[1..10] de type-etudiant

• Nom de l’étudiant i:
Etudiants[i].nom
Structures et tables en PHP
• On ne dispose pas de type • En réalité, on entrebaille la porte
« structure » de la programmation objet.
• On va s’appuyer sur la notion de • Aussi, n’entrez pas dans le détail
classe d’objets de ces notations, c’est inutile et
• Avec les notations ‘’new’’ il vous manque une partie du
contexte : exemple du mot clé
et ‘’ ->’’ public
Création des types de structure : Utilisation des enregistrements structurés :

<?php $article=new tarticle;

class tfabricant {
$article->fab=new tfabricant;
public $ref;
public $nom;
public $adresse; $article->ref="Art001_01";
public $tel; $article->fab->ref="Fabl234";
}
class tarticle { echo $article->ref;
public $ref; echo "<br />";
public $libelle;
echo $article->fab->ref;
public $prix;
public $fab;
} ?>
 $article[0]=new tarticle;
Une table d’article $article[1]=new tarticle;
$article[0]->fab=new tfabricant;
<?php $article[1]->fab=new tfabricant;

class tfabricant { $article[0]->ref="Art001_01";

public $ref; $article[1]->ref="Art002_02";
public $nom; $article[0]->fab->ref="Fabl234";
public $adresse; $article[1]->fab->ref="Fab4321";
public $tel;
} echo $article[0]->ref;
echo "<br />";
class tarticle { echo $article[0]->fab->ref;
public $ref; echo "<br />";
public $libelle;
echo $article[1]->ref;
public $prix;
echo "<br />";
public $fab;
echo $article[1]->fab->ref;
}
echo "<br />";
?>
 Une table d’article for($i=0;$i<3;$i++) {
$article[$i]=new tarticle;
$article[$i]->fab=new tfabricant;
<?php }
$article[0]->ref="Art001_01";
class tfabricant { $article[0]->fab->ref="Fabl234";
public $ref; $article[1]->ref="Art002_02";
public $nom; $article[1]->fab->ref="Fab4321";
public $adresse;
public $tel; echo $article[0]->ref;
} echo "<br />";
echo $article[0]->fab->ref;
class tarticle { echo "<br />";
public $ref;
echo $article[1]->ref;
public $libelle;
echo "<br />";
public $prix;
echo $article[1]->fab->ref;
public $fab;
}
?>
Les fichiers
Objectif
• Assurer la persistance des données :
• Permettre la sauvegarde et la récupération des données entre deux sessions
de travail
• Les données sont sauvegardées sur des supports particuliers : disque dur (ex
C:), clé USB …
Types de fichiers
• Fichiers texte : lignes de texte successives
• Fichiers binaires : suite de ‘’0’’ et ‘’1’’ qui ne correspondent pas (sauf
accident) à du texte.

• Interprétation interne des fichiers : liée aux programmes qui les

utilisent
• Formats : HTML, JPEG, .doc, .pdf, MP3 …
Accès aux fichiers
• Séquentiel
• Direct
• Séquentiel indexé
Principales fonctions
• Ouvrir un fichier (en lecture, en écriture)
• Traiter un fichier : lire et écrire des lignes, des enregistrements, des
caractères …
• Fermer un fichier
 Forme générale d’un programme de
traitement d’un fichier
Programme TRAITER-FICHIER Début
Var //On récupère la référence au fichier
fic: fichier fic  ouvrir(nom_de_fichier)
nom_de_fichier : chaîne Tantque non EOF (fic) faire
ligne : chaîne //on lit la ligne en cours du fichier
//dans la variable ‘’ligne’’
• ‘’fic’’ est la référence du fichier dans le lire(fic, ligne)
programme //traiter la ligne
• ‘’nom de fichier’’ est le nom du fichier sur disque traiter(ligne)
//passer à la ligne suivante
• EOF fonction qui teste la fin d’un fichier Findetantque
(End Of File) Fermer(fic)
Fin
Exemple PHP avec ‘’fgets’’
<?php
// on déclare le nom du fichier à ouvrir
$fichier = ‘[Link]';
//ouverture du fichier en lecture seule
$fp = fopen($fichier,'r');
//feof indiquera la fin du fichier
//le fichier est parcouru jusqu'à la fin
while(!feof($fp))
{
//lecture du fichier, stockage dans $ligne
$ligne = fgets($fp);
//affiche la ligne à l'écran, n'oubliez pas
print $ligne.'<br/>';
}
fclose($fp); //pensez à refermer à la fin du script
?>
Fichiers en PHP
• Ouverture :
int fopen(string filename, string mode)
Mode:
Mode: Les associations d'ouvertures liées à fopen()

ouvre le fichier pour écriture, et détruit les données si le

'w' fichier en contient
'w+' comme ci dessus mais crée le fichier si celui ci n'éxiste pas
ouvre le fichier pour ajouter de nouvelles données en fin
'a' de fichier
'a+' comme ci-dessus mais crée le fichier si celui n'existe pas
'r' ouvre le fichier en lecture seulement
Fichiers en PHP
• Lecture • Ecriture
string fgets(int fp, [int length]) int fwrite(int fp, string chaîne [,
retourne la ligne courante du fichier int length])
Si lenght est précisé, lit lenght écrit le contenu de chaîne dans le fichier
caractères ou jusqu’à la fin de ligne fp; si lenght (optionnel) est précisé, au
plus lenght octets seront écrits

• Fermeture
Synonyme : fputs
bool close(string filename)
Autres fonctions
• Autres :
array file(string filename)
lit un fichier et le range dans un tableau
ligne par ligne
string fread(int fp, int length)
idem fgets mais ignore les fins de ligne
int filesize(string filename)
Exemple PHP avec ‘’fgets’’
<?php
// on déclare le nom du fichier à ouvrir
$fichier = ‘[Link]';
//ouverture du fichier en lecture seule
$fp = fopen($fichier,'r');
//feof indiquera la fin du fichier
//le fichier est parcouru jusqu'à la fin
while(!feof($fp))
{
//lecture du fichier, stockage dans $ligne
$ligne = fgets($fp);
//affiche la ligne à l'écran, n'oubliez pas
print $ligne.'<br/>';
}
fclose($fp); //pensez à refermer à la fin du script
?>
Exemple ‘’file’’
<?php
$myFileArray = file(‘[Link]');
for ($index=0;$index<count($myFileArray);$index++)
{
print ($myFileArray[$index]."<br/>");
}
?>
Les fichiers d’enregistrements en
PHP
• Délimiter les champs avec un caractère spécial
• Mettre un enregistrement par ligne

12:Alfred:2017:CiteHauteMalgrange

• Lecture : lire une ligne et récupérer les champs grâce aux

délimiteurs (voir fonction ‘’explode’’)
• Ecriture : coller les champs en insérant le délimiteur entre eux
(voir fonction ‘’implode’’)
Sujet de TP (2017 – 2018)
Tri d’un fichier de données selon un champ de la structure des enregistrements.

On désire réaliser un programme qui prend en entrée une liste d’étudiants initialement non triée et qui retourne la
même liste d’étudiants mais triée par numéro d’étudiant croissant.
La liste d’étudiants est stockée dans un fichier texte dont chaque enregistrement contient un étudiant avec la
structure suivante : no-étudiant, nom, prénom et inscription. Le fichier tient entièrement en mémoire.
On propose d’organiser l’étude en trois temps de la façon suivante :
- Ecrire un programme en PHP qui trie un tableau d’entiers en mémoire
- Adapter le programme pour trier des entiers stockés dans un fichier
- Adapter le programme pour trier des étudiants (structures composées des champs no-étudiant, nom, prénom et
inscription) stockés dans un fichier.
- A Chaque étape, donner :
- L’algorithme utilisé en langage algorithmique
- Le programme correspondant
(On pourra utiliser les fonctions implode et explode pour gérer les structures.)
Une fois le programme trié, on veut :
- pouvoir insérer dans le fichier un nouvel étudiant
- pouvoir supprimer un étudiant de numéro donné
TP 2018-2019
FIN
Algorithmique sur les
tableaux
Algorithmique sur les tableaux
• Fortement liée à la notion de boucle
• Recherche d’un élément
• Plus petit/ plus grand élément
• Moyenne
• Tris
• …
Recherche d’un élément
PROGRAMME Recherche DEBUT
i 1
VAR trouve  faux
nombres : tableau [1..10] Tant que i<=10 et trouve = faux Faire
d’entiers Si nombre[i] = valeur_cherchée Alors trouve  vrai
Fsi
valeur_cherchée : entier ii+1
trouve: booléen FinTantQue
Si Trouve alors Afficher « Trouvé en position » i -1
sinon Afficher « Pas trouvé »
FinSi
FIN
Recherche d’un élément en PHP
<?php
$nombres = array(3,7,59,45,12,999, 45,5,88,1);
$trouve=false;
$valeur-recherchee=5;
$i = 0;
while(($i<9) && (! $trouve)
{
If ($nombres[$i] == $valeur-recherchee) trouve = true;
$i = $i + 1;
}
If ($trouve) echo ‘’trouvé en position’’.($i-1). ’’\n ’’;
?>
Foreach <?php
$a = array (1, 2, 3, 17);

<?php $i = 0;
$a = array (1, 2, 3, 17); foreach($a as $v){
foreach ($a as $v){ print "\$a[$i] => $v.\n";
print "Valeur courante de \$a: $v.\n"; $i = $i + 1;}
} ?>
?>
Valeur courante de $a: 1. $a[0] => 1.
Valeur courante de $a: 2. $a[1] => 2.
Valeur courante de $a: 3. $a[2] => 3.
Valeur courante de $a: 17. $a[3] => 17.
Foreach
<?php
$a = array ("un" => 1,"deux" => 2,"trois"
=> 3,"dix-sept" => 17 );
foreach($a as $k => $v)
{
print "\$a[$k] => $v.\n";
}
?>
$a[un] => 1.
$a[deux] => 2.
$a[trois] => 3.
$a[dix-sept] => 17.
La récursivité
• Une fonction (procédure) récursive est une fonction (procédure) qui
s’appelle elle-même, directement ou par l’intermédiaire d’une autre
fonction ou procédure.
• Un problème difficile de la programmation récursive est de trouver
la(les) bonne(s) condition(s) d’arrêt.
 • Croisée
La récursivité Procedure recursive1 ()
DEBUT
• Simple …
Recursive2 ()
Procedure recursive ()
…
DEBUT FIN
…
recursive () Procedure recursive2 ()
DEBUT
…
…
FIN recursive1 ()
…
FIN
Exemple : calcul d’une factorielle
• n! = n*n-1*n-2*…*2*1

=> fact(n) = n*fact(n-1)

fact(5) = 5*fact(4)
fact(4) = 4*fact(3)
fact(3) = 3*fact(2)
fact(2) = 2*fact(1)
fact(1) = 1*fact(0)
fact(0) = 1
Exemple : calcul d’une factorielle
• Version 1 :
Fonction factorielle (n: entier) : entier
DEBUT
fact  n*factorielle(n-1)
Retourne fact
FIN

Oui, mais quand est-ce que l’on s’arrête ?

Factorielle
• Version 2
Fonction factorielle (n: entier) : entier
DEBUT
Si n > 1
alors retourne n*factorielle(n-1)
Sinon
retourne n
Fsi
FIN
• Oui mais, et factorielle 0 ?
Factorielle
• Version 3
Fonction factorielle (n: entier) : entier
DEBUT
Si n = 0
Alors retourne 1
Sinon
retourne n*fact(n-1)
Fsi
FIN
La récursivité
• Une fonction (procédure) récursive est une fonction (procédure) qui
s’appelle elle-même, directement ou par l’intermédiaire d’une autre
fonction ou procédure.
• Un problème difficile de la programmation récursive est de trouver
la(les) bonne(s) condition(s) d’arrêt.
 • Croisée
La récursivité Procedure recursive1 ()
DEBUT
• Simple …
Recursive2 ()
Procedure recursive ()
…
DEBUT FIN
…
recursive () Procedure recursive2 ()
DEBUT
…
…
FIN recursive1 ()
…
FIN
Exemple : calcul d’une factorielle
• n! = n*n-1*n-2*…*2*1

=> fact(n) = n*fact(n-1)

fact(5) = 5*fact(4)
fact(4) = 4*fact(3)
fact(3) = 3*fact(2)
fact(2) = 2*fact(1)
fact(1) = 1*fact(0)
fact(0) = 1
Exemple : calcul d’une factorielle
• Version 1 :
Fonction factorielle (n: entier) : entier
DEBUT
fact  n*factorielle(n-1)
Retourne fact
FIN

Oui, mais quand est-ce que l’on s’arrête ?

Factorielle
• Version 2
Fonction factorielle (n: entier) : entier
DEBUT
Si n > 1
alors retourne n*factorielle(n-1)
Sinon
retourne n
Fsi
FIN
• Oui mais, et factorielle 0 ?
Factorielle
• Version 3
Fonction factorielle (n: entier) : entier
DEBUT
Si n = 0
Alors retourne 1
Sinon
retourne n*fact(n-1)
Fsi
FIN
Factorielle en PHP
<?php
function factorielle($nbre)
{
if($nbre == 0)
{
return 1;
}
else
{
return $nbre*factorielle($nbre-1);
}
}
echo factorielle(5);
?>