retour
au sommairePrésenté par Willrich-Moritz Olivier, DEUG TI option EEA, juin 98
L'étude faite dans ce rapport est celle des différentes boucles, la récursivité, les boucles imbriquées dans le langage C. Elle comporte un cours, des exemples, ainsi qu'un programme complet d'application des boucles dans les suites numériques. Le cours est systématiquement suivi d'exemples. Les différents exemples d'application des boucles portent sur le calcul de la factorielle d'un nombre pour montrer ce qui les différentient les unes des autres.
Une instruction peut être :
Par définition, une boucle est une suite d'instructions répétées jusqu'à ce que la condition de sortie soit vérifiée. En C, on devra spécifier la condition de continuation (complémentaire de la condition de sortie). On va donner une instruction, puis on va demander au programme de répéter cette instruction tant que la condition (qu'on a définie) est vraie.
Il existe trois types de boucles :
On la place dans un programme de la façon suivante :
while
(expression)
Instruction
;
Elle évalue d'abord l'expression (la condition) entre parenthèses. Si la condition est vraie, elle exécute l'instruction. Puis elle teste de nouveau la condition et cela jusqu'à ce que la condition devienne fausse. Alors la boucle se termine et le programme passe à la suite (ou s'arrête, si c'est la dernière instruction).
Exemple d'utilisation : Calcul de la factorielle d'un nombre
int fact(int n)
{
int r=1;
while (n>1)
{
r= r * n - -;
}
return (n);
}
On la place dans un programme de la façon suivante :
Do
Instruction
While
(expression);
L'instruction s'exécute, puis l'expression est évaluée. Si elle est vraie, on effectue de nouveau l'instruction, et ainsi de suite.
Exemple : calcul de la factorielle d'un nombre
int fact(int n)
{
int r=1;
do
{
r= r * n- -;
}
while(n>1);
return(r);
}
On la place dans un programme de la façon suivante :
for (expression 1; expression
2; expression
3)
instructions;
Le rôle de l'expression 1 est d'initialiser un paramètre qui contrôle la reprise de la boucle. L'expression 2 est la condition à satisfaire pour continuer l'exécution de la boucle et l'expression 3 sert à modifier la valeur du paramètre initialisé par l'expression 1.
Quand l'instruction for est exécutée, l'expression 2 est évaluée et testée avant chaque parcours de la boucle et l'expression 3 est évaluée à la fin de chaque passage. Ainsi l'instruction for est équivalente à :
expression 1;
while
(expression 2)
{ instruction;
expression 3; }
Exemple : calcul de la factorielle d'un nombre
int fact(int n)
{
int r=1, i;
for (i=n; i>1; i- -)
r= r * i;
return(r);
}
La boucle for est préférable lorsque l'initialisation et l'incrémentation sont simples, puisqu'elle regroupe les instructions de contrôle en tête de boucle. Elle est la plus simple à mettre en oeuvre lorsque l'on connaît le nombre d'itérations à effectuer.
La boucle do...while, qui teste la condition d'arrêt à la fin, voit donc le corps de la boucle s'exécuter au moins une fois, alors que la boucle while peut ne pas l'exécuter du tout (si la condition est déjà fausse).
Elle est utilisée pour mettre fin à une boucle ou sortir d'une instruction de sélection. Elle peut figurer dans les instructions : while, do...while, for (ainsi que switch)
Elle s'écrit tout simplement :
break ;
sans expression ni instruction imbriquée.
Le rôle de l'instruction continue est de suspendre l'itération en cours dans la boucle. La boucle ne se termine pas : ce sont seulement les instructions restantes de l'itération en cours qui sont sautées, et le traitement reprend dans la même boucle au début de l'itération suivante.
(continue et break ont donc un rôle totalement différent).
L'instruction continue peut figurer dans les trois boucles : while, do...while, for, et elle s'écrit :
continue;
sans expression ni instruction imbriquée.
La récursivité est le fait qu'une fonction s'appelle elle-même. C'est à dire qu'on crée une fonction qui a comme instruction de rappeler cette même fonction jusqu'à une certaine condition de sortie.
On utilise la récursivité à la place des boucles uniquement quand celles-ci ne peuvent être utilisées, car le récursivité prend beaucoup de temps et de mémoire pour être exécutée.
Exemple d'application : calcul de la factorielle
int fact(int n)
{
if (n>1) return (n * fact(n-1));
else return(1);
}
Utilisation des boucles while, do...while, et for pour le calcul de la somme d'une suite numérique de raison 1, ainsi que par récursivité.
Le programme calcule la somme des N premiers termes d'une suite numérique de raison 1, c'est à dire 1+2+3+...+N.
De plus, une fonction nous donne le temps mis par chaque boucle pour le calcul des sommes (en millisecondes). Néanmoins, pour que le temps mesuré soit significatif, il faut que le nombre choisi pour le calcul de la somme soit supérieur à 500 000 (sur un pentium 200). On remarque que les durées sont assez proches. En utilisant des fonctions spécifiques à votre compilateur, vous pourriez utiliser une unité de temps plus précise, la ms étant la seule normalisée en ANSI C.
Remarque : Ce type de calcul déconseille la récursivité. En effet, la récursivité permettrait de calculer cette somme, mais dans des temps très importants et de plus l'ordinateur indique un message d'erreur (dépassement capacité mémoire) dés que le nombre choisi dépasse 5000.
Programme :
# include<stdio.h>
# include <time.h>
# include <sys\timeb.h>
#define limite_pour_recurs 200
typedef float nombre; /* pour dépasser 32000 */
long heure_en_ms(void)
/*nb de ms dans l'heure (pb si passage à l'heure suivante) */
{
struct timeb t;
ftime(&t);
return((t.time%3600)*1000+t.millitm);
}
nombre add1(nombre n)
{
nombre r=1;
while(n>1)
{
r=r+n--;
}
return(r);
}
nombre add2(nombre n)
{
nombre r=1;
do
{
r+=n--; /*cette écriture devrait accélérer un peu */
}
while(n>1);
return(r);
}
nombre add3(nombre n)
{
nombre r=1,i;
for(i=n;i>1;i--) r=r+i;
return(r);
}
nombre add4(nombre n)
{
nombre r;
if (n>1) r=n+add4(n-1);
else r=1;
return(r);
}
void main(void)
{
nombre nb;
printf("Entrez un nombre entier naturel:");
scanf("%f",& nb);
printf("La somme du nombre %0.0f avec ses antécédents vaut:\n\n",nb);
long heure_actu, heure_avant;
heure_avant = heure_en_ms();
printf("%0.0f pour la boucle while\n",add1(nb));
heure_actu = heure_en_ms();
printf("durée du calcul : %ld ms\n\n",heure_actu-heure_avant);
heure_avant = heure_en_ms();
printf("%0.0f pour la boucle do...while\n",add2(nb));
heure_actu = heure_en_ms();
printf("durée du calcul: %ld ms\n\n",heure_actu-heure_avant);
heure_avant = heure_en_ms();
printf("%0.0f pour la boucle for\n",add3(nb));
heure_actu = heure_en_ms();
printf("durée du calcul: %ld ms\n\n",heure_actu-heure_avant);
if(nb<=limite_pour_recurs)
{
heure_avant = heure_en_ms();
printf("%0.0f pour la récursivité\n",add4(nb));
heure_actu = heure_en_ms();
printf("durée du calcul: %ld ms\n\n",heure_actu-heure_avant);
}
printf("\n\n");
}
