Cours algorithmes structures iteratives et traduction en c a

Télécharger PDF

Les structures itératives

Plan du cours

Introduction aux structures itératives
Itérations déterministes
Itérations indéterministes
De l'algorithmique au langage C

Itérations déterministes

Exemple : Le calcul de la factorielle

Les itérations déterministes sont des boucles dont le nombre d'exécutions est connu à l'avance. Elles sont souvent implémentées avec des structures "Pour" (for en C).

Itérations indéterministes

Les itérations indéterministes, ou non déterministes, sont des boucles dont le nombre d'exécutions n'est pas connu à l'avance. Elles dépendent généralement d'une condition qui peut varier lors de l'exécution, comme une saisie utilisateur ou un état du programme. Elles sont souvent implémentées avec des structures "Tant que" (while) ou "Répéter jusqu'à" (do/while).

Exemple : Contrôle de saisie

Voici un algorithme illustrant le contrôle de saisie pour s'assurer qu'un utilisateur entre un nombre positif.

Algorithme Somme des N premiers entiers positifs

Cet algorithme calcule la somme des N premiers entiers positifs. Il inclut une validation pour s'assurer que N est un entier positif.

Algorithme Somme
  Variables:
    n, i, S : Entier
  Début
    S <- 0
    Répéter
      Écrire("Saisir un entier positif N : ")
      Lire(n)
    Jusqu'à ce que (n >= 0)
    Pour i allant de 1 à n faire
      S <- S + i
    Fin Pour
    Écrire("La somme des ", n, " premiers entiers est : ", S)
  Fin

Exemple : Plus grand entier dont la factorielle est inférieure à N

Cet algorithme trouve le plus grand entier e tel que e! (factorielle de e) est inférieure ou égale à un entier n donné. C'est une application typique des boucles indéterministes car le nombre d'itérations dépend de la valeur de n.

Algorithme FactorielleMax

Algorithme FactorielleMax
  Variables:
    n, e, fact : Entier
  Début
    Répéter
      Écrire("Saisir un entier positif N : ")
      Lire(n)
    Jusqu'à ce que (n >= 0)
    e <- 0
    fact <- 1
    Tant que (fact * (e + 1) <= n) faire
      e <- e + 1
      fact <- fact * e
    Fin Tant que
    Écrire("Le plus grand entier e tel que e! <= N est : ", e)
  Fin

De l'algorithmique au langage C

Traduire les itérations

La traduction d'un algorithme vers un langage de programmation comme le C implique de choisir les structures de contrôle appropriées. Les boucles "Pour" se traduisent souvent par for, tandis que les boucles "Tant que" et "Répéter jusqu'à" se traduisent par while et do/while.

Instructions de bouclage : `while` et `do/while`

En C, la boucle while exécute un bloc de code tant qu'une condition est vraie, la vérification ayant lieu avant chaque itération. La boucle do/while garantit au moins une exécution du bloc de code, la condition étant vérifiée après la première itération.

Exercice 1

Exercice 1.1 : Calcul du PGCD par soustractions successives

Écrire un algorithme et sa traduction en C pour calculer le Plus Grand Commun Diviseur (PGCD) de deux entiers a et b, en utilisant la méthode des soustractions successives :

Si a > b, alors PGCD(a, b) = PGCD(a-b, b)
Si a < b, alors PGCD(a, b) = PGCD(a, b-a)
Si a = b, alors PGCD(a, b) = a (point d'arrêt de la récursion ou de la boucle)

Code C pour le PGCD

#include <stdio.h>

int main() {
  int a, b;
  printf("Saisissez deux entiers a et b : ");
  scanf("%d %d", &a, &b);
  while (a != b) {
    if (a > b) {
      a = a - b;
    } else {
      b = b - a;
    }
  }
  printf("Le PGCD est : %d\n", a);
  return 0;
}

Exercice 1.2 : Comptage de la fréquence des voyelles

Écrire un algorithme puis un programme C qui compte la fréquence des voyelles (majuscules et minuscules : A, a, E, e, I, i, O, o, U, u) dans un texte saisi caractère par caractère. La saisie se termine par le caractère point ('.'). Le programme affichera le résultat sous la forme suivante :

A, a : [nombre]
E, e : [nombre]
I, i : [nombre]
O, o : [nombre]
U, u : [nombre]

Les voyelles minuscules et majuscules sont comptées ensemble. Utiliser la fonction C getchar() pour lire les caractères un par un.

Foire Aux Questions (FAQ) sur les Structures Itératives

Qu'est-ce qu'une structure itérative en algorithmique ?

Une structure itérative, ou boucle, est un mécanisme qui permet de répéter l'exécution d'un bloc d'instructions plusieurs fois. C'est un concept fondamental pour automatiser des tâches répétitives en programmation.

Quelle est la différence entre une itération déterministe et une itération indéterministe ?

Une itération déterministe est une boucle dont le nombre de répétitions est connu à l'avance (par exemple, "répéter 10 fois"). Une itération indéterministe est une boucle dont le nombre de répétitions n'est pas connu à l'avance et dépend d'une condition qui peut changer pendant l'exécution (par exemple, "répéter tant qu'une condition est vraie").

Comment les structures itératives algorithmiques sont-elles traduites en langage C ?

En langage C, les itérations déterministes sont généralement implémentées à l'aide de la boucle for. Les itérations indéterministes sont traduites par les boucles while (la condition est testée avant l'exécution du corps de la boucle) et do/while (le corps de la boucle est exécuté au moins une fois avant que la condition ne soit testée).