Name: Algorithmique - Techniques fondamentales de programmation Exemples en PHP (nombreux exercices corrigés) - 3e édition (BTS, DUT Informatique)
Rating: 5 (1 reviews)

Présentation

1. Principe et définitions

a. Simplifier les variables

Jusqu’à présent, les types de données que vous avez rencontrés sont des scalaires, sauf pour les chaînes de caractères. Pour rappel un scalaire est un type de donnée qui ne représente qu’une seule variable à la fois. Un entier, un caractère, un réel, un booléen, etc., sont des scalaires. Une chaîne de caractères non : il s’agit d’une suite, ou liste, de caractères, les uns après les autres. Une chaîne est donc une liste ordonnée par vos soins de scalaires. Les langages proposent souvent un type pour les chaînes de caractères, mais c’est une facilité offerte par ceux-ci. Un langage comme le C n’en propose pas. En algorithmique, vous utilisez le type "alphanumérique", il vous faudra alors faire attention lors de la conversion en C.

Mais alors comment se représenter une chaîne de caractères avec un type scalaire ? Il faut pour cela se rappeler comment sont placées en mémoire les informations. La mémoire de l’ordinateur est composée de cases pouvant contenir certaines informations. Ces cases sont numérotées (on parle d’adresse de la case) et contiennent des données. Ces données représentent ce que vous voulez selon le contexte de leur utilisation.

Vous pouvez, par exemple, partir du principe qu’elles contiennent des scalaires. Si une case mémoire contient le nombre 65, ce peut être la valeur entière 65 ou encore le code ASCII du caractère "A". Une case mémoire peut parfaitement contenir l’adresse d’une autre case mémoire : c’est un peu plus compliqué que cela en a l’air et ce sera l’objet d’un plus long exposé dans la suite de cet ouvrage.

Une chaîne de caractères est donc une suite de scalaires de type Caractère, les uns derrière les autres dans des cases mémoires en principes contiguës. Selon le même principe, si vous reprenez l’exemple de la saisie des notes d’étudiants, ne pensez-vous pas qu’il serait plus pratique de pouvoir conserver ces notes pour la suite du programme ? Il serait...

Manipulations simples

1. Recherche d’un élément

Vous disposez d’un tableau de n éléments correspondant aux prénoms de vos amis et vous voulez savoir si l’un de ceux-ci est bien présent dans votre tableau. Il faut alors le rechercher. Le principe consiste à balayer l’intégralité du tableau à l’aide d’une structure itérative et à en sortir dès que l’élément a été trouvé ou que le nombre maximal d’indice a été dépassé. À la sortie de la boucle, il faudra de nouveau vérifier pour savoir si oui ou non l’élément a été trouvé : il se peut en effet que tout le tableau ait été parcouru et que ce soit la raison de la sortie de la boucle.

PROGRAMME RECHERCHE 
VAR 
  Tableau noms:tableau[1..10] de chaînes 
  rech:chaîne 
  i:entier 
DEBUT 
  i1 
  Tant que i<=10 et noms[i]<>rech Faire 
    ii+1 
  FinTantQue 
  ii-1 
  Si nom[i]=Rech Alors 
    Afficher "Trouvé" 
  Sinon 
    Afficher "Absent" 
  FinSi 
FIN

Il y a la possibilité de faire différemment avec un drapeau :

PROGRAMME RECHERCHE2 
VAR 
  Tableau noms:tableau[1..10] de chaînes 
  Rech:chaîne 
  i:entier 
  trouve:booléen 
DEBUT 
  i1 
  trouveFAUX 
  Tant que i<=10 et trouve=FAUX Faire 
    Si nom[1]=rech Alors 
      trouveVRAI 
    FinSi 
    ii+1 
  FinTantQue 
  Si trouve Alors 
    Affiche "Trouvé" 
  Sinon 
    Affiche "Absent" 
  FinSi 
FIN

En PHP :

