\documentclass[10pt,a4paper,twoside]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{amsfonts,amsmath,amsthm,amssymb,url,stmaryrd}
\usepackage{xspace}
\usepackage{fullpage}
\usepackage{color}
\usepackage{fancyhdr}

%\usepackage[correction]{ennonce}
\usepackage{ennonce}
\usepackage{fancyvrb}
\usepackage{color}
\usepackage{ifthen}
\usepackage{calc}

% Small verbatim + tabs
% \makeatletter
% \newenvironment{code}{\small\obeylines\@verbatimtab}{\endtrivlist}
% \makeatother

\fvset{numbersep=5pt}
\fvset{obeytabs=true}
\fvset{resetmargins=true}
\fvset{baselinestretch=0.7}
\fvset{frame=single}
\fvset{numbers=left}

\renewcommand{\FancyVerbFormatLine}[1]{\small{#1}}

\def\C{\textsf{C}\xspace}


\fancyhf{}
\renewcommand{\headrulewidth}{0mm}\renewcommand{\footrulewidth}{0mm}
\fancyhead[L]{\footnotesize DEUG MIAS 2\ieme~année}
\fancyhead[R]{\footnotesize Cours de programmation 2001--2002}
\fancyfoot[C]{\footnotesize M.\textsc{Quinson}}

\begin{document}
\pagestyle{fancy}
\begin{center}
  {\Large \ifennonce{Examen}\ifcorrection{Correction de l'examen de} de TD n°1}

  \bigskip\parbox{120mm}{%
    La durée de l'examen est de 30 minutes, les notes de cours et de
    TD sont autorisées. La notation prendra en compte la présentation
    et la clarté des explications (programmes commentés, dessins
    explicatifs, \dots). L'examen sera noté sur 10 points et
    le barème est donné uniquement à titre indicatif. Il pourra être
    modifié lors de la notation finale.
  }\bigskip
\end{center}

\begin{Question}\textbf{(2 points)}
  Expliquez le fonctionnement, l'utilité et les éventuels désavantages de
  la construction \texttt{typedef} en \C.
\end{Question}
\begin{Reponse}
  \texttt{typedef} sert à créer un nouveau type, qui est l'alias d'un
  autre type. En général, on l'utilise pour donner un nom clair et simple à
  un type composé que l'on va utiliser couramment par la suite. Ainsi, si
  le programme manipule des pointeurs sur des chaines, il est plus simple
  d'écrire :

  \texttt{typedef char **p\_string;}

  \noindent puis d'utiliser le type \texttt{p\_string} pour les manipuler
  que d'utiliser directement \texttt{char **}. On a moins de chance
  d'oublier une étoile, et on voit plus imédiatement ce que \texttt{p\_string}
  représente. 

  \medskip
  L'usage de cette construction est simplement : 

  typedef $<$définition du type crée$>$ $<$nom du type créé$>$

  \noindent Dans la suite du programme, il est équivalent d'écrire le nom
  du type construit, ou sa définition.
  
  \medskip 
  
  La construction en elle même n'a pas vraiment de désavantage, mais il
  vaut mieux suivre certaines règles d'usage. \texttt{typedef} doit servir
  à améliorer la lisibilité du programme, et définir des noms de types
  illisibles ou ne reflètant pas leur définition est une mauvaise idée. De
  même, une trop grande abondance de types définis, peut dérouter le
  lecteur en le forçant à lire ailleurs dans le programme ce qu'ils
  définissent.
\end{Reponse}

\begin{Question}\textbf{(2 points)}
  Comment faire pour qu'une fonction renvoie deux résultats ? \'Ecrivez une
  fonction prenant deux nombres en argument et «renvoyant» leur somme ainsi
  que leur produit.
\end{Question}
\begin{Reponse}
  Il y a deux méthodes : la première consiste à définir une nouvelle
  structure contenant les différentes variables à renvoyer, puis à renvoyer
  une telle structure. Exemple :
  \begin{Verbatim}
    typedef struct s_resultat {
      int somme;
      int produit;
    } resultat_t;
    resultat_t somprod(int a, int b) {
      resultat_t res;
      res.somme   = a+b;
      res.produit = a*b;
      return res;
    }
  \end{Verbatim}

  La seconde méthode (celle qu'on a utilisé pour la fonction \texttt{push}
  en TD) consiste à passer en argument de la fonction des pointeurs sur
  l'emplacement où il faut écrire les résultats. Exemple :
  \begin{Verbatim}
    void somprod(/* Vrais arguments */ int a, int b, 
                 /* Résultats */       int *somme, int *prod) {
      *somme   = a+b;
      *produit = a*b;
    }
  \end{Verbatim}
  La première solution est un peu plus lourde, puisqu'elle impose de la
  définition puis l'usage d'une structure dédiée, mais les deux sont valides.
\end{Reponse}


\begin{Question}\textbf{(3 points)}
  Écrire une fonction \C prenant un nombre $n$ en argument et renvoyant le
  $n^\text{ième}$ terme de la suite de Fibonnaci. On rappelle que cette
  suite est défini par :
  \[\left\{
      \begin{array}{l}
        U_{n+2} = U_n + U_{n+1}\\
        U_0 = 0\\
        U_1 = 1
      \end{array}
    \right.\]
\end{Question}
\begin{Reponse}
  Version récursive (Temps
  $>2^{\frac n 2}$) :
  \begin{Verbatim}
    int fibonacci (int n) {
      if (n < 0) {
        return 0;
      } else if (n == 1) {
        return 1;
      } else {
        return fibonacci(n-1) + fibonacci(n-2);
      }
    }
  \end{Verbatim}
  La même chose, plus court :
  \begin{Verbatim}
    int fibonacci (int n) {
      return (n<0 ? 0 : (n==1 ? 1 : fibonacci(n-1) + fibonacci(n-2)));
    }
  \end{Verbatim}
  Version itérative optimisée sans recalculer deux fois la même chose (Temps :
  $O(n)$) :
  \begin{Verbatim}
    int fibonacci (int n) {
      int j; /* va parcourir 2->n */
      int uj;  /* un   */
      int uj1; /* un-1 */
      int uj2; /* un-2 */

      /* On élimine les cas triviaux */
      if (n < 0) {
        return 1;
      } else if (n == 1) {
        return 0;
      }
      /* initialisation */
      uj1=0;   uj2=1;
      
      /* boucle principale */
      for (j=2 ; j<=n ; j++) {
        uj=uj1 + uj2;
        uj2=uj1;
        uj1=uj;
      }

      /* La boucle est finie. Maintenant, j=n */
      return uj;
    }
  \end{Verbatim}
\end{Reponse}

\begin{Question}\textbf{(3 points)}
  On rappelle les définitions suivantes:
  \begin{Verbatim}
     typedef struct s_maillon *p_maillon_t;
     typedef p_maillon_t       liste_t;
     typedef liste_t          *p_liste_t;
     typedef struct s_maillon {
       int         valeur;
       p_maillon_t suivant;
     } maillon_t;
   \end{Verbatim}
  Écrire une fonction \C qui prend une liste et un nombre en argument et
  renvoie la valeur «1» si ce nombre fait partie de la liste ou «0» s'il
  n'en fait pas partie.
  \begin{Verbatim}
     liste_t nil() {
       return NULL;
     }
     int car(liste_t liste) {
       if(liste == nil()) {
         printf("Une liste vide n'a pas de car !!\n");
         exit(1);
       }
       return liste->valeur;
     }
     liste_t cdr(liste_t liste) {
       if(liste == nil()) {
         return(nil());
       }
       return liste->suivant;
     }
   \end{Verbatim}
\end{Question}
\begin{Reponse}
  \begin{Verbatim}
    int find_int (liste_t liste, int val) {
      if (liste == NULL) { /* C'est le cas d'arrêt de la récursion */
        return 0;
      } else if (val == liste.valeur) { /* trouvé ! */
        return 1;
      } else { /* pas encore trouvé, mais on a pas parcouru toute la liste => on continue */
        return find_int(liste->suivant,val);
      }
    }
   \end{Verbatim}
   Version volontairement peu lisible et compacte :
   \begin{Verbatim}
     int find_int (liste_t liste, int val) {
       return (liste ? (liste->valeur - val ? find_int(liste->suivant,val) : 1) : 0);
     }
   \end{Verbatim}
\end{Reponse}
\end{document}

