Corrigés des exercices

Introduction à l’algorithmique

Exercice 1

Sans tenir compte du signe, quelle est la valeur maximale d’un nombre codé en 32 bits ? Indiquez comment calculer facilement cette valeur et exprimez le résultat en décimal et en hexadécimal.

Réponse

La taille maximale d’un nombre sur 32 bits est de 2³²-1. Ce résultat est facilement trouvable comme ceci :

1*2³¹ + 1*2³⁰ + 1*2²⁹ + … + 1*2⁰

Ce qui donne 4294967295, le nombre maximal pouvant être stocké dans 32 bits, et non 4294967296 (2³²).

Sa représentation hexadécimale est FFFFFFFF.

Exercice 2

Convertissez le nombre décimal 123456789 en binaire et en hexadécimal.

Réponse

123456789/2 = 61728394, reste 1

61728394/2 = 30864197, reste 0

30864197/2 =15432098, reste 1

15432098/2 = 7716049, reste 0

7716049/2 = 3858024, reste 1

3858024/2 = 1929012, reste 0

1929012/2 = 964506, reste 0

964506/2 = 482253, reste 0

482253/2 = 241126, reste 1

241126/2 =120563, reste 0

120563/2 = 60281, reste 1

60281/2 = 30140, reste 1

30140/2 =15070, reste 0

15070/2 = 7535, reste 0

7535/2 = 3767, reste 1

3767/2 = 1883, reste 1

1883/2 = 941, reste 1

941/2 = 470, reste 1

470/2 = 235, reste 0

235/2 = 117, reste 1

117/2 = 58, reste 1

58/2 = 29, reste 0

29/2 = 14, reste 1

14/2 = 7, reste 0

7/2 = 3, reste 1

3/2 = 1 reste 1

1/2 = 0 reste 1

Le résultat est donc 111 0101 1011 1100 1101 0001 0101 soit 31 bits.

En hexadécimal...

Les variables et opérateurs

Exercice 1

Quelles seront les valeurs des variables A et B après chaque ligne du code suivant ?

VAR 
  A,B :entiers 
DEBUT 
  A←3 
  B←A+3 
  A←4 
FIN
 

Réponse

  A←3
 

A=3, B n’a pas encore de valeur.

  B←A+3
 

A=3, B=6

  A←4
 

A=4, B=6

Exercice 2

Quelles seront les valeurs des variables A, B et C après chaque ligne du code suivant ?

VAR 
  A,B,C :entiers 
DEBUT 
  A←3 
  B←5 
  C←A+B 
  A←2 
  C←B-A 
FIN
 

Réponse

  A←3
 

A=3, B et C n’ont pes encore de valeur.

  B←5
 

A=3, B=5, C n’a pas encore de valeur.

  C←A+B
 

A=3, B=5, C=8

  A←2
 

A=2, B=3, C=8

  C←B-A
 

A=2, B=3, C=1

Exercice 3

Quelles seront les valeurs des variables A et B après chaque ligne du code suivant ?

VAR 
  A,B :entiers 
DEBUT 
  A←3 
  B←A+4 
  A←A+2 
  B←A-4 
FIN
 

Réponse

  A←3
 

A=3, B n’a pas encore de valeur.

  B←A+4
 

A=3, B=7

  A←A+2
 

A=5, B=7

  B←A-4
 

A=5, B=1

Exercice 4

Quelles seront les valeurs des variables A, B et C après chaque ligne du code suivant ?

VAR 
  A,B,C:entiers 
DEBUT 
  A←5 
 ...

Tests et logique booléenne

Exercice 1

Écrire, avec des comparaisons, un algorithme qui affiche l’état de l’eau (glace, liquide, vapeur) en fonction de sa température.

Réponse

PROGRAMME ETAT 
VAR 
  T :numérique 
DEBUT 
  Afficher "Température ?" 
  Saisir T 
  Si T<=0 Alors 
    Afficher "C'est de la glace" 
  SinonSi T<100 Alors 
    Afficher "C'est liquide" 
  Sinon 
    Afficher "C'est de la vapeur" 
  FinSi
 

Exercice 2

Écrire le même algorithme, mais en utilisant deux variables booléennes pour vérifier l’état de l’eau, sans comparaisons dans les SI.

Réponse

PROGRAMME ETAT 
VAR 
  T :numérique 
  A,B :booléens 
DEBUT 
  Afficher "Température ?" 
  Saisir T 
  A←T<=0 
  B←T<100 
  Si A Alors 
    Afficher "C'est de la glace" 
  SinonSi B Alors 
    Afficher "C'est liquide" 
  Sinon 
    Afficher "C'est de la vapeur" 
  FinSi
 

Exercice 3

Écrire un algorithme qui détermine la catégorie sportive d’un utilisateur en fonction de son âge :

Écrire le programme C# associé.

Réponse

La meilleure solution est d’utiliser une structure Si - SinonSi.

PROGRAMME CATEGORIE 
VAR 
  age :entier 
