Source Latex
du cours de mathématiques
\documentclass[12pt]{article}
\usepackage{amsfonts}\usepackage{amssymb}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage[utf8]{inputenc}
\usepackage{calc}
\usepackage{enumerate}
\usepackage{pst-all}
\usepackage{multicol}
\usepackage{hyperref}
\hypersetup{
pdfauthor={Yoann Morel},
pdfsubject={Cours mathématiques: algorithmique},
pdftitle={Algorithmique},
pdfkeywords={Mathématiques, algorithmique, programmation,
calculatrice, TI, Casio, python}
}
\hypersetup{
colorlinks = true,
linkcolor = red,
anchorcolor = red,
citecolor = blue,
filecolor = red,
pagecolor = red,
urlcolor = red
}
%\voffset=-2.2cm
% Raccourcis diverses:
\newcommand{\nwc}{\newcommand}
\nwc{\dsp}{\displaystyle}
\nwc{\ct}{\centerline}
\nwc{\bge}{\begin{equation}}\nwc{\ene}{\end{equation}}
\nwc{\bgar}{\begin{array}}\nwc{\enar}{\end{array}}
\nwc{\bgit}{\begin{itemize}}\nwc{\enit}{\end{itemize}}
\nwc{\bgen}{\begin{enumerate}}\nwc{\enen}{\end{enumerate}}
\nwc{\la}{\left\{}\nwc{\ra}{\right\}}
\nwc{\lp}{\left(}\nwc{\rp}{\right)}
\nwc{\lb}{\left[}\nwc{\rb}{\right]}
\nwc{\bgsk}{\bigskip}
\nwc{\vsp}{\vspace{0.1cm}}
\nwc{\vspd}{\vspace{0.2cm}}
\nwc{\vspt}{\vspace{0.3cm}}
\nwc{\vspq}{\vspace{0.4cm}}
\def\N{{\rm I\kern-.1567em N}} % Doppel-N
\def\D{{\rm I\kern-.1567em D}} % Doppel-N
\def\No{\N_0} % Doppel-N unten 0
\def\R{{\rm I\kern-.1567em R}} % Doppel R
\def\C{{\rm C\kern-4.7pt % Doppel C
\vrule height 7.7pt width 0.4pt depth -0.5pt \phantom {.}}}
\def\Q{\mathbb{Q}}
\def\Z{{\sf Z\kern-4.5pt Z}} % Doppel Z
\renewcommand{\Re}{\mathcal{R}e}
\renewcommand{\Im}{\mathcal{I}\!m}
\def\epsi{\varepsilon}
\def\lbd{\lambda}
\def\tht{\theta}
\def\Cf{\mathcal{C}_f}
\nwc{\tm}{\times}
\nwc{\V}[1]{\overrightarrow{#1}}
\nwc{\zb}{\mbox{$0\hspace{-0.67em}\mid$}}
\nwc{\db}{\mbox{$\hspace{0.1em}|\hspace{-0.67em}\mid$}}
\nwc{\ul}[1]{\underline{#1}}
\newcounter{nex}%[section]
\setcounter{nex}{0}
\newenvironment{EX}{%
\stepcounter{nex}
\bgsk{\noindent {\bf Exercice }\arabic{nex}}\hspace{0.2cm}
}{}
\nwc{\bgex}{\begin{EX}}\nwc{\enex}{\end{EX}}
\nwc{\bgfg}{\begin{figure}}\nwc{\enfg}{\end{figure}}
\nwc{\epsx}{\epsfxsize}\nwc{\epsy}{\epsfysize}
\nwc{\bgmp}{\begin{minipage}}\nwc{\enmp}{\end{minipage}}
\nwc{\limcdt}[4]{
$\dsp
\lim_{\bgar{ll}\scriptstyle{#1}\vspace{-0.2cm}\\\scriptstyle{#2}\enar}
{#3}={#4}$
}
\nwc{\tq}{\ \mbox{\bf\Large /}\ }
\headheight=0cm
\textheight=26.cm
\topmargin=-1.8cm
\footskip=0.8cm
\textwidth=18cm
\oddsidemargin=-1cm
\parindent=0.2cm
\voffset=-0.8cm
\setlength{\unitlength}{1cm}
\newcounter{ntheo}
\setcounter{ntheo}{1}
\newlength{\ltheo}
\nwc{\bgth}[1]{
\settowidth{\ltheo}{Théorème \arabic{ntheo}}
\noindent
\paragraph{Théorème}% \arabic{ntheo}}
\hspace{-0.5em}%\hspace{-0.4cm}
\bgmp[t]{\textwidth-\ltheo-0.5em}{\it #1}\enmp
\stepcounter{ntheo}
}
\newcounter{nprop}
\setcounter{nprop}{1}
\newlength{\lprop}
\nwc{\bgprop}[1]{
\settowidth{\lprop}{Propriété \arabic{nprop}}
\noindent
\paragraph{Propriété}% \arabic{ntheo}}
\hspace{-0.5em}%\hspace{-0.4cm}
\bgmp[t]{\textwidth-\lprop-0.5em}{\it #1}\enmp
\stepcounter{nprop}
}
\nwc{\bgcorol}[1]{
\settowidth{\ltheo}{Corollaire \arabic{ntheo}}
\noindent
\paragraph{Corollaire}% \arabic{ntheo}}
\hspace{-0.5em}%\hspace{-0.4cm}
\bgmp[t]{\textwidth-\ltheo-0.5em}{\it #1}\enmp
}
\newcounter{ndef}
\setcounter{ndef}{1}
\newlength{\ldef}
\nwc{\bgdef}[1]{
\settowidth{\ldef}{Définition \arabic{ndef}}
\noindent
\paragraph{Définition}% \arabic{ndef}}
\hspace{-0.5em}%\hspace{-0.4cm}
\bgmp[t]{\textwidth-\ldef-0.5em}{\it #1}\enmp
\stepcounter{ntheo}
}
\nwc{\bgproof}[1]{
\vspq\noindent
\ul{Démonstration:} #1
\hfill$\square$
}
% "Cadre" type Objectifs....
\nwc{\ObjTitle}{Définition\!\!:\ \ }
\newlength{\lgObjTitle}
\newlength{\hgObj}
\newlength{\hgObjTitle}\settoheight{\hgObjTitle}{\ObjTitle}
\newcommand{\Obj}[1]{%
\begin{flushright}%
\settowidth{\lgObjTitle}{\ObjTitle}
\settototalheight{\hgObj}{\phantom{\bgmp{16.4cm}{\bf\emph{\ObjTitle}}#1\enmp}}
\bgmp{17.1cm}
\psline(-1ex,-\hgObj)(-1ex,-1.5\hgObjTitle)(\lgObjTitle,-1.5\hgObjTitle)\par
\bgmp{17.cm}{\bf\emph{\ObjTitle}}#1\enmp
\enmp
\end{flushright}
}
\renewcommand\thesection{\Roman{section}\ \ -}
\renewcommand\thesubsection{\arabic{subsection})}
% Concernant la mise en page des algo:
\definecolor{grayp}{gray}{0.8}
\definecolor{graypc}{gray}{0.65}
\newlength{\ProgIndent}
\setlength{\ProgIndent}{0.6cm}
\nwc{\PI}{\hspace*{\ProgIndent}}
\nwc{\DPI}{\hspace*{2\ProgIndent}}
\nwc{\TPI}{\hspace*{3\ProgIndent}}
\nwc{\QPI}{\hspace*{4\ProgIndent}}
\newlength{\lgcoin}\setlength{\lgcoin}{3ex}
\newlength{\lgshadow}\setlength{\lgshadow}{0.5ex}
\newlength{\phgn}\newlength{\phgnp}
\newlength{\phgng}
\newlength{\plgn}\newlength{\plgng}
\newlength{\phgtq}\newlength{\phgtqg}
\newlength{\plgtq}\newlength{\plgtqg}
\newlength{\plgcoin}\setlength{\plgcoin}{3ex}
\newlength{\plgshadow}\setlength{\plgshadow}{0.5ex}
\nwc{\Prog}[3]{%
%\par\vspd%
\bgmp[t]{#2+0.5cm}%\linewidth}
\hspace*{-0.3pt}\hspace*{-\parindent}\hspace*{-1ex}%
\psframebox[fillstyle=solid,fillcolor=graypc]{
\emph{\textcolor{white}{\!\!#1}}} \\
\vspace*{-0.5ex}\\
\bgmp{#2}
%\setlength{\fboxrule}{0.1pt}
\settototalheight{\phgn}{\phantom{\bgmp{#2}#3\enmp}}
\setlength{\phgn}{\phgn-2ex}
\setlength{\plgn}{\linewidth}
\setlength{\phgtq}{-\phgn}%\addtolength{\hgtq}{-3ex}
\setlength{\phgtqg}{\phgtq}\addtolength{\phgtqg}{-\lgshadow}
\setlength{\plgng}{\plgn}\addtolength{\plgng}{\lgshadow}
\setlength{\plgtq}{\plgn}\addtolength{\plgtq}{-\lgcoin}
\setlength{\plgtqg}{\plgtq}\addtolength{\plgtqg}{\lgshadow}
\setlength{\phgnp}{\phgn}\addtolength{\phgnp}{\lgcoin}
\setlength{\phgng}{\phgnp}\addtolength{\phgng}{\lgshadow}
\pspolygon[linecolor=white,fillstyle=solid,fillcolor=grayp]%
(-1ex,-\phgnp)(-1ex,1ex)(\plgn,1ex)(\plgng,0)%
(\plgng,\phgtqg)(\plgtqg,-\phgng)(-0.5ex,-\phgng)
\pspolygon[linewidth=0.6pt,linecolor=graypc,fillstyle=solid,fillcolor=graypc]%
(\plgn,\phgtq)(\plgtq,\phgtq)(\plgtq,-\phgnp)
\pspolygon[fillstyle=solid,fillcolor=white]%
(-1ex,-\phgnp)(-1ex,1ex)(\plgn,1ex)%
(\plgn,\phgtq)(\plgtq,\phgtq)(\plgtq,-\phgnp)
\par
\bgmp{\linewidth}#3\enmp
\enmp
\enmp
\vspd
}
% et pour les progs casio:
\nwc{\return}{
\psset{unit=1cm,arrowsize=4pt}
\psline{<-}(0,0.1)(0.3,0.1)(0.3,0.25)}
\nwc{\disp}{\pspolygon[fillstyle=solid,fillcolor=black](0,0)(0.2,0)(0.2,0.15)}
% Bandeau en bas de page
\newcommand{\TITLE}{Algorithmique}
\author{Y. Morel}
\date{}
\usepackage{fancyhdr}
\pagestyle{fancyplain}
\setlength{\headheight}{0cm}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.1pt}
\lhead{}\chead{}\rhead{}
\lfoot{Y. Morel - \url{https://xymaths.fr/BTS/}}
\rfoot{\TITLE\ - $BTS$ - \thepage/\pageref{LastPage}}
%\cfoot{\TITLE\ - $T^{\text{\scriptsize{ale}}}S$}
\cfoot{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%\thispagestyle{empty}
%\vspace*{-0.9cm}
\ct{\LARGE \bf \TITLE}
\vspace{-0.6cm}
\section{Généralités}
\vspace{-0.2cm}
\Obj{
Un \emph{algorithme} est une suite finie d'instructions
permettant la résolution systématique d'un problème donné.
}
Un algorithme peut-être utilisé pour\vsp
\bgit
\item[$\bullet$] \ul{décrire} par une suite d'instructions ou de procédures la
marche complète à suivre pour résoudre un problème;
\item[$\bullet$] \ul{automatiser} une tâche complexe;
on sait déjà dans ce cas résoudre le problème posé et on cherche
à tirer parti de moyens informatiques pour effectuer automatiquement
toutes les étapes et tous les calculs intermédiaires
%plus ou moins fastidieux
qui permettent d'aboutir au résultat;
\item[$\bullet$] \ul{chercher} la solution d'un problème;
on ne sait pas a priori résoudre le problème posé
mais on peut tirer parti d'un système informatisé pour explorer
l'ensemble des possibilités, et ainsi tenter de trouver la
solution, ou du moins une bonne approximation de celle-ci.
\enit
\vspt
\bgmp{5.9cm}
\paragraph{Un exemple courant: notice d'utilisation ou mode d'emploi}
%Application d'une huile teck
\ \\
Voici la notice d'utilisation d'une huile teck, imprimée au dos du
flacon d'huile:
\enmp\hspace{\fill}
\bgmp{11.2cm}
\Prog{Mode d'application}{11.2cm}{
1. Vérifier que la surface est bien du teck ou un bois exotique \\
2. Bien agiter avant emploi \\
3. Imprégner le bois généreusement \\
4. 20 minutes après, essuyer l'excédent à l'aide d'un chiffon \\
5. Laisser sécher 6 heures \\
6. Recommencer à partir de l'étape 2 \\
7 Laisser couler quelques gouttes d'eau sur la surface traitée\\
\PI Si les gouttes perlent à la surface, \\
\PI Alors le bois est correctement huilé et imperméabilisé \\
\PI Sinon, recommencer à l'étape 2.
}
\enmp
\Obj{
Un \emph{langage de programmation} est un ensemble d'instructions et
de règles syntaxiques compréhensibles par un système automatisé
(calculatrice, ordinateur, puce électronique,\dots).
\\
Un \emph{programme} est la traduction d'un algorithme dans un langage
de programmation particulier. \
}
\vspd
Il existe de très nombreux langages de programmation tels que,
parmi bien d'autres, Basic, Fortran, Python, C, C++, Matlab, assembleur\dots,
ainsi que ceux implantés dans les calculatrices
(alors dites "programmables"\dots).
Dans la suite les langages des
calculatrices TI et Casio, et le langage Python
qui est un language gratuit, moderne, très efficace,
et dont le code source est
libre ("open source").
Il peut être téléchargé à l'adresse
\emph{http://www.python.org/}.
%\vspd
%Un tableur, tel que celui fourni dans la suite bureautique Open
%Office, téléchargeable gratuitement à l'adresse
%\emph{http://download.openoffice.org/}, peut aussi être utilisé pour
%effectuer automatiquement des calculs.
\section{Premiers exemples: calcul du pgcd de deux nombres}
\subsection{Algorithme d'Euclide:
\normalsize{\emph{Automatisation} du calcul du pgcd de deux
entiers.}}
\bgmp[t]{5.6cm}
Par exemple, pour les entiers \\
$a=462$ et $b=60$:
\enmp
\bgmp[t]{11cm}
\[\bgar{ccccccc}
462
&= &\psovalbox{60}\psline{->}(-.8,-.1)(-1.9,-.6) &\tm &7 &+
&\psovalbox{42}\psline{->}(-.8,-.1)(-3,-.6)
\\[0.3cm]
\psovalbox{60}
&= &\psovalbox{42}\psline{->}(-.8,-.1)(-1.9,-.6) &\tm &1 &+
&\psovalbox{18}\psline{->}(-.8,-.1)(-3,-.6)
\\[0.3cm]
\psovalbox{42}
&= &\psovalbox{18}\psline{->}(-.8,-.1)(-1.9,-.6) &\tm &2 &+
&\psshadowbox{6}\psline{->}(-.8,-.1)(-3,-.6)
\\[0.3cm]
\psovalbox{18}
&= &6 &\tm &3 &+ &\ul{\ul{0}}
\enar\]
\enmp
\noindent
\psset{arrowsize=6pt,xunit=1cm,yunit=0.9cm}
\bgmp{11cm}
\begin{pspicture}(-7.5,-4)(3,5)
\pspolygon(-3,4)(3,4)(3,5.)(-3,5.)
\rput(0,4.5){Entrer les nombres entiers $a$ et $b$}
\psline{->}(0,4)(0,2.8)
\psline(-3,2.8)(3,2.8)(3,1.2)(-3,1.2)(-3,2.8)
\rput(0,2){
\bgmp{5.6cm}
Calculer le reste $r$ de la division\\
euclidienne de $a$ par $b$
\enmp}
\psline{->}(0,1.2)(0,0)
\psline(0,0)(1.5,-1)(0,-2)(-1.5,-1)(0,0)
\rput(0,-1){$r = 0$ ?}
\psline{->}(0,-2)(0,-3.2)\rput(0.5,-2.5){OUI}
\psline(-1,-3.2)(1,-3.2)(1,-4)(-1,-4)(-1,-3.2)
\rput(0,-3.6){$pgcd = b$}
\psline{->}(-1.5,-1)(-5,-1)(-5,-0.5)
\rput(-2,-0.8){NON}
\rput(-5,0){
\bgmp{4cm}
$a$ prend la valeur $b$ \\
$b$ prend la valeur $r$
\enmp
}
\psline(-7.2,0.6)(-3.2,0.6)(-3.2,-0.5)(-7.2,-0.5)(-7.2,0.6)
\psline{->}(-5,0.6)(-5,2)(-3,2)
\end{pspicture}
\enmp\hspace*{\fill}
\bgmp{6cm}\vspace{-1.5cm}
\Prog{Algorithme}{6cm}{
Lire \texttt{a} et \texttt{b} \\
(reste division de \texttt{a} par \texttt{b}) $\to$ \texttt{r} \\
\texttt{Tant que r$\not=$0 faire}\\
\PI\texttt{b$\to$a} \\
\PI\texttt{r$\to$b} \\
(reste division de \texttt{a} par \texttt{b}) $\to$ \texttt{r} \\
\texttt{Fin tant que}
}
\enmp
\bgex
\bgen[a)]
\item Déterminer le pgcd de $a=140$ et $b=42$.
\item Déterminer le pgcd de $a=1500$ et $b=2310$.
\enen
\enex
\subsection{Algorithme des différences}
Cet autre algorithme permettant de calculer le pgcd de deux
nombres $a$ et $b$ s'exécute de la manière suivante:
on soustrait le plus petit des deux nombres $a$ et $b$ au plus grand,
on obtient le nombre positif $d$;
puis on recommence de même avec les deux plus petits nombres parmi les
trois précédents, et ainsi de suite...
\vsp
Par exemple, avec $a=14$ et $b=6$:
\hspace{0.5cm}
\bgmp[t]{5cm}\vspace{-0.7cm}
$14-6=8$ \vsp\\
$8-6=2$ \vsp\\
$6-2=4$ \vsp\\
$4-2=\psshadowbox{2}$ \vsp\\
$2-2=\ul{\ul{0}}$
\enmp
\vspd
\Prog{Algorithme}{3.5cm}{
\texttt{Lire a}\\
\texttt{Lire b}\\
\newline
\texttt{a-b$\to$d}\\
\texttt{Afficher d}\\
\newline
\texttt{Tant que d$\not=$0}\\
\PI\texttt{Si d<b}\\
\DPI\texttt{b$\to$a}\\
\DPI\texttt{d$\to$b}\\
\PI\texttt{Sinon}\\
\DPI\texttt{d$\to$a}\\
\PI\texttt{Fin Si}\\
\PI\texttt{a-b$\to$d}\\
\PI\texttt{Afficher d}\\
\texttt{Fin Tant que}
}\hfill
\Prog{Programme TI}{2.8cm}{
\texttt{Prompt A}\\
\texttt{Prompt B}\\
\newline
\texttt{A-B$\to$D}\\
\texttt{Disp D}\\
\newline
\texttt{Wile D$\not=$0}\\
\texttt{If D<B}\\
\texttt{Then}\\
\texttt{B$\to$A}\\
\texttt{D$\to$B}\\
\texttt{Else}\\
\texttt{D$\to$A}\\
\texttt{End}\\
\texttt{A-B$\to$D}\\
\texttt{Disp D}\\
\texttt{End}
}\hfill
\Prog{Programme Casio}{3.3cm}{
\texttt{"A="?$\to$A\return}\\
\texttt{"B="?$\to$B\return}\\
\newline
\texttt{A-B$\to$D\disp}\\
\newline
\texttt{Wile D$\not=$0\return}\\
\texttt{If D<B\return}\\
\texttt{Then B$\to$A\return}\\
\texttt{D$\to$B\return}\\
\texttt{Else D$\to$A\return}\\
\texttt{IfEnd\return}\\
\texttt{A-B$\to$D\return}\\
\texttt{D\return}\\
\texttt{WhileEnd}
}\hfill
\Prog{Programme Python}{4cm}{
\texttt{a=input("a ?")}\\
\texttt{b=input("b ?")}\\
\newline
\texttt{d=a-b}\\
\texttt{print d}\\
\newline
\texttt{while d !=0:}\\
\PI\texttt{if d<b:}\\
\DPI\texttt{a=b}\\
\DPI\texttt{b=d}\\
\PI\texttt{else:}\\
\DPI\texttt{a=d}\\
\PI\texttt{d=a-b}\\
\PI\texttt{print d}
}
\section{Lire, exécuter et comprendre un algorithme}
\vspace{-0.3cm}
\bgex
\bgmp{7cm}
Ci-contre est donné un algorithme:
\bgen
\item Qu'affiche cet algorithme lorsque l'utilisateur entre
le nombre $3$ ?
le nombre $-12,7$ ?
\item A quoi sert cet algorithme ?
\enen
\enmp\hfill%\hspace{0.3cm}
\bgmp{10cm}\vspace{-0.5cm}
\Prog{Algorithme}{10cm}{
\texttt{Entrer $x$}\\
\texttt{Si $x<0$}\\
\PI\texttt{Affecter à $x$ la valeur $-x$}\\
\texttt{Fin Si}\\
\texttt{Afficher la valeur $x$}
}
\enmp
\enex
\bgex
\bgmp{7cm}
Ci-contre est donné un algorithme:
\vspq
\bgen
\item Qu'affiche cet algorithme lorsque l'utilisateur entre
successivement les nombres
\[12\,;\ 3\,;\ 18\,;\ 11\,;\ 0\]
\item A quoi sert cet algorithme ?
\enen
\vspace{1.2cm}
\enmp\hfill%\hspace{0.3cm}
\bgmp{10cm}\vspace{-0.6cm}
\Prog{Algorithme}{10cm}{
\texttt{x=1}\\
\texttt{S=0}\\
\texttt{i=0}\\
\texttt{Tant que $x\not=0$}\\
\PI\texttt{Demander à l'utilisateur d'entrer un nombre}\\
\PI\texttt{Lire $x$}\\
\PI\texttt{Affecter à $S$ la valeur $S+x$}\\
\PI\texttt{Affecter à $i$ la valeur $i+1$}\\
\texttt{Fin Tant que}\\
\texttt{Afficher la valeur $S/i$}
}
\enmp
\enex
\vspace{-1cm}
\section{Variables}
\vspace{-0.8cm}
\bgdef{
On appelle \emph{variable} tout emplacement de la mémoire dans lequel
une information peut-être stockée.
Une variable est constituée de :
\begin{itemize}
\item un nom qui permet à l'ordinateur de la localiser dans sa
mémoire (en général une lettre:
\texttt{A}, \texttt{B}, \dots, \texttt{X}, \dots)
\item une valeur: l'information (souvent un nombre) qu'elle
contient.
\end{itemize}
}
La valeur d'une variable peut changer au cours de l'exécution de
l'algorithme.
\begin{minipage}{\textwidth-3.4cm}
Une affectation consiste à attribuer une valeur à une variable, ou à
en modifier la valeur.
%Cette valeur peut être le résultat d'un calcul.
La valeur {\it val} est attrivuée à la variable nommée \texttt{var}.
\end{minipage}
\hspace{\fill}
\begin{tabular}{|l|}\hline
\ \\
{\it val}$\to$\texttt{var}\hspace*{1cm}\\
\ \\\hline
\end{tabular}
\section{Structures dans les algorithmes}
\vspace{-0.2cm}
\subsection{Boucles itératives}
\vspace{-1.2cm}
\begin{minipage}[c]{\textwidth-7cm}
Une boucle permet de répéter un ensemble d'instructions un nombre fixé
de fois.
\end{minipage}\hspace{\fill}
\begin{tabular}[c]{|p{6cm}|}\hline
\texttt{Pour {\it variable} de {\it début} à {\it Fin}}\\
\hspace*{0.4cm}{\it instructions 1}\\
\hspace*{0.4cm}{\it instructions 2}\\
\hspace*{0.4cm}{\it \dots}\\
\texttt{Fin Pour} \\\hline
\end{tabular}
\bgex
\bgen[a)]
\item Ecrire un algorithme qui calcule et affiche la suite des carrés
des nombres entiers de 1 à 10.
\item Modifier cet algorithme pour qu'il calcule et affiche la somme
des carrés des entiers de 1~à~10.
\enen
\enex
\subsection{Tests et instructions conditionnelles}
\begin{minipage}[b]{\textwidth-5.cm}
Un test est une comparaison entre la valeur d'une variable et une
valeur donnée, ou entre les valeurs de deux variables.
\vspd
Un test a deux résultats possibles:
$0$ (faux), ou $1$ (vrai).
%\vspd
Dans une structure conditionnelle,
les instructions ne sont effectuées que \emph{si} le test indiqué est vrai.
\end{minipage}\hspace{\fill}
\begin{tabular}[b]{|p{4cm}|}\hline
\texttt{Si} {\it test}\\
\hspace*{0.4cm}{\it instructions 1}\\
\hspace*{0.4cm}{\it instructions 2}\\
\hspace*{0.4cm}{\it \dots}\\
\texttt{Fin Si} \\\hline
\end{tabular}
\bgex
Ecrire un algorithme qui demande un nombre à l'utilisateur et affiche
en résultat si le nombre est positif ou négatif.
\enex
\subsection{Boucles conditionnelles}
\vspace{-0.8cm}
\begin{minipage}[b]{\textwidth-5cm}
Une boucle conditionnelle permet de répéter une série d'instructions
sans connaître a priori le nombre d'itérations.
La boucle est répété \emph{tant que} le test indiqué est vrai.
\end{minipage}\hspace{\fill}
\begin{tabular}[b]{|p{4cm}|}\hline
\texttt{Tant que} {\it test} \\
\hspace*{0.4cm}{\it instructions 1}\\
\hspace*{0.4cm}{\it instructions 2}\\
\hspace*{0.4cm}{\it \dots}\\
\texttt{Fin Tant que} \\\hline
\end{tabular}
\bgex
Ecrire un algorithme qui demande un nombre entier à l'utilisateur
et compte à rebours jusqu'à~$0$.
\enex
%\vspace{1cm}
%\clearpage
\section{Jeu du nombre mystérieux}
Ce jeu se joue à deux personnes de la manière suivante.
Un des deux joueurs choisit un nombre entier au hasard compris entre 1
et 100.
Le but du deuxième joueur est de trouver ce nombre.
Pour cela il propose un nombre au premier joueur qui lui
fournit une des trois réponses:
\bgit
\item \emph{Gagné}, si le nombre proposé est le bon;
\item \emph{Trop grand}, si le nombre proposé est plus grand que le
nombre mystérieux;
\item \emph{Trop petit}, si le nombre proposé est plus petit que le
nombre mystérieux;
\enit
Si le nombre proposé n'est pas le bon, le deuxième joueur propose un
autre nombre, et le jeu se poursuit jusqu'à ce qu'il trouve le nombre
exact.
Le but du jeu est de trouver le nombre mystérieux avec le moins de
tentatives possible.
\vspd\noindent
\subsection{L'ordinateur fait deviner}
Le programme dans lequel l'ordinateur est le joueur choisissant
un nombre au hasard compris entre 1 et 100, et l'utilisateur est le
joueur qui doit trouver ce nombre.
Le programme doit aussi afficher le nombre de tentatives utilisées.
\vspd
Lire attentivement l'algorithme suivant (ou un des programmes),
bien suivre et comprendre la succession d'instruction,
et indiquer le rôle de chacune des variables
\texttt{M},
\texttt{C},
\texttt{N}.
\vspd\par
\Prog{Algorithme}{9.6cm}{
\texttt{M prend une valeur aléatoire entre $0$ et $100$}\\
\texttt{C prend la valeur 1}\\
\texttt{Afficher "Entrer un nombre"}\\
\texttt{Lire N}\\
\texttt{Tant que N$\not=$M}\\
\PI\texttt{Si N<M alors}\\
\DPI\texttt{Afficher "Trop petit"}\\
\PI\texttt{Sinon}\\
\DPI\texttt{Afficher "Trop grand"}\\
\PI\texttt{Fin Si}\\
\PI\texttt{C prend la valeur C+1}\\
\PI\texttt{Afficher "Entrer un nombre"}\\
\PI\texttt{Lire N}\\
\texttt{Fin Tant que}\\
\texttt{Afficher "Gagne en",C," coups"}
}
\Prog{Programme TI}{6.2cm}{
\texttt{randInt(0,100)$\to$M}\\
\texttt{1$\to$C}\\
\texttt{Prompt N}\\
\texttt{while N$\not=$M}\\
\texttt{if N<M}\\
\texttt{Then}\\
\texttt{Disp "Trop petit"}\\
\texttt{Else}\\
\texttt{Disp "Trop grand"}\\
\texttt{End}\\
\texttt{C+1$\to$C}\\
\texttt{Prompt N}\\
\texttt{End}\\
\texttt{Disp "Gagne en",C," coups"}
}
\vspq
\Prog{Programme Casio}{4.9cm}{
\texttt{Int(100$\tm$Ran\#+1)$\to$M}\!\return\\
\texttt{1$\to$C}\return\\
\texttt{"N="?$\to$N}\return\\
\texttt{While N$\not=$M}\return\\
\texttt{If N<M}\return\\
\texttt{Then "Trop petit"}\return\\
\texttt{Else "Trop grand"}\return\\
\texttt{IfEnd}\return\\
\texttt{C+1$\to$C\return}\\
\texttt{"N="?$\to$N}\return\\
\texttt{WhileEnd}\return\\
\texttt{"Gagne"}\return\\
\texttt{"Nombre de coups="}\return\\
\texttt{C\disp}
}
\Prog{Programme Python}{7.3cm}{
\texttt{import random}\\
\newline
\texttt{M=random.randint(0,100)}\\
\texttt{N=input('Entrer un nombre: ')}\\
\newline
\texttt{C=0}\\
\texttt{while N!=M:}\\
\PI\texttt{N=input('Entrer un nombre: ')}\\
\PI\texttt{if N<M:}\\
\DPI\texttt{print "Trop petit"}\\
\PI\texttt{else}\\
\DPI\texttt{print "Trop grand"}\\
\PI\texttt{C=C+1}\\
\texttt{print "Gagne en ",C," coups"}
}
\vspace{-0.4cm}
\subsection{L'ordinateur doit deviner}
Ecrire un programme pour ce jeu avec les rôles inversés:
vous pensez à un nombre entier compris entre 1 et 100,
et l'ordinateur doit le trouver.
Essayer de trouver une stratégie pour que l'ordinateur trouve ce
nombre avec le moins de coups possible.
\vspace{-0.4cm}
%\clearpage
\section{Corrigés: Algorithmes et programmes des exercices}
\setcounter{nex}{3}
\vspace{-0.6cm}
\bgex
\bgen[a)]
\item Affichage des 10 premiers entiers:\vspd\par
\Prog{Algorithme}{3.6cm}{
\texttt{Pour I de 1 à 10}\\
\PI\texttt{Afficher I*I}\\
\texttt{Fin Pour}
}\hfill
\Prog{Programme TI}{3.2cm}{
\texttt{For (I,1,10)}\\
\texttt{Disp I*I}\\
\texttt{End}
}\hfill
\Prog{Programme Casio}{3.55cm}{
\texttt{For 1$\to$I To 10\!\return}\\
\texttt{I*I\disp}\\
\texttt{Next}
}\hfill
\hspace{\fill}
\Prog{Programme Python}{4.8cm}{
\texttt{for i in range(1,11):}\\
\hspace*{\ProgIndent}\texttt{print i*i}
}
\vspace{-0.56cm}
\item Calcul de la somme des carrés des 10 premiers entiers:\vspd\par
\Prog{Algorithme}{3.6cm}{
\texttt{0$\to$S}\\
\texttt{Pour I de 1 à 10}\\
\PI\texttt{S+I*I$\to$S}\\
\texttt{Fin Pour}\\
\texttt{Afficher S}
}\hfill
\Prog{Programme TI}{3.2cm}{
\texttt{0$\to$S}\\
\texttt{For (I,1,10)}\\
\texttt{S+I*I$\to$S}\\
\texttt{End}\\
\texttt{Disp S}
}\hfill
\Prog{Programme Casio}{3.55cm}{
\texttt{0$\to$S}\\
\texttt{For 1$\to$I To 10\!\return}\\
\texttt{S+I*I$\to$S\return}\\
\texttt{Next}\\
\texttt{S\disp}
}\hfill
\hspace{\fill}
\Prog{Programme Python}{4.8cm}{
\texttt{S=0}\\
\texttt{for i in range(1,11)\!:}\\
\hspace*{\ProgIndent}\texttt{print i*i}\\
\texttt{print S}
}
\enen
\enex
\vspace{-0.8cm}
\bgex Test: nombre positif ? \vspd\par
\Prog{Algorithme}{4.6cm}{
\texttt{Lire A}\\
\texttt{Si A>0}\\
\hspace*{0.2cm}\texttt{Afficher "A positif"}\\
\texttt{Sinon}\\
\hspace*{0.2cm}\texttt{Afficher "A négatif"}\\
\texttt{Fin Si}
}
%\hspace{\fill}
\Prog{Programme TI}{3.5cm}{
\texttt{Prompt A}\\
\texttt{If A$\geq$0}\\
\texttt{Then}\\
\texttt{Disp "A positif"}\\
\texttt{Else}\\
\texttt{Disp "A négatif"}\\
\texttt{End}
}\hfill
\Prog{Programme Casio}{4.cm}{
\texttt{"A="?$\to$A\return}\\
\texttt{If A$>$0\return}\\
\texttt{Then "A positif"\!\return}\\
\texttt{Else "A négatif"\!\return}\\
\texttt{IfEnd}
}%\hfill
\Prog{Programme Python}{4.cm}{
\texttt{A=input("A ?")}\\
\texttt{if A$\geq$0:}\\
\hspace*{0.2cm}\texttt{print "A positif"}\\
\texttt{else:}\\
\hspace*{0.2cm}\texttt{print "A negatif"}\\
}
\enex
\vspace{-0.9cm}
\bgex Compte à rebours: \vspd\\
\Prog{Algorithme}{3.5cm}{
\texttt{Lire N}\\
\texttt{Tant que N>0}\\
\hspace*{\ProgIndent}\texttt{N-1$\to$N}\\
\hspace*{\ProgIndent}\texttt{Afficher "N"}\\
\texttt{Fin Tant que}
}\hfill
\Prog{Programme TI}{3.5cm}{
\texttt{Prompt N}\\
\texttt{While N>0}\\
\texttt{N-1$\to$N}\\
\texttt{Disp N}\\
\texttt{End}
}\hfill
\Prog{Programme Casio}{3.5cm}{
\texttt{"N="?$\to$N}\\
\texttt{While N>1\return}\\
\texttt{N-1$\to$N\disp}\\
\texttt{WhileEnd}\\
}\hfill
\Prog{Programme Python}{3.5cm}{
\texttt{N=input("N ?")}\\
\texttt{While N>0:}\\
\hspace*{\ProgIndent}\texttt{N=N-1}\\
\hspace*{\ProgIndent}\texttt{print N}
}
\enex
\vspace{-0.8cm}
%\clearpage
\section{Exercices}
\vspace{-0.4cm}
%\bgex
%Qu'affiche l'algorithme des différences pour le calcul du pgcd
%lorsqu'on lui fournit les valeurs
%$a=42$ et $b=140$.
%
%Modifier l'algorithme afin que l'utilisateur puisse entrer des valeurs
%quelconques pour $a$ et $b$.
%\enex
\bgex
Ecrire un algorithme qui demande trois nombres $a$, $b$ et $c$ à
l'utilisateur et calcule et affiche les solutions de l'équation du
second degré $ax^2+bx+c=0$.
\enex
\bgex
Ecrire un algorithme qui demande à l'utilisateur un nombre entier $n$
et calcule et affiche la somme
$1+2+3+\dots+n$.
\enex
%\bgex
%Soit la suite $(u_n)$ définie par
%$u_0=1$ et, pour tout entier $n$,
%$u_{n+1}=2u_n+3$.
%
%\bgen[a)]
%\item Ecrire un algorithme qui permet de calculer et d'afficher les
% $N$ premiers termes de la suite $(u_n)$.
%\item Ecrire un algorithme qui permet de calculer et d'afficher la
% somme $S$ des $N$ premiers termes de la suite $(u_n)$,
% \quad$S=u_0+u_1+u_2+\dots+u_{N-1}$.
%\enen
%\enex
\bgex
Ecrire un algorithme qui demande à l'utilisateur un nombre entier $n$,
et calcule et affiche~$n!$.
\emph{(Rappel: pour un nombre entier $n$,
$n!=n\tm(n-1)\tm(n-2)\tm(n-3)\tm \dots \tm 2\tm1$.\ )
}
\enex
\bgex
Ecrire un algorithme qui demande un nombre entier à l'utilisateur et
indique si ce nombre est pair ou impair.
\vsp\noindent
\emph{(Indication: Un entier est pair, par exemple, si en lui
retranchant suffisamment de fois 2 on arrive~à~0.)
}
\enex
\bgex {\it Distributeur de billets}
Ecrire un algorithme qui demande un montant $N$ en euros (un nombre
entier) et qui calcule et affiche
le nombre minimal de billets de 20, 10 et de 5 euros
à fournir pour faire le montant~$N$.
{\it(Afficher éventuellement un message d'erreur si le montant $N$ demandé
n'est pas un multiple de 5).}
\enex
%\bgex
%Ecrire un algorithme qui demande une suite de nombres à l'utilisateur,
%et qui calcule et affiche la moyenne de ces nombres.
%
%On pourra écrire ce programme de la manière suivante:
%on demande à l'utilisateur les valeurs les unes après les autre, et on
%considère que la saisie est terminée lorsque l'utilisateur entre la
%valeur $0$.
%\enex
%\bgex
%TVI et Dichotomie\dots
%\enex
\bgex
La population d'une ville augmente de 4\,\% par an.
Ecrire un algorithme qui permet de déterminer le nombre d'années au
bout desquelles la population aura doublé.
\enex
\noindent
\bgmp{10cm}
\bgex
On considère la fonction $f$ définie par $f(x)=\dfrac{x^2+2}{x+3}$.
Soit de plus $\tau(h)=\dfrac{f(3+h)-f(3)}{h}$.
Ecrire un algorithme qui cacule les valeurs du tableau ci-contre.
\enex
\enmp\quad
\bgmp{8cm}
\begin{tabular}{|c|c|c|*{4}{p{1cm}|}}\hline
$h$ & \ 1\ & $0,1$ & $0,01$ & $0,001$ & $0,0001$ &\ \dots\ \\\hline
\rule[-0.4cm]{0.cm}{1.cm}$\tau(h)$ &&&&&& \\\hline
\end{tabular}
\enmp
\label{LastPage}
\end{document}
Télécharger le fichier source 
