6. N-uplets, listes et tableaux

Les N-uplets et les listes sont des structures qui permettent de construire des données composées à partir de données élémentaires. Une notion essentielle en informatique.

Opérateur ','

En réalité, comme Mr Jourdain faisait de la prose sans le savoir, nous avons déjà utilisé des N-uplets, et cela, à chaque fois que nous avons utilisé la ',' (virgule). a,b par exemple désigne le couple (ou 2-uple) des termes a et b.

Il est souvent utile de regrouper ainsi des données pour construire une donnée composée comme dans l'exemple suivant :

var nom, prenom, age = "Durand", "Paul", 26

En écrivant cette instruction avec des parenthèses, la structure de donnée apparaît encore plus clairement :

var (nom, prenom, age) = ("Durand", "Paul", 26)

On peut désigner l'ensemble de la structure par une seule variable, comme ceci :

var personne = ("Durand", "Paul", 26)

Ou encore, en précisant le type :

var personne : (string, string, int) = ("Durand", "Paul", 26)

Et ensuite, afin d'obtenir séparément les éléments de la structure, il est possible d'écrire une affectation comme :

(nom, prenom, age) = personne

Mais voyons dès maintenant une autre façon d'utiliser des données composées.

Les listes

Alors que les N-uplets permettent d'associer des données de types différents, les listes, elles, servent à regrouper des données de même type, par exemple, une liste de nombres, une liste de noms de personnes, des N-uplets etc. Elles se notent avec des guillemets '{' '}' (et des ',' pour séparer les éléments). Exemples :

add nombresPremiers = { 2, 3, 5, 7, 11, 13, 17, 19, 23 }
add mails = { ("Paul", "paul.martin@wanadoo.fr"), ("Lucie", "luciedurand@gmail.com") }

On accède aux éléments de listes en spécifiant un index entre crochets '[' ']', l'index commençant à 0. Exemple :

---? write nombresPremiers[3]

---= 7

Calendrier perpétuel

Pour illustrer l'utilisation de listes et, en même temps, faire une petite pause dans notre parcours, nous vous proposons un programme "calendrier perpétuel" qui à partir de n'importe quelle date (du calendrier grégorien) trouve le jour de la semaine correspondant.

Sans entrer dans les détails, disons que des décalages sont liés au jour, au mois, à l'année dans le siècle et au siècle. On sait par exemple que, d'une année à la suivante, on a un décalage d'un jour sauf après une année bissextile où le décalage est de 2 jours. Ou encore, que du moins de janvier à février, on a un décalage de 3 jours car janvier compte 31 jours, c'est-à-dire 4 semaines plus 3 jours. Etc.

On connait moins, en général, l'exception concernant les années séculaires 1900, 2000, 2100 etc. qui, bien qu'elles soient divisibles par 4, ne sont bissextiles que si le numéro du siècle est également divisible par 4.

En ajoutant tous ces décalages et en tenant compte de toutes ces particularités, on obtient un nombre qui, modulo 7, nous indique le jour de la semaine.

C'est ce que fait le programme ci-contre qui, en définitive, n'est pas si long.

Deux listes sont utilisées : l'une donnant les noms des jours de la semaine, l'autre les décalages associés à chaque mois qui sont ajustés plus loin pour tenir compte de la présence ou non d'un 29 février.

res est la somme résultant de tous les décalages, on en prend le modulo 7 pour nous ramener à un nombre compris entre 0 et 6, correspondant à l'indice du jour de la semaine.

Exemple d'appel de la fonction quelJour :

---? quelJour 17,02,2021

---= "mercredi"

quelJour (j:int, m:int, a:int):string
var jours = {"dimanche", "lundi", "mardi", "mercredi", "jeudi", "vendredi", "samedi"};
var mois = {0,3,3,6,1,4,6,2,5,0,3,5};
var s = a // 100; # siècle
a = a % 100; # quantième de l'année dans le siècle
var res = j + mois[m-1] + a + a//4 + 2*(3-s%4);
if a%4==0 && (a!=0 || s%4==0) && m<=2 then res -=1 fi;
jours[res%7]

