LES VARIABLES SCALAIRES

codage binaire
boucles
récursivité

codage binaire

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 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) fait que l'ajout de 1 à 32767 (le plus grand entier signé) donne -32768 (cela devait de toute façon donner un nombre car 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.

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 2¹²⁷=1,7.10³⁸). On cherchera donc à ne combiner que des réels du même ordre de grandeur. Par exemple en mécanique, ajouter à une dimension d'un mètre une dilatation thermique d'un micron n'a de sens que si les flottants possèdent plus de 6 chiffres significatifs, donc par exemple un algorithme cumulatif ne donnera pas de résultat si le pas en température est trop faible.

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,1_d = 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 <stdio.h>
void main(void)
 {
  float x=1000;
  int i;
  for (i=0;i<10000;i++)x+=0.1;
  printf("On obtient %12.4f au lieu de 2000.0000\n",x);
 }

Ce problème est moins flagrant en C que dans les autres langages, le C effectuant toujours les calculs sur des réels en double précision. 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 réels.

boucles

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). (voir exemples dans la première partie).

Lorsqu'une valeur à calculer C dépend de n calculs intermédiaires C_i (que l'on ne désire pas mémoriser), la méthode la plus simple consiste à initialiser C à la première valeur C₁, puis pour i variant de 2 à n, calculer chaque C_i 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 xⁿ :

#include <stdio.h>
void main(void)
 {
  int n,i,x,result;
  printf("entrez x et n : ");
  scanf("%d %d",&x,&n);
  result=x;
  for(i=1;i<n;i++)result*=x;
  printf("résultat : %d\n",result);
 }

La fonction puissance est souvent disponible dans les langages (pow en C), mais correspond à un calcul assez long et souvent moins précis (xⁿ=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 2x⁴-3x³+x²-5x+2 pour x réel.

exemple (boucle_B) : calcul de moyenne :

#include <stdio.h>
void main(void)
 {
  int n=0;
  float note,moy=0;
  do
   {
    printf("entrez la note (négative pour terminer) : ");
    scanf("%f",&note);
    if(note>=0) 
     {
      moy+=note;
      n++;
     }
   }
  while(note>=0);
  moy/=n;
  printf("moyenne : %f\n",moy);
 }

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.

récursivité

On appelle fonction récursive une fonction qui s'appelle elle-même. 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).

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.