% ***CWD is: /users/formel/dicosmo
% ***TOPLEVEL EXPORT
% ****FULLNAME: ./TD1.tex
% Document Type: LaTeX
% Master File: TP1.tex
% Creator: Roberto DiCosmo [dicosmo@anis]
% Creation Date: Tue Oct  5 19:19:51 1993
\documentstyle[a4]{article}
% *****FULLNAME: /users/formel/dicosmo/Paperi/Miei/Definitions/tdenv.tex
% *****EXPORTBEGS: \input{tdenv}
%
% General \ignore{ . . . } macro.
%
\long\def\ignore#1{\relax}
%
% definition rules environment
%
\newenvironment{rules}{\begin{list}{}{\itemindent.3in\labelwidth0in\labelsep10pt\parskip0pt\partopsep0pt\itemsep0pt\topsep0pt\leftmargin0pt}}{\end{list}}
%
% definition of standard Article environment
%
\def\piripi{\par} % cambiare con \endgraf
\newenvironment{bodydouble}[1]{\endgraf\noindent {\bf #1}\em}{\endgraf}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{notation}[theorem]{Notation}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{rem}[theorem]{}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{exercise}[section]{Exercice}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exmpl}[theorem]{Example}
\newenvironment{example}{\begin{exmpl}\em}{$\qed$\end{exmpl}}
\newenvironment{tinyexample}{\begin{exmpl}\em\twocolscond{\footnotesize\endgraf\smallskip}{\endgraf}}{$\qed$\end{exmpl}}
\newtheorem{defn}[theorem]{Definition}
\newenvironment{definition}{\begin{dfntn}\em}{$\qed$\end{dfntn}}
\newtheorem{lgrthm}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{lgrthm}\em}{\end{lgrthm}}
\newtheorem{xms}[theorem]{Axioms}
\newenvironment{abstract2}[1]{\small\centerline{#1}\begin{list}{}{\rightmargin=\leftmargin} \item}{ \end{list} \normalsize }
\newenvironment{axioms}{\begin{xms}\em}{\end{xms}}
\newenvironment{proof}{\begin{trivlist}\item[]\hspace{\parindent}{\em Proof.}}{$\qed$\end{trivlist}}
%
%\newenvironment{remark}{\begin{trivlist}\item[]{\bf Remark\ \ }}{\end{trivlist}}
%
\def\qed{\proofbox}
\def\proofbox{\begin{picture}(7,7)%
  \put(0,0){\framebox(7,7){}}\end{picture}}
\def\iff{\mbox{$\leftrightarrow$}}
\def\Iff{\mbox{$\Longleftrightarrow$}}
\def\imp{\mbox{$\rightarrow$}}
\def\revimp{\mbox{$\leftarrow$}}
\def\Imp{\mbox{$\Rightarrow$}}
\def\RevImp{\mbox{$\Leftarrow$}}

\begin{document}
% tp1-enonce.tex
\parindent=0pt
MMFAI\par
Cours de programmation
\bigskip
\bigskip

\centerline {TP num\'ero 1}
\centerline {semaine du 13 octobre 1997}
\bigskip
\bigskip
\bigskip

\font\twelvebf=cmbx12
\noindent{\twelvebf Commencer~:} \par

Commencez par vous connecter (login,  passwd, etc.) puis  tapez la commande {\tt
mesg n} pour bosser tranquillement.  Une bonne habitude est  de lire son mail et
le forum chaque jour en se connectant, mais pour gagner du temps en T.P., lancez
directement un \'editeur de texte (joe, vi, {\bf emacs}, etc.).\\

Pour   bien travailler, organisez votre \'ecran   avec une fen\^etre  pas trop large
d\'edi\'ee  \`a l'\'editeur de  texte  (en programmant, on   n'utilise que  rarement des
lignes tr\`es longues), puis une  fen\^etre de terminal plac\'ee \`a  cot\'e ou en dessous
de la premi\`ere.\\

Un programme C est contenu  dans un fichier dont  l'extension est \verb|.c|, par
exemple \verb|toto.c|  \\ Le cycle  de production  pour programmer  en C  est le
suivant:

  \begin{itemize}
    \item \'edition du programme C \verb|toto.c| avec votre \'editeur pr\'ef\'er\'e
    \item compilation \`a l'aide du compilateur C (typiquement \verb|gcc| \ldots{})
\begin{verbatim}

	gcc -o toto toto.c

\end{verbatim}
          (pour les curieux, l'option \verb|-o toto| dit que l'executable s'appellera \verb|toto|
           et non pas \verb|a.out| qui est le nom par d\'efaut\ldots{} faire \verb|man gcc| pour
           en savoir plus)
    \item ex\'ecution du programme: on tape \verb|toto| et on regarde ce qui se passe
  \end{itemize}

Au contraire donc de ce qui se passe en \verb|CamlLight| ou \verb|Maple| vous
ne voyez pas de r\'esultats avant d'avoir compl\'et\'e ce cycle.\\

\begin{exercise}[Hello World]
\end{exercise}
Essayez le cycle de production pr\'ec\'edent sur le programme suivant
(attention, un \verb|;| de perdu et \c{c}a ne marche pas, mais vous pouvez
vous passer des commentaires!):

\begin{verbatim}
/* ceci est un commentaire */
/* voyons comment imprimer */
#include <stdio.h>;

main()
{
	printf("Bonjour\n");
        exit(0);
}
\end{verbatim}

Remarquons que:
\begin{itemize}
  \item les fichiers avec extension \verb|.h| contiennent des d\'efinitions
  \item on peut inclure des d\'efinitions \`a l'aide de \verb|#include|
  \item C dispose des plusieurs types de base et de m\'ecanismes pour d\'efinir des types utilisateur.
        Pour le moment, contentons nous de savoir que \verb|void|, \verb|int|, \verb|float| et \verb|char|
        sont des types valides
  \item une d\'eclaration de fonction est de la forme
\begin{verbatim}
           TYPE_RESULTAT nom(par1, par2)
           type1 par1;
           type2 par2;
           {
                   ...
                   return RESULTAT;
           }
\end{verbatim}
ou bien, si on suit le standard ANSI,
\begin{verbatim}
           TYPE_RESULTAT nom(type1 par1, type2 par2)
           {
                   ...
                   return RESULTAT;
           }
\end{verbatim}
  \item \emph{tout} en C est une fonction qui prend des param\`etres et renvoie un
        r\'esultat, \emph{mais} on si on  veut on peut  ignorer ces r\'esultats (cas
        de printf), et quand ces r\'esultats ne sont jamais significatifs, le type
        du r\'esultat est \verb|void| (cas  de exit).  Faites donc \verb|man exit|
        et \verb|man printf|.
\end{itemize}
\begin{exercise}[Imprimer avec un \emph{format}]
\end{exercise}

Pour imprimer  un valeur en C,  il faut se  servir de la fonction \verb|printf|,
qui attend une cha\^{\i}ne de  caract\`eres (le \emph{format})  et un nombre arbitraire
de valeurs (m\^eme  0 comme   ci-dessus) qui  seront   plac\'es dans le format   aux
positions indiqu\'ees par les \emph{descripteurs  de  format} tels que  \verb|%d|,
\verb|%f| et \verb|%s|. Modifiez votre programme comme suit et testez \`a nouveau.

\begin{verbatim}
#include <stdio.h>;

main()
{
	printf("Bonjour, ceci (%d) est un entier, ceci (%f) est un flottant",300,3.1416);
	printf("et ceci (%s) est une \"string\" (chaine de caracteres)\n","blah blah");
        exit(0);
}
\end{verbatim}

Faite \verb|man printf| pour plus d'information sur les \emph{formats d'impression}.\\
Notez que \verb|\n| indique un fin de ligne (de l'anglais ``newline'').\\
Comment imprime-t-on un caract\`ere \verb|%| ? Et un \verb|\| ?

\begin{exercise}[Lire une valeur]
\end{exercise}

Pour lire une valeur sur l'entr\'ee standard en C, il faut se servir de la fonction
\verb|scanf|, qui  attend une  cha\^{\i}ne de   caract\`eres (le \emph{format})  et  un
nombre arbitraire de valeurs (m\^eme 0 comme ci-dessus)  qui seront plac\'es dans le
format aux  positions indiqu\'ees par  les \emph{descripteurs de format}  tels que
\verb|%d|, \verb|%f| et \verb|%s|. Modifiez votre programme comme suit et testez
\`a nouveau.

\begin{verbatim}
#include <stdio.h>;

main()
{
int i;
float f;
	printf("Bonjour: rentrez un entier et un flottant separes par 
                des espaces ou un retour chariot\n");
        scanf("%d %f ",&i,&f);
	printf("Bonjour, ceci (%d) est un entier, ceci (%f) est un flottant",i,f);
        exit(0);
}
\end{verbatim}

{\bf R\'emarque:} on a d\'eclar\'e une \emph{variable} \verb|i|  de type \verb|int| et
une \verb|f| de  type \verb|float|.\\ Comme  en  C le passage  de param\`etres aux
fonctions se fait par valeur, on est oblig\'e de donner \`a la fonction \verb|scanf|
l'\emph{adresse} m\'emoire o\`u sont physiquement allou\'es f et i.  Cela se fait avec
l'op\'erateur \verb|&|  qui  renvoie un entier    nomm\'e \emph{pointeur}, vu  qu'il
pointe sur une case m\'emoire.\\

\subsection*{Les instructions minimales}

En C vous pouvez utilisez d\'ej\`a les instructions suivantes:
\begin{itemize}
   \item affectation:\\\verb|i=3;|
   \item addition/soustraction de 1:\\\verb|i++;i--;|
   \item comparaison:\\
         \verb|< > <= >= == !=|
   \item arithmetique simple:\\
         \verb|+ * - / %|
   \item s\'equence:\\\verb|{ inst; inst; }|
   \item conditionnelle:\\\verb|if (expr) inst;|\\
         \verb|if (expr) inst; else inst;|\\
         \verb|expr ? inst : inst|
   \item boucle while:\\
         \verb|while (expr) inst;|
   \item boucle for:\\
         \verb|for (start; end; cont) inst;|\\
         \emph{Exemple:}\\
         \verb|for (i = 0, j = 99; i < j; i++, j--) ...;|
   \item retour d'un r\'esultat:\\\verb|return(expr);|
\end{itemize}

Bien, vous avez  maintenant  le minimum  indispensable pour pouvoir  utiliser le
langage C (on en apprendra plus au fur et \`a  mesure de nos n\'ecessit\'es, mais pour
les plus int\'eress\'es,  il serait mieux de se   procurer la r\'ef\'erence  du langage:
\emph{Kernigan,  Ritchie. Le langage  C}.  Vous pouvez  aussi  trouver un r\'esum\'e
succinct dans \verb|http://www.dmi.ens.fr/~beig/systeme/langageC.html|).\\

Passons donc aux choses s\'erieuses \ldots{}
\clearpage

\subsection*{Premiers programmes}
\begin{exercise}[Algorithme d'Euclide b\^ete]
\'Ecrivez un programme C \verb|eubete.c| qui  lit deux entiers $a,~ b$ sur l'entr\'ee
standard    et  calcule et   imprime  $pgcd(a,b)$   en   utilisant seulement  la
soustraction.
\end{exercise}

\begin{exercise}[Algorithme d'Euclide]
En sachant  que  en C les op\'erations   \verb|+,*,/,-| sur les entiers  sont bien
d\'efinies, \'ecrivez  maintenant un programme  C \verb|eu.c|  qui lit deux  entiers
$a,~ b$ sur l'entr\'ee standard et   calcule  et imprime $pgcd(a,b)$ en   utilisant
l'algorithme vu en cours.
\end{exercise}

\begin{exercise}[Algorithme d'Euclide \'etendu]
\'Ecrivez un programme  C qui r\'ealise l'algorithme d'Euclide \'etendu.
\end{exercise}

\begin{exercise}[Les nombres de Fibonacci]   \'Ecrivez  un programme qui  lit   un
entier $n$  et imprime $F_n$, le  $n$-i\`eme  nombre de Fibonacci.\\  Essayez avec
$40$.  Si au but de  quelques  secondes vous n'avez pas  de  r\'esultat, arr\^etez le
programme (tapez Ctrl-C) et r\'efl\'echissez \`a votre algorithme.
\end{exercise}

\begin{exercise}[Exponentiel modulo]   \'Ecrivez  un programme qui  lit trois
entiers $a,~b,~n$  et imprime $(a^b) mod~ n$. Pour cela, il peut \^etre utile
de savoir que C dispose d'op\'erateurs pour travailler sur les bits, comme
\verb|<<| et \verb|>>| qui font du roulement a gauche ou \`a droite de la
representation binaire d'un entier (par ex. \verb|1<<4| = 16).
\end{exercise}


{\bf N'oubliez pas de vous d\'econnecter avant d'abandonner le clavier (voir notes du stage Unix).}

\end{document}
