Séance d'exercices 12, Programmation I
Sciences et Technologies du Vivant, Semestre 1

Les exercices marqués d'une étoile (*) sont des exercices supplémentaires de révision.

Exercice 1 - Polygones

Dans cet exercice, vous allez écrire un programme vous permettant de caractériser et de représenter graphiquement un polygone.

  1. Un point dans le plan est défini simplement par ses coordonées $x$ et $y$. Déclarez une structure Point contenant deux entiers, afin de représenter un point et ses deux coordonnées.
  2. En informatique, une couleur se définit en général par les trois niveaux de rouge, vert et bleu qui la compose. Le niveau de chaque couleur fondamentale est représenté par un réel entre 0 et 1. Par exemple, la couleur blanche vaut (1,1,1), rouge (1,0,0). Écrivez une structure Couleur permettant de représenter une couleur.
  3. Déclarez finalement une structure Polygone. Un polygone peut être représenté par un ensemble de points et une couleur (vous vous servirez des structures Point et Couleur, définies plus haut). Un champ ferme servira à indiquer si le polygone est fermé ou s'il s'agit d'une ligne polygonale (ouvert).
  4. Implémentez une fonction affiche_polygone, dont le but sera d'afficher un polygone dans une fenêtre graphique. Pour cela, vous utiliserez la libraire swindow dont vous vous êtes déjà servi lors de la leçon 10. La fonction prendra un pointeur sur SimpleWindow ainsi qu'un pointeur sur Polygone: 
    void affiche_polygone(SimpleWindow * window, Polygone * polygone)

    Comme ici window est un pointeur, il faudra utiliser l'opérateur -> plutôt que . pour accéder aux champs et fonctions de window. Par exemple, window->draw_line(...). On rappelle que SimpleWindow est une classe C++, et les classes sont une extension des structures. Comme pour les structures, on utilise donc -> sur un pointeur au lieu du point (.).

  5. Déclarez un Polygone nommé losange dans main et remplissez ses champs, de manière à ce qu'il représente correctement un losange. Initialisez ensuite une nouvelle fenêtre. Vous pouvez utiliser le code suivant à cet usage: 
      SimpleWindow window("Polygone", 300, 300);
  window.map();
  window.color(1, 1, 1);
  window.fill();

    Dessinez ensuite le losange dans la fenêtre à l'aide de la commande affiche_polygone et faites afficher la fenêtre. Ajoutez le code suivant à la fin de votre programme 

      cout << "Appuyez sur une touche pour continuer..." << endl;
  char a = getchar();

    afin que le programme ne se termine pas tout de suite et que vous ayez le temps d'admirer votre losange.

Exercice 2 - Structures et pointeurs

On souhaite réaliser des statistiques sur les résultats d'un sondage, pour lequel plusieurs personnes ont été interrogées sur 3 questions notées $A$, $B$ et $C$. Pour chacune des personnes, on connaît son âge, son genre (M ou F), son salaire annuel, et sa réponse (oui ou non) à chacune des trois questions.