DEBUT 
  Afficher "Age ?" 
  Saisir age 
  Si age>=12 Alors 
    Afficher "cadet" 
  SinonSi age>=10 Alors 
    Afficher "minime" 
  SinonSi age>=8 Alors 
    Afficher "pupille" 
  SinonSi age>=6 Alors 
    Afficher "poussin" 
  FinSi 
FIN
 

Ce qui donne en C# :

class chap3_categorie 
{ 
    static void Main(string[] args) 
    { ...

Les boucles

Exercice 1

Quel algorithme permet d’afficher les nombres pairs entre 1 et 10 ? Fournissez le programme C# associé. Que faut-il simplement faire pour afficher ensuite les nombres impairs ?

Réponse

Programme Pair 
VAR 
    a:entier 
            
DEBUT 
    a←1 
    Tant Que a<=10 
      Si a MOD 2 = 0 Alors 
        Afficher a 
      FinSi 
      a←a+1 
    FinTantQue 
FIN
 

Ceci se traduit en C# comme ceci :

class chap4_pair 
{ 
    static void Main(string[] args) 
    { 
        int a = 1; 
 
        while (a <= 10) 
        { 
            if (a % 2 == 0)  
                System.Console.WriteLine(a); 
            a++; 
        } 
    } 
}
 

Ce qui donne :

> chap4_pair.exe 
2 
4 
6 
8 
10
 

Il suffit de modifier le test du Si pour sortir les nombres impairs :

if(a % 2 == 1) 
   System.Console.WriteLine(a);
 

Le même algorithme avec une boucle Pour :

DEBUT 
    a←1 
    Pour a De 1 à 10 Faire 
      Si a MOD 2 = 0 Alors 
        Afficher a 
      FinSi 
    FinPour 
FIN
 

Exercice 2

Écrire un algorithme qui calcule la somme de tous les chiffres de 1 à n. Utilisez tout d’abord Tant Que, puis Pour. Fournissez les deux possibilités dans le même programme C#.

Réponse

On doit calculer 1+2+3+…+n, donc effectuer n passages dans la boucle. Avec un Tant que, on peut décrémenter n et stopper la boucle lorsque sa valeur atteint zéro.

Programme multiplication 
VAR 
    n:entier 
    resultat:entier 
DEBUT 
    n←10 
  
    Tant Que n<>0 
      resultat←resultat+n ...

Les tableaux et structures

Exercice 1

Donnez un algorithme (et le code C# associé) qui permet de trouver le nombre d’occurrences d’une valeur entière dans un tableau de 20 valeurs.

Réponse

On définit un tableau de 20 valeurs, une variable qui contient la valeur recherchée et une dernière qui contient le nombre d’occurrences. On balaie tout le tableau et à chaque fois que la valeur est trouvée on incrémente le compteur.

PROGRAMME OCCUR 
VAR 
  tab:tableau[1..20]←{10,17,14,3,12,2,15,9,7,10,14,13,8,1,9,19,17,
14,2, 5} d'entiers 
  valeur,nb_occurences,i:entiers 
DEBUT 
  valeur←14 
  nb_occurences←0 
  Pour i de 1 à 20 Faire 
    Si tab[i]=valeur Alors 
      nb_occurences←nb_occurences+1 
    FinSi 
  FinPour 
  Afficher nb_occurences 
FIN
 

Le code C# ressemble à ceci :

class chap5_occur 
{ 
    static void Main(string[] args) 
    { 
        int[] tab = { 10, 17, 14, 3, 12, 2, 15, 9, 7, 10, 14, 13, 
            8, 1, 9, 19, 17, 14, 2, 5 }; 
        int valeur, nb_occurences, i; 
 
        valeur = 14; 
        nb_occurences = 0; 
 
        for (i = 0; i < 20; i++) 
        { 
            if (tab[i] == valeur) nb_occurences++; 
        } 
        System.Console.WriteLine(nb_occurences); 
    } 
}
 

Ce qui logiquement donne à l’exécution :

> chap5_occur.exe 
3
 

Exercice 2

Comment déterminer si un tableau d’entiers à une dimension est trié par ordre croissant ? Donnez l’algorithme et le code C#.

Réponse

Pour déterminer si un tableau est trié, il faut balayer l’ensemble du tableau et comparer chaque élément avec le suivant (ou le précédent, selon qu’on démarre au premier ou au second élément). Un drapeau, de type booléen et initialisé à VRAI, prendra la valeur FAUX...

Les sous-programmes

Exercice 1

Créer la fonction « absolu » qui prend une valeur numérique en paramètre et qui retourne sa valeur absolue.

Réponse

La fonction prend et retourne un entier :

Fonction absolu(n :numérique) :entier 
Début 
  Si n<0 Alors 
    n← -n 
  FinSi 
  Retourne n 
FinFonc
 

La fonction va s’utiliser dans un programme comme ceci :

PROGRAMME TESTABS 
DEBUT 
 Afficher absolu(-2) 
FIN
 

Exercice 2

Reprendre l’algorithme de l’exercice 4 du chapitre Les tableaux et structures et le transformer en fonction qui trie le tableau passé en paramètre. Un second paramètre, de type booléen, sera vrai pour croissant, faux pour décroissant. Pour simplifier la tâche, on introduit la fonction prédéfinie taille() qui retourne le nombre d’éléments du tableau.

Le tri par ordre décroissant a-t-il un intérêt ?

Réponse

L’adaptation est relativement simple :

Fonction tri(t[] :tableau d'entiers, croissant :booléen) 
VAR 
  i,mem,pos,Cpt:entiers 
DEBUT 
  Cpt←taille(t) 
  Pour i de 1 à Cpt faire 
    mem←t[i] 
    pos←i-1 
    Tant Que pos>=0 ET ( (croissant ET t[pos]>mem) 
    OU ( NON  croissant ET t[pos]<mem ) ) 
      t[pos+1]←t[pos] ...

Les fichiers

Exercice 1

Écrire l’algorithme COPIE qui copie un fichier dans un autre, octet par octet. Donner le programme C# associé.

Réponse

On ouvre un fichier en lecture, l’autre en écriture, et on utilise la fonction EcrireOctet pour y écrire les octets lus dans le premier.

Programme COPIE 
Var 
  Fic,fic2 :fichiers binaires 
  octet :entier 
Début 
  Ouvrir nom dans fic en lecture 
  Ouvrir nom2 dans fic2 en écriture 
  Tant que NON EOF(fic) Faire 
    octet←LireOctet(fic) 
    EcrireOctet(fic2,octet) 
  FinTantQue 
  Fermer fic 
  Fermer fic2 
Fin
 

On peut se passer de la variable octet :

    EcrireOctet(fic2,LireOctet(fic))
 

Le résultat en C# est le suivant :

using System.IO; 
 
class chap7_copy 
{ 
    static void Main(string[] args) 
    { 
        FileStream FicSRC = null; 
        FileStream FicDST = null; 
 
        int o = 0; 
        try 
        { 
            // Ouvre le fichier  
            FicSRC = new FileStream("SRC.jpg", FileMode.Open, 
               FileAccess.Read); 
            FicDST = new FileStream("DST.jpg", FileMode.Open, 
               FileAccess.Write); 
 
            while ((o = FicSRC.ReadByte()) != -1) 
                FicDST.WriteByte((byte)o); 
 
            FicSRC.Close(); 
            FicDST.Close(); 
 
        } 
        catch (IOException e) 
        { 
            System.Console.WriteLine("IOException:"); 
        } 
    } 
}
 

Exercice 2

Cet exercice représente une synthèse des précédents chapitres et propose de développer un utilitaire complet, pratique...

Notions avancées

Exercice 1

Écrire l’algorithme permettant de parcourir et d’afficher les n éléments d’un tableau d’entiers, partant de son premier élément, avec un pointeur.

Réponse

Il suffit de récupérer l’adresse du premier élément dans un pointeur. En incrémentant ce pointeur, on se déplace dans le tableau.

PROGRAMME TabPointeur 
Var 
  Tab:tableau[1..10] d'entiers 
  n←1:entier 
  pTab: pointeur sur entier 
Début 
  pTab←adresse de Tab[1] 
  Tant Que n<=10 Faire 
    Afficher *pTab  
    pTab←pTab+1 
  FinTanQue 
Fin
 

Exercice 2

Créer une structure de liste chaînée circulaire et y placer trois éléments. Créer la fonction permettant de retourner le premier élément, puis celle permettant de parcourir tous les éléments.

Réponse

Un élément d’une liste circulaire est identique à ceux vus dans le chapitre, sauf qu’on y ajoute un drapeau, un booléen qu’on va appeler premier. Il prend la valeur VRAI si l’élément est le premier, FAUX sinon.

TYPES 
  // Un élément de liste chaînée 
Structure element 
    valeur:entier ...

Une approche de l’objet

Exercice 1

Écrire une classe permettant de décrire un livre et de positionner les valeurs associées. Donner un exemple d’utilisation en C#.

Réponse

Tout d’abord on liste les propriétés, ou attributs, d’un livre :

Ensuite, on liste les méthodes permettant de gérer ces propriétés :

Un constructeur par défaut va initialiser les variables, un autre prendra toutes les valeurs. On implémente ensuite quelques méthodes.

Une définition peut être :

Classe livre 
  attributs 
    titre : chaine 
    auteur: chaine 
    editeur: chaine 
    nbpages : entier 
    annee : entier 
  methodes: 
    Constructeur livre() 
    Début 
      this.titre←"" 
      this.auteur←"" 
      this.editeur←"" 
      this.nbpages←0 
      this.annee←1900 
    Fin 
    Constructeur livre(titre:chaine,  auteur:chaine, 
    editeur:chaine, nbpages:entier, annee:entier) 
    Début 
      this.titre←titre 
      this.auteur←auteur 
      this.editeur←editeur 
      this.nbpages←nbpages 
      this.annee←annee 
    Fin 
  
    Fonction settittle(titre:chaine) 
    Début 
      this.titre←titre 
    FinFonc 
  
    Fonction setauteur(auteur:chaine) 
    Début 
      this.auteur←auteur 
    FinFonc 
  
    Fonction setediteur(editeur:chaine) 
   ...