Opérations et fonctions sur les listes

Plusieurs opérations s'appliquent aux listes :

?< qui permet de tester l'appartenance d'un élément à une liste. Exemple : i ?< {2,3,5}
:< qui donne l'index d'un élément dans une liste. Exemple : i :< {2,3,5}
++ qui permet de concaténer deux listes. Exemple : {2,3,5} ++ {7,11}
| qui permet d'ajouter un élément à une liste. Exemple : {2,3,5} | 7
++= qui combine concaténation et affectation (cf. opérateurs combinés vu précédemment). Exemple : prem ++= {7,11, 13,17}
|= qui combine ajout d'un élément et affectation. Exemple : prem |= 7

Quelques fonctions également :

<liste>.length : longueur de <liste>
<liste>.left(n) : sous-liste des n premiers éléments de <liste>
<liste>.right(n) : sous-liste des n derniers éléments de <liste>
<liste>.middle(i, n) : sous-liste des n éléments de <liste> à partir de la ième position
<liste>.middle(i) : sous-liste de tous les éléments de <liste> à partir de la ième position

On remarque ici une nouvelle notation de fonctions appelées "fonctions membres" ou "méthodes" qui s'appliquent à un objet particulier, une liste dans le cas présent. L'objet est d'abord indiqué suivi d'un "." puis de l'appel de fonction sans espace. Par exemple :

---? nombresPremiers.length

---= 9

Ou encore :

---? {"abc", "de", "f", "ghij", "xyz"}.left(3)

---= {"abc", "de", "f"}

Ces nouvelles possibilités nous permettent de dérouler maintenant l'exercice suivant sur les décimales des nombres rationnels.

Tout d'abord, voyons comment on peut afficher autant de décimales que l'on veut du quotient décimal de deux entiers naturels.

Pour cela, nous définissons une procédure division qui reproduit la technique habituelle de la division : pour chaque décimale, on part du reste de la division auquel on ajoute un 0 (on multiplie par 10) ; on effectue la division entière de ce nombre par le diviseur, ce qui donne la nouvelle décimale ; on calcule le nouveau reste et on recommence jusqu'à obtenir le nombre de décimales voulu.

Cette procédure, définie ci-contre, permet d'afficher N décimales de la division de p par q. Elle utilise l'instruction write avec l'option /c qui permet d'écrire les chiffres successifs sur la même ligne.

Exemple d'appel de la fonction division :

---? division 1,7,50

0.14285714285714285714285714285714285714285714285714

---= ok

Les nombres rationnels p/q sont parfois décimaux, quand on finit par obtenir le reste 0, et parfois non décimaux, quand on n'arrive jamais au reste 0. C'est le cas de 1/7 ci-dessus. Dans ce dernier cas, on observe une période dans la liste des décimales à partie de laquelle on retrouve la même série de chiffres. Cette période est de longueur 6 dans notre exemple.

Nous allons maintenant utiliser les listes pour repérer ces périodes.

Dans la division telle qu'on la calcule classiquement, les restes que nous obtenons successivement sont, par définition, compris entre 0 et q-1. Et pour les rationnels non décimaux, ces restes sont compris entre 1 et q-1. De cela, on déduit que la longueur de période sera au plus égale à q-1.

Dans notre nouveau programme, basé sur la procédure division, nous mémorisons ces restes successifs et dès que nous arrivons à un reste déjà obtenu précédemment, nous déduisons que nous avons fini de parcourir la 1ère période et nous sortons de la boucle de recherche des décimales. Bien sûr, nous quittons la boucle également lorsque le reste égal à 0. Voir ci-contre.

Pour poursuivre l'exercice : à partir de ce programme, trouver tous les nombres q inférieurs à 500 tels que 1/q est un rationnel non décimal dont la période est de longueur maximale (c'est-à-dire q-1).