On décide de représenter la réponse d'une personne par la structure suivante: 

  struct Reponse {
    int age;
    char genre;
    float salaire;
    bool repA, repB, repC;
  };

  1. Déclarez un tableau de pointeurs sur Reponse de 20 éléments dans la fonction main. Vous le nommerez sondage. L'intérêt de déclarer un tableau de pointeurs sur Reponse (Reponse *sondage[20]) plutôt qu'un tableau de Reponses (Reponse sondage[20]) est que seuls les éléments utilisés du tableau occupent de la mémoire.

    Ceci est illustré par la figure 1.

    Figure 1: Comparaison de l'espace mémoire occupé par un tableau de structures (Reponse sondage[20]) et un tableau de pointeurs sur structure (Reponse *sondage[20]). Remarques: Les adresses mémoire utilisées sont arbitraires. La taille en mémoire d'une structure Reponse est plus grande que celle représentée sur la figure. Elle a été volontairement réduite afin de rendre la figure plus lisible. La même chose est valable pour les pointeurs.
    \begin{figure}\begin{center} \subfigure[\normalsize Un tableau de \texttt{Repon... ...ures utilis\'ees.]{% \input{fig/memoire2.pstex_t}} \end{center} \end{figure}

    Comme le tableau contient des pointeurs, il faut éviter de lire ou d'écrire dans un pointeur qui n'a pas été initialisé. Pour ce faire, on attribue généralement la valeur NULL (constante valant 0) à un pointeur, pour indiquer qu'il ne pointe sur 'rien'. Après avoir déclaré votre tableau sondage, ajoutez le code suivant pour indiquer que le tableau est pour l'instant vide. 

    for (int i=0; i<20; i++)
  sondage[i] = NULL;

  2. Écrivez une fonction alloue_reponse qui alloue et initalise une structure Reponse. La fonction aura l'en-tête suivante: 
    Reponse *alloue_reponse(int age, char genre, float salaire, 
                        bool repA, bool repB, bool repC)

    Elle devra allouer de la mémoire pour une nouvelle structure Reponse et initialiser ses champs aux valeurs passées en paramètres. Finalement, elle retournera un pointeur sur la nouvelle structure.

    Après avoir écrit votre fonction, entrez le code suivant dans main pour initialiser un tableau avec 5 réponses au sondage: 

    	sondage[0] = alloue_reponse(35, 'M', 65000, false, true, false);
	sondage[1] = alloue_reponse(40, 'F', 80000, false, true, true);
	sondage[2] = alloue_reponse(52, 'F', 110000, true, true, true);
	sondage[3] = alloue_reponse(22, 'M', 50000, false, false, false);
	sondage[4] = alloue_reponse(45, 'F', 95000, true, true, false);

  3. Écrivez la fonction reponse_plus_haut_salaire qui prend en paramètre un tableau de Reponse * ainsi que sa taille, et qui renvoie la réponse (une valeur de type Reponse *) de la personne ayant le plus haut salaire. Prenez soin d'éviter les segmentation fault en ne lisant que les pointeurs qui ont été correctement initialisés.

    Pour cette fonction et les suivantes, vérifiez votre code en utilisant votre fonction dans main, en lui passant le tableau sondage en paramètre, et en affichant le résultat.

  4. Écrivez la fonction nombre_hommes_plus_de_trente_ans_AB qui renvoie le nombre d'hommes de plus de trente ans qui ont répondu oui aux questions $A$ et $B$, et non à la question $C$. La fonction prend en paramètre un tableau de Reponse * ainsi que sa taille.

  5. Écrivez la fonction moyenne_salaires_femmes_moins_de_100000, qui renvoie le salaire moyen des femmes qui gagnent moins de 100'000 CHF. Si aucune femme ne gagne moins de 100'000 CHF, la fonction devra renvoyer $-1$. La fonction prend en paramètre un tableau de Reponse * ainsi que sa taille.

  6. Écrivez la fonction au_moins_une_reponse_oui, qui renvoie true si au moins une personne a répondu oui aux trois questions, false sinon. La fonction prend en paramètre un tableau de Reponse * ainsi que sa taille.

  7. Comme les variables de type Reponse * pointées par les éléments du tableau ont été allouées dynamiquement (avec new), il faut les supprimer manuellement. Faites-le à l'aide de l'instruction delete, à la fin du programme.

Exercice 3 - Tableaux à 3 dimensions

Dans cet exercice, vous allez réaliser une petite animation dans une fenêtre graphique, à l'aide de la librairie swindow. Une animation n'est rien d'autre qu'une successions d'images (voir Figure 2) Une image, en informatique, est un ensemble de points (nommés pixels) répartis dans le plan. Pour stocker une animation, vous avez donc besoin d'un tableau à 3 dimensions: 2 dimensions pour les axes $x$ et $y$ du plan et une troisième dimension pour le temps.

Figure 2: Une animation est une sucession d'images dans le temps, donc un tableau d'images, ou un tableau à 3 dimensions de pixels.
\begin{figure}\begin{center} % \input{fig/anim.pstex_t} \end{center} \end{figure}

  1. Écrivez un nouveau programme animation.cpp dans lequel vous déclarerez la librairie swindow. Déclarez trois constantes globales (i.e. en dehors de main) représentant la taille de votre animation: 
          const int largeur = 200;
      const int hauteur = 100;
      const int duree   = 100;

    Au début de votre programme, déclarez un tableau de booléens à 3 dimensions que vous appellerez animation. La taille du tableau sera de $largeur\times hauteur\times duree$.

  2. Écrivez la fonction efface en utilisant l'en-tête ci-dessous: 
          void efface(bool tab[largeur][hauteur][duree])

    Comme son nom l'indique, la fonction devra effacer le tableau passé en paramètre, c.-à-d. mettre toutes ses valeurs à false.

  3. Écrivez une fonction dessine_rectangle qui prend comme paramètres un tableau à 3 dimensions de booléens (bool t[largeur][hauteur][duree]), la taille du rectangle selon les deux axes, sa position aussi selon les deux axes et le numero de l'image dans laquelle il faut dessiner le rectangle (i.e. le temps). Dessiner le rectangle revient à mettre à true les pixels du tableau où se trouve le rectangle. Prenez garde à ne pas excéder les dimensions du tableau. Une bonne méthode est d'utiliser l'opérateur modulo (%). De cette manière, si le rectangle disparaît dans un bord de l'image, il réapparaitra de l'autre côté.

  4. Écrivez une fonction anime_rectangle. Vous lui passerez le tableau de booléens de l'animation, les coordonnées de départ du rectangle, sa taille ainsi que sa vitesse (voir Figure 3). Cette fonction devra dessiner le carré dans toutes les images de l'animation. Elle utilisera la valeur des vitesses pour savoir comment déplacer le rectangle dans les images. La vitesse sera donnée en nombre de pixels à parcourir entre deux images successives.

    Figure 3: $x$ et $y$ sont la position du rectangle, $t_x$ et $t_y$, sa taille et $\hat{v}$ sa vitesse que l'on peut décomposer en deux composantes $v_x$ et $v_y$.
    \begin{figure}\begin{center} % \input{fig/rectangle.pstex_t} \end{center} \end{figure}

  5. Implémentez une fonction que vous appellerez affiche_animation. Cette fonction recevra un pointeur sur SimpleWindow ainsi que le tableau de l'animation. Le but de cette fonction est d'afficher l'animation dans la fenêtre graphique. Elle devra fonctionner comme suit:

  6. Implémentez finalement la fonction main de manière à tester votre animation.

Exercice 4 - Entrelacement de tableaux (*)

Écrivez une fonction prenant pour paramètres deux tableaux d'entiers A et B de même taille, ainsi que leur taille. Cette fonction devra allouer un nouveau tableau R dont la taille sera le double de celle de A ou B. R sera ensuite construit de la façon suivante:

La fonction renverra un pointeur sur le premier élément de R.

Exercice 5 - Éléments en indice (*)

Écrivez une fonction prenant un tableau T d'entiers et sa taille en paramètres. La fonction devra allouer un nouveau tableau T2. T2 sera construit de la façon suivante: Les éléments de T d'indice pair seront placés dans T2 à l'indice donné par l'élément suivant de T. Exemple:

La fonction devra renvoyer un pointeur sur le premier élément de T2. On remarquera que la taille de T doit être paire. Si ce n'est pas le cas, la fonction devra renvoyer le pointeur 0 pour indiquer une erreur.

Exemple:

T:
4 2 8 0 7 1
T2:
8 7 4

Exercice 6 - Damier (*)

Écrivez une fonction 

    void damier(int largeur, int hauteur)

qui affiche un damier: 

    damier(4, 3);

    # # # #
     # # #
    # # # #
     # # #
    # # # #

dont la taille (largeur et hauteur) sera passée en paramètre.

Exercice 7 - Triangle creux (*)

Écrivez une fonction qui affiche un triangle isocèle ``creux'' à l'aide des caractères /, \ et _: 

        /\
       /  \
      /    \
     /      \
    /________\

Le nombre de lignes sera passé en paramètre. Attention, pour afficher le caractère \, il faut le répéter deux fois. Exemple: cout << "\\"; affiche un seul |.

Exercice 8 - Somme et produit des chiffres (*)

Écrivez un programme qui trouve les 20 premiers nombres entiers dont la somme des chiffres est égale au produit de ces mêmes chiffres. Vous devez trouver 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 22, 123, 132, 213, 231, 312, 321, 1124, 1142 et 1214.

Exercice 9 - Suite de Fibonacci (*)

La suite de Fibonnacci est la solution au problème suivant: supposons qu'un couple (un mâle, une femelle) de lapins immatures soit mis dans un champ, que la maturité sexuelle du lapin soit atteinte après un mois qui est aussi la durée de gestation, que chaque portée comporte toujours un mâle et une femelle et que les lapins ne meurent pas. Combien y aura-t-il de lapins dans le champ après un an?

Écrivez un programme qui affiche les premiers termes de la suite de Fibonacci. Cette suite qu'on notera $F$ peut se calculer ainsi: $F(0) = 1$, $F(1) = 1$, et $F(i)=F(i-1)+F(i-2)$. Essayez les deux possiblités: avec et sans récursivité. Quelle version est la plus rapide ?

Vérifiez que le quotient de 2 nombres consécutifs de la suite de Fibonacci converge vers le nombre d'or $\frac{1+\sqrt{5}}{2}$, qui vaut environ 1.61803...

Exercice 10 - Nombres parfaits et nombres amicaux (*)

Un nombre parfait est un nombre (entier) égal à la somme de ses diviseurs (ce nombre n'étant pas compté parmi ses diviseurs; en revanche 1 en fait partie). Par exemple, $6 = 3 + 2 + 1$ et $28 = 1 + 2 + 4 + 7 + 14$ sont parfaits. Écrivez un programme qui trouve les premiers nombres parfaits.

Deux nombres entiers $n$ et $m$ sont dits amicaux si la somme des diviseurs de $n$ ($n$ non compris) vaut $m$ et la somme des diviseurs de $m$ ($m$ non compris) vaut $n$. Par exemple, 220 et 284 sont amicaux. Écrivez une fonction ayant deux paramètres $n$ et $m$, et qui renvoie true si $n$ et $m$ sont amicaux, false sinon.

Exercice 11 - Nombres romains (*)

Écrivez une fonction récursive permettant de traduire un nombre romain en un nombre sous la forme décimale. Il n'est pas nécessaire de vérifier la valididé du nombre romain. Pour rappel:

romain décimal
M 1000
D 500
C 100
L 50
X 10
V 5
I 1

Exercice 12 - Recherche par dichotomie (*)

Dans cet exercice, vous allez apprendre à rechercher une valeur dans un tableau trié. La manière la plus simple est de parcourir le tableau jusqu'à ce qu'on trouve la valeur recherchée ou que l'on parvienne à la fin du tableau. Cependant, cette méthode n'est pas optimale. La recherche par dichotomie permet de faire bien plus rapide, en moyenne.

Soit un tableau $T$ de $n$ entiers triés. Supposons qu'on recherche l'entier $r\in\mathbb{N}$. Une recherche par dichotomie s'effectue comme suit:

  1. on divise le tableau en deux parties (de 0 à $\lfloor \frac{n}{2} \rfloor$ et de $\lfloor \frac{n}{2} \rfloor + 1$ à $n-1$);
  2. on compare l'élément recherché ($r$) avec le milieu de l'intervalle ( $T[\lfloor \frac{n}{2} \rfloor]$);
  3. si $r = T[\lfloor \frac{n}{2} \rfloor]$, la recherche est terminée. Si $r < T[\lfloor \frac{n}{2} \rfloor]$, il faut effectuer une recherche dans l'intervalle de gauche, sinon dans l'intervalle de droite;
  4. on répète les points 1 à 3 jusqu'à ce que la valeur ait été trouvée ou que la taille de l'intervalle de recherche soit nulle.

Implémentez une fonction effectuant une recherche par dichotomie dans un tableau d'entiers triés. La fonction devra être récursive et prendra comme arguments un tableau d'entiers ainsi que sa longueur et la valeur recherchée. La fonction retournera l'indice du tableau où la valeur a été trouvée, ou $-1$ si la valeur n'apparaît pas dans le tableau.

Retour