UFR Physique et Ingénierie - Campus Meinau - les variables scalaires
Que peut-on faire avec des varibles simples (j’entends par là, celles qui ne peuvent contenir qu’une seule valeur à la fois) ? Nous allons voir ici comment les variables sont stockées, et quelques algorithmes de base (boucles et récursivité).
Les seules valeurs que peut traiter l’ordinateur (et d’ailleurs tout système numérique) est le 0 et le 1 (en fait, c’est nous qui représentons par 0 ou 1 le fait que le système numérique ait vu du courant ou non). Un problème important est que différents types d’informations doivent être codés : instructions machine (lignes de programmes), valeurs numériques, caractères, adresses,… et que rien ne permet de distinguer dans un groupe de 0 et de 1 le type d’information qu’il est censé représenter (10010110 est sur un PC le code machine permettant d’échanger les contenus des registres SI et AX, mais également le code du caractère ’û’, de l’octet signé décimal -106, du signé 150, l’exposant du flottant 1,23x10-32, etc…). Il est donc capital d’associer à chaque mémoire que l’on utilise le type de donnée que l’on y mettra. C’est ce que permet la déclaration des variables dans les langages évolués (explicite en Pascal et en C, implicite en Basic et Fortran). Néanmoins cette erreur reste possible (en C, lors d’une erreur sur des pointeurs, par l’utilisation des unions, ou simplement par erreur de format dans un printf). Une utilisation d’objets (avec attributs privés et accesseurs publics) limitera ces risques.
Une autre erreur est due à la représentation des nombres négatifs. En effet, le signe ne peut être, lui aussi, représenté que par 0 ou 1. Le codage choisi (pour les entiers 16 bits, nommés "short" en C++) fait que l’ajout de 1 à 32767 (le plus grand entier signé) donne -32768. Cela devait de toute façon donner un nombre car, dans un bit d’une mémoire, soit il y a du courant, soit il n’y en a pas, il n’est pas prévu de combinaison de 0 et 1 représentant une erreur. La plupart des compilateurs ne signalent pas d’erreur en cas de dépassement de capacité de nombres entiers, car ça ralentirait énormément les programmes (le test dure souvent 4 fois le temps du calcul, et des calculs il en fait souvent, rien que pour passer à la mémoire suivante il faut additionner 1).
Autre problème, la codification des réels. Représenter la présence ou non d’une virgule par un 0 ou un 1 est évidement impossible (comment la reconnaître ?), la première solution envisagée était donc la virgule fixe (un mot pour la partie entière, un autre pour la partie fractionnaire). On utilise désormais la "virgule flottante" (d’où le nom de flottants ou float), représentée par un mot pour la mantisse (qui est un réel en virgule fixe puisque pas de partie entière), un autre (souvent de taille différente) pour l’exposant (entier signé). Ceci implique deux limitations : le nombre de chiffres significatifs (dû à la taille de la mantisse), et le plus grand réel codifiable (dû à la taille de l’exposant, par exemple 2127=1,7.1038). Donc, même sans dépasser la capacité des float, on peut avoir une erreur si l’on n’a pas combiné que des réels du même ordre de grandeur. Sur un float en 32 bits, on peut atteindre 1,7.1038, mais seulement avec moins de 7 chiffres décimaux significatifs. Par exemple en mécanique, ajouter à une dimension d’un mètre une dilatation thermique d’un micron n’aurait pas de sens, donc par exemple un algorithme cumulatif ne donnera pas de résultat si le pas en température est trop faible (et tous ceux qui croient qu’en diminuant le pas de calcul on augmente la précision se trompent).
Dans les deux cas (virgule fixe ou flottante), un problème se pose : en fait, nous ne pouvons représenter qu’un sous ensemble des réels (je ne pense pas que les mathématiciens lui aient donné un nom) qui correspond à la différence, en base 10, entre D et R. En fait on ne peut représenter que les nombres pouvant s’écrire sous forme d’une partie fractionnaire comportant un nombre fini de chiffres (en binaire). Or, comme c’est impossible en base 10 pour 1/3 (qui pourtant s’écrit 0,1 en base 3) la représentation en binaire de 1/10 donne une suite infinie, qui est donc toujours tronquée (0,1d = 0,000100100100100100100…b). donc sur tout ordinateur calculant en binaire, (1/10)*10 donne 0,999999999… Cette erreur devient gênante dans le cas où le résultat du calcul précédent est utilisé dans le calcul suivant, pour de grandes suites de calculs.
exemple (flottant) :
#include <iostream>
using namespace std;
int main(void)
{
float x=1000;
int i;
for (i=0;i<10000;i++)x+=0.1;
cout.precision(10);
cout<<"On obtient "<<x<<" au lieu de 2000.0000\n";
}
Ce problème est moins flagrant en C que dans d’autres langages, le C effectuant toujours les calculs sur des réels en double précision (14 chiffres décimaux significatifs). Il en résulte néanmoins que, par exemple, il ne faut pas tester dans un programme si le résultat d’un calcul flottant est nul mais si sa valeur absolue est inférieure à un petit nombre. On cherchera aussi, autant que possible, à choisir des algorithmes utilisant des entiers plutôt que des réels, d’autant plus que les calculs sur des flottants sont plus lents que sur des entiers.
Tous les langages possèdent des structures permettant de répéter des instructions, les boucles. En général, certaines sont réservées aux cas où l’on connaît à l’entrée le nombre de boucles à effectuer (for en C), et celles dont on connaît la condition d’arrêt (while et do-while en C). Je ne détaille pas d’exemples ici, je suppose que vous connaissez le C++, ou regardez ici
Lorsqu’une valeur à calculer C dépend de n calculs intermédiaires Ci (que l’on ne désire pas mémoriser), la méthode la plus simple consiste à initialiser C à la première valeur C1, puis pour i variant de 2 à n, calculer chaque Ci et le cumuler à C. C’est en général la méthode utilisée pour les calculs de sommes, produits, suites…
exemple (boucle_A) : calculer xn :
#include <iostream>
using namespace std;
int main(void)
{
int n,i,x,result;
cout<<"entrez x et n : ";
cin>>x>>n;
result=x;
for(i=1;i<n;i++)result*=x;
cout<<"résultat : "<<result<<endl);
}
La fonction puissance est souvent disponible dans les langages (pow en C), mais correspond à un calcul assez long et souvent moins précis (xn=exp(n*ln(x)) qui donne toujours un résultat avec une erreur de précision même si x est entier). La méthode ci-dessus sera plus rapide soit pour n petit (quelques multiplications d’entiers sont plus rapides qu’une exponentielle de logarithme), soit quand toutes les puissances intermédiaires doivent être connues.
Exercice (boucle) : faire le programme calculant 2x4-3x3+x2-5x+2 pour x réel.
exemple (boucle_B) : calcul de moyenne :
#include <iostream>
using namespace std;
int main(void)
{
int n=0;
float note,moy=0;
do
{
cout<<"entrez la note (négative pour terminer) : ";
cin>>note;
if(note>=0)
{
moy+=note;
n++;
}
}
while(note>=0);
moy/=n;
cout<<"moyenne : "<<moy<<endl;
}
Les valeurs des notes ayant servi au calcul ne sont pas mémorisées, car toutes stockées successivement dans la même mémoire.
On appelle fonction récursive une fonction qui s’appelle elle-même. Pour comprendre lea récursivité, imaginez l’exemple du parcours d’un disque dur :
Lister un dossier c’est :
rechercher un à un les composants du dossier
si c’est un fichier en alfficher le nom (et dessiner l’icône…)
si c’est un sous-dossier le lister (de la même manière, c’est ici qu’on est récursif)
Parcourir tout un disque dur c’est :
lister sa racine (c :\ par exemple sous Windows)
La récursivité n’est possible que dans un langage acceptant des variables locales. En effet, l’emploi de la récursivité n’est réellement utile que lorsqu’une fonction doit retrouver, après un appel récursif, toutes ses variables locales dans leur état initial. Dans le cas contraire, une méthode itérative (boucle) sera en général plus efficace (il est inutile de mémoriser les variables locales et les restaurer pour ne plus les réutiliser), comme par exemple pour le calcul d’une factorielle (voir mon document sur le C, paragraphes 4.6 et 4.7, pour l’explication de la récursivité, l’empilement des variables locales et l’exemple de la factorielle). Pour le C++ regardez ici (paragraphe 9.7).
Néanmoins dans un certain nombre de cas, l’emploi de la récursivité facilite la programmation. Si le temps de calcul ou la mémoire utilisée sont prohibitifs pour de grands nombres de données, il est toujours possible de traduire un algorithme récursif en itératif, et souvent de manière plus efficace que le compilateur, qui est obligé de le faire (le langage machine n’est pas récursif) sans connaître aussi bien que vous les conditions d’utilisation de l’algorithme.
Nous parlerons plus particulièrement d’algorithmes récursifs pour les listes, arbres et graphes.
Rappels : une classe définit la manière de représenter des données dans sun programme. Elle réunit les attributs (une ou plusieurs variables, plus ou moins complexes, y compris tableaux et objets) et les méthodes (les diverses actions que l’on prévoit d’effectuer sur les attributs). Le mécanisme d’héritage permet de créer une nouvelle classe à partir d’une classe existante (une ou plusieurs en C++ mais une seule en java), en lui ajoutant si nécessaire des attributs et méthodes (on ne peut pas vraiment en supprimer, mais en empêcher l’accès). La surcharge quand à elle correspond au fait de pouvoir réutiliser un même nom (d’attribut ou méthode) dans deux classes différents, sans qu’il n’y ait obligatoirement de lien (c’est à dire que si ça doit être lié, c’est à vous de le préciser). On peut également surcharger des méthodes dans une même classe, et dans ce cas le compilateur choisira, parmi toutes les méthodes qui ont le même nom, celle (qui doit être unique) ayant la même signature (définie suivant le type et l’ordre des arguments transmis). En C++ (pas en java) on peut même surcharger des opérateurs (+ pour ajouter par exemple).
L’idéal (en matière de sécurité du code source) serait que même pour des variables simples on crée des objets. Cela permettrait de limiter ce que l’on appelle les "effets de bord" : les erreurs dues aux valeurs abhérentes, aux dépassements de capacité,…
Si l’on doit traiter dans un programme des poires et des pommes, et qu’on considère qu’on peut ajouter des pommes (aux pommes), des poires (aux poires), mais pas de "mélange des genres", le plus sûr sera de définir les classes pommes et poires, et surcharger l’opérateur + conformément à nos contraintes.
A l’inverse, on ne va pas créer de classe rien que pour une variable locale qui ne sert que le temps d’effectuer quelques instructions. Bien que… Si cette variable nous sert pour une fonction bien précise, et que cette fonction est utilisée assez souvent, on peut penser à créer une classe pour cela. Par exemple pour les indices de boucle, on peut créer une classe nommée "itérateurs" (d’ailleurs, elle existe).