division (p:int, q:int, N:int);
var d = p//q;
var r = p%q;
write/c d ++ ".";
for var i=1 to N do
p = r*10;
d = p//q;
r = p%q;
write/c d
done

calculPeriode (p:int, q:int);
var d = p//q;
var r = p%q;
write/c d ++ ".";
var lr = {};
while (r!=0 && !(r ?< lr)) do
lr |= r;
p = r*10;
d = p//q;
r = p%q;
write/c d
done;
write "\nNombre de décimales : " ++ lr.length;
if r==0 then
write "Nombre rationnel décimal"
else
var lgPeriode = lr.length - (r:<lr);
write "Nombre rationnel non décimal, longueur de période : " ++ lgPeriode
fi

Les tableaux

Les modules nous avons vus à la page précédente nous offrent également la possibilité de créer des tableaux de données.

Une fois un module créé par la commande :

add t:Module = new Module

nous pouvons ajouter des éléments indexés, en spécifiant un index entre crochets '[' ']'. Par exemple :

add t[1] = ("Pauline", 1997)
add t[2] = ("Juliette", 2000)
add t[3] = ("Denis", 2003)

Pour utiliser ces éléments, il est alors possible d'écrire une boucle comme :

for var i=1 to 3 do
var nom, annee = t[i];
write "Age de " ++ nom ++ " : " ++ (2021-annee)
done

Remarque : les listes permettent de réaliser à peu près la même chose. En fonction des problèmes à traiter, nous pourrons donc utiliser l'une ou l'autre des solutions, selon ce qui nous semble le plus commode.

Tri à bulles

A titre d'exercice, nous allons implémenter l'algorithme de tri le plus simple appelé "tri à bulle" (Bubble sort in English).

Etant donné un tableau de valeurs numériques val, nous allons réordonner ces valeurs afin qu'elles apparaissent dans l'ordre : val[1] < val[2] < val[3] etc.

Pour commencer, créons le tableau à trier avec des valeurs aléatoires :

for var i=1 to 30 do
add /f val[i] = Math.random(100)
done

Puis, affichons les valeurs obtenues pour voir les valeurs obtenues (et être sûrs qu'elles ne sont pas déjà triées !) :

for var i=1 to 30 do
write val[i]
done

Le tri à bulles consiste à parcourir tout le tableau et à inverser deux valeurs consécutives si elles ne sont pas dans l'ordre ; puis à recommencer tant qu'il y a des échanges à faire.

Cela s'appelle "tri à bulles" car les plus grandes valeurs vont alors rapidement trouver leur place à la fin du tableau de la même façon que des bulles remontent à la surface de l'eau. Et, en effet, dans notre exemple, dès le 1er passage la 30ème place contiendra bien la plus grande valeur ; au 2ème passage, on aura le bon nombre en 29ème position etc. Mais, bien entendu, en fonction de l'ordre fourni au départ, le tri peut se faire plus rapidement.

Dans une première solution, nous parcourir donc parcourir les valeurs du tableau de 1 à 30 ; puis de 1 à 29 ; de 1 à 28 etc. Après avoir développée la procédure tri1 qui procède ainsi, vous pourrez regarder le code proposé ci-contre.

La seconde solution, implémentée par la procédure tri2, apporte une optimisation en limitant le nombre de parcours des éléments du tableau.

Mais sachez qu'il existe de bien meilleurs algorithmes de tri et que si vous avez un gros volume de données à trier, il sera préférable d'avoir recours à des solutions plus efficaces.

tri1 (t);
for var fin=30 to 2 step -1 do
for var i=1 to fin-1 do
if t[i]>t[i+1] then
t[i],t[i+1] = t[i+1],t[i]
fi
done
done

tri2 (t);
var fin=30;
while fin>1 do
var dern = 0;
for var i=1 to fin-1 do
if t[i]>t[i+1] then
t[i],t[i+1] = t[i+1],t[i];
dern=i
fi
done;
fin = dern
done