<html> 
  <head><meta/> 
    <title>Recherche</title> 
  </head> 
  <body> 
  <?php 
 
  $t=array(10,20,14,25,17,8,10,12,15,5,41,19,2,6,21); 
  $i=0; 
  $trouve=false; 
  $rech=15; 
 
  while($i<count($t) && !$trouve) { 
 ...

Algorithmes avancés

1. Les algorithmes des tris

a. Principe

Vous avez pu voir dans les exemples précédents l’intérêt des tableaux pour le stockage de valeurs multiples. Mais suivant le cas, il peut être utile d’avoir besoin d’obtenir une liste ordonnée de valeurs par ordre croissant ou décroissant. Autrement dit, vous voulez trier le contenu du tableau. Prenez le cas d’un professeur souhaitant trier les notes de ses élèves de la plus basse à la plus haute, ou des résultats d’un tirage du loto pour le rendre plus lisible.

Imaginez un tirage du loto de cinq numéros, évidemment tous différents, dont les valeurs s’étalent entre 1 et 49. Voici l’état initial du tableau suite au tirage au sort :

48	17	25	9	34

Il existe plusieurs méthodes permettant de trier ces différentes valeurs. Elles ont toutes leurs qualités et leurs défauts. Ainsi une méthode sera lente, l’autre sera plus gourmande en mémoire et ainsi de suite. C’est leur complexité qui détermine leur usage notamment pour de grandes plages de valeurs.

Dans les algorithmes suivants, la variable Cpt contient le nombre d’éléments du tableau initial et t[] est le tableau.

Il est intéressant de prendre en compte la complexité de ces divers algorithmes, bien que cette notion, présentée au premier chapitre, ne soit généralement pas (ou peu) abordée dans les premières années d’études en informatique. Les algorithmes ont souvent une complexité proche. Pourtant à l’usage un tri shell est plus rapide qu’un tri par sélection, tout dépendant du nombre d’éléments et l’éventuel ordre de ceux-ci au départ.

b. Le tri par création

Le tri par création ne sera abordé que du point de vue théorique. En effet si cette méthode semble simple, elle est en fait lourde et compliquée. Si on demande à un débutant en programmation comment trier un tableau, il vous proposera très certainement de créer un deuxième tableau dans lequel on placera au fur et à mesure les éléments du premier tableau dans l’ordre croissant.

C’est...

Structures et enregistrements

1. Principe

Les tableaux sont certes très pratiques, mais ils ne permettent pas toujours de répondre efficacement à tous les besoins de stockage. Un tableau est une structure de données dont tous les éléments sont de même type. Que faire quand vous avez besoin de placer dans une structure de type tableau des enregistrements de types différents ?

Comme exemple concret, prenez un catalogue de produits dans un magasin spécialisé. Un article est décrit à l’aide d’une référence, un nom (libellé) et un prix. Les deux premiers sont des chaînes de caractères, le dernier un nombre réel. Comment se représenter cela avec des tableaux ? Il faudrait trois tableaux : un pour les références, un autre pour les libellés et un troisième pour les prix. L’indice de l’article devrait être identique pour les trois tableaux.

C’est possible, faisable, mais en pratique totalement ingérable dès qu’il s’agit d’aller un peu plus loin que de simples traitements. Quid des tris ? Quid des recherches ? Cela devient difficile. Il faudrait donc une sorte de méta-type particulier qui pourrait regrouper en un seul ensemble des variables de types différents.

Ces méta-types existent. Ils s’appellent des structures, ou types structurés et permettent de décrire des enregistrements. Les enregistrements sont en fait des structures de données composées d’éléments de types différents ou non. Ces structures composées de plusieurs éléments forment une entité unique qui est appelée un type structuré.

Autrement dit, vous pouvez créer vos propres types de données en combinant d’autres éléments de types différents ou non et créer des variables de ce nouveau type, qu’on appelle des enregistrements. Les différents éléments contenus dans un type structuré sont appelés des champs.

2. Déclaration

a. Type structuré

Le type structuré est opposable aux types dit primitifs vus jusqu’à présent. Un type structuré peut contenir des éléments de types primitifs (entiers, réels...

Exercices

Exercice 1

Créer un tableau contenant les chiffres de 1 à 10 et un autre tableau contenant les nombres de 11 à 20. Ensuite créer un autre tableau contenant la somme des deux premiers tableaux et afficher ses valeurs. Il faut utiliser les boucles pour créer ces tableaux.

Écrire le programme PHP équivalent.

Exercice 2

Soit deux tableaux :

Le tableau1 est composé des éléments 6,25,35 et 61.
Le tableau2 est composé des éléments 12,24 et 46.

Écrire l’algorithme permettant de calculer une valeur représentative de ces deux tableaux notée S. La valeur S se calcule en multipliant chaque valeur du tableau1 par celle du tableau2 et en additionnant le tout.

Dans cet exemple, la valeur S sera égale à :

12*6+12*25+12*35+12*61+24*6+24*25+24*35+24*61+46*6+46*25+46*35+46*61

Il faut bien entendu utiliser les boucles pour réaliser cet exercice.