"Fossies" - the Fresh Open Source Software Archive

Member "hevea-2.35/examples/a.tex" (16 Jan 2021, 4565 Bytes) of package /linux/www/hevea-2.35.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) TeX and LaTeX source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 \documentclass{article}
    2 \usepackage{fullpage}
    3 \usepackage[latin1]{inputenc}
    4 \usepackage{hevea}
    5 \usepackage[french]{babel}
    6 \def\homedir{http://w3.edu.polytechnique.fr/profs/informatique/Luc.Maranget/X.97}
    7 \begin{latexonly}
    8 \gdef\url#1#2{#2}
    9 \gdef\oneurl#1{\url{#1}{{\tt #1}}}
   10 \end{latexonly}
   11 
   12 
   13 \title{TD-5, encore les pointeurs}
   14 \date{}
   15 \author{}
   16 \pagestyle{empty}
   17 \begin{document}
   18 \maketitle
   19 \thispagestyle{empty}
   20 \begin{center}
   21 Ce document est disponible à l'URL
   22 \oneurl{\homedir/TD-5/enonce.html}
   23 \end{center}
   24 
   25 \begin{center}
   26 Programmes  {\em Prenom.Nom.c} à déposer par {\em
   27 ftp} sur {\tt poly} en {\tt /users/profs/maranget/TD-5}.
   28 \end{center}
   29 
   30 
   31 \section{Calculatrice HP}
   32 On se propose de réaliser une petite calculette HP.
   33 
   34 \subsection{Quatre opérations}
   35 Cette première partie s'inspire du cours. On utilisera une pile {\tt
   36 stack}, globale et codée
   37 en machine par une liste d'entiers, voici la définition de {\tt stack} et
   38 le constructeur des listes~:{\small
   39 \begin{verbatim}
   40 typedef struct cell {
   41   int val;
   42   struct cell *next;
   43 } Cell, *Stack;
   44 
   45 Stack stack = NULL;
   46 
   47 Cell *cons(int val,Cell *next)
   48 {
   49   Cell *r;
   50 
   51   r = (Cell *)malloc(sizeof(Cell));
   52   if ( r == NULL) {
   53     fprintf(stderr,"Plus de memoire\n");
   54     exit(-1);
   55   }
   56   r->val = val;
   57   r->next = next;
   58   return r;
   59 }
   60 \end{verbatim}
   61 }
   62 \begin{itemize}
   63 \item Écrire les fonctions de base de manipulation de la pile,
   64 affichage de la pile ({\tt afficher}), empilage ({\tt push}) et
   65 dépilage ({\tt pop}). Voici des signatures possibles~:{\small
   66 \begin{verbatim}
   67 void afficher(void)
   68 int pop(void)
   69 void push(int i)
   70 \end{verbatim}
   71 }
   72 \item Une quelconque des quatre opérations (par exemple $-$) se
   73  réalise ainsi~: dépiler le second argument (par exemple $i_2$), dépiler le
   74 premier argument, (par exemple $i_1$), effectuer l'opération (par
   75  exemple $i_1-i_2$) et empiler le résultat.
   76 
   77 
   78 La calculatrice obéira à un programme contenu dans une chaîne de
   79 caractères et affichera, à chaque étape intermédiaire, le caractère lu
   80 (utiliser \verb+printf+ avec le format \verb+"%c"+)
   81 et l'état de de la pile. Par exemple,
   82 pour le programme {\tt "12-34++"}, on aura~(la pile est affichée du
   83 sommet vers le fond)~:{\small
   84 \begin{verbatim}
   85     []
   86 1 : [1]
   87 2 : [2, 1]
   88 - : [-1]
   89 3 : [3, -1]
   90 4 : [4, 3, -1]
   91 + : [7, -1]
   92 + : [6]
   93 \end{verbatim}
   94 }
   95 Vous aurez donc à lire la chaîne-programme caractère par caractère
   96 (rappelez vous qu'une chaîne est un tableau de caractères) et
   97 à empiler un entier ou à réaliser une opération selon ce que vous avez
   98 lu. Les quatre opérations devront bien entendu utiliser les primitives de
   99 pile, {\tt push} et {\tt pop}. Attention au sens de la soustraction et
  100 de la division.
  101 \end{itemize}
  102 
  103 
  104 \subsection{Opérations avancées sur les piles}
  105 Les vraies calculatrices HP ont des touches spéciales qui permettent
  106 des manipulations de la pile. Les opérations suivantes (qui diffèrent
  107 un peu de celles des calculatrices HP) sont à réaliser sans allouer aucune
  108 cellule de liste.
  109 \begin{itemize}
  110 \item {\em Échanger} les deux éléments du sommet de pile. Cette
  111 opération sera réalisée par le caractère {\tt 's'}. Ainsi, le
  112 programme {\tt "12s-"} donnera le résultat suivant~:{\small
  113 \begin{verbatim}
  114     []
  115 1 : [1]
  116 2 : [2, 1]
  117 s : [1, 2]
  118 - : [1]
  119 \end{verbatim}
  120 }
  121 \item {\em Rotation de la pile vers le haut}~: tous les éléments
  122 montent d'un cran vers le sommet de pile, le sommet de pile se
  123 retrouve en fond de 
  124 pile. Le programme {\tt "4321u"} devra produire~:{\small
  125 \begin{verbatim}
  126     []
  127 4 : [4]
  128 3 : [3, 4]
  129 2 : [2, 3, 4]
  130 1 : [1, 2, 3, 4]
  131 u : [2, 3, 4, 1]
  132 \end{verbatim}
  133 }
  134 \item {\em Rotation de la pile vers le bas}~: c'est l'opération
  135 inverse, tous les éléments
  136 descendent d'un cran, le fond  de pile se retrouve en sommet de pile.
  137 Ainsi, le programme {\tt "4321d"} s'exécute ainsi~:{\small
  138 \begin{verbatim}
  139     []
  140 4 : [4]
  141 3 : [3, 4]
  142 2 : [2, 3, 4]
  143 1 : [1, 2, 3, 4]
  144 d : [4, 1, 2, 3]
  145 \end{verbatim}
  146 }
  147 \end{itemize}
  148 Remarquez que les rotations reviennent, pour la rotation vers le haut,
  149 à mettre la cellule de tête en queue de liste et pour la rotation vers
  150 le bas, à mettre la cellule de queue en tête de liste. Vous aurez
  151 sans doute intérêt à faire de petits dessins pour vous guider.
  152 
  153 
  154 La solution de cet exercice apparaîtra \url{hp.c}{en hp.c}.
  155 
  156 \section{S'il vous reste du temps}
  157 Réaliser une calculatrice PH, dont la structure de contrôle est une
  158 file. La file sera réalisée par une liste (voir la fin du cours).
  159 Une opération se fera en défilant les deux arguments et en enfilant le
  160 résultat.
  161 Vous pouvez aller jusqu'à donner une signification claire aux
  162 rotations et à les programmer.
  163 \end{document}