@ccueil Colles

Source LaTeX icone Cours-Exercices-Algorithmique-Programmation



Fichier
Type: Cours
File type: Latex, tex (source)
Télécharger le document pdf compilé pdficon
Description
Algorithmique et programmation: exemples et exercices - Algorithmes et programmes sur calculatrice TI, Casio et en langage Python
Niveau
Seconde
Table des matières
  • Algorithmique et programmation: exemples et exercices
  • Suites d'instructions
  • Boucles itératives
  • Tests et instructions conditionnelles
  • Boucles conditionnelles
  • Jeu du nombre mystérieux
Mots clé
algorithme, algorithmique, programmation, calculatrice, TI, Casio, Python, structures fondamentales, boucle, test, exemples, exercices
Voir aussi:

Documentation sur LaTeX
pdficon
Source LaTex icone
Télécharger le fichier source pdficon

\documentclass[12pt]{article}
\usepackage{amsfonts}\usepackage{amssymb}
\usepackage[french]{babel}
\usepackage{amsmath}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{epsf}
\usepackage{calc}
\usepackage{enumerate}
\usepackage{array}
\usepackage{pst-all}
\usepackage{pstricks-add}

\usepackage{hyperref}
\hypersetup{
    pdfauthor={Yoann Morel},
    pdfsubject={Cours mathématiques: algorithmique},
    pdftitle={Algorithmique},
    pdfkeywords={Mathématiques, algorithmique, programmation, 
      lycée, 2nde, seconde, 1S, 
      première, S, 1èreS, 1ère S, terminale, terminale S, 
      python}
}
\hypersetup{
    colorlinks = true,
    linkcolor = red,
    anchorcolor = red,
    citecolor = blue,
    filecolor = red,
    urlcolor = red
}
\voffset=-1.cm
% 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}}
\def\D{{\rm I\kern-.1567em D}}
\def\No{\N_0}
\def\R{{\rm I\kern-.1567em R}}
\def\C{{\rm C\kern-4.7pt 
\vrule height 7.7pt width 0.4pt depth -0.5pt \phantom {.}}}
\def\Q{\mathbb{Q}}
\def\Z{{\sf Z\kern-4.5pt Z}}


\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{\bgmp}{\begin{minipage}}\nwc{\enmp}{\end{minipage}}

\headheight=0cm
\textheight=26.2cm
\topmargin=-1.8cm
\footskip=0.8cm
\textwidth=18.6cm
\oddsidemargin=-1.3cm
\parindent=0.2cm

% 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%
}

% 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 et programmation}
\author{Y. Morel}
\date{}

\usepackage{fancyhdr}
\usepackage{lastpage}

\pagestyle{fancyplain}
\setlength{\headheight}{0cm}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.1pt}
\lhead{}\chead{}\rhead{}

\lfoot{Y. Morel - \url{xymaths.free.fr}}
\rfoot{\TITLE\ - \thepage/\pageref{LastPage}}
\cfoot{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\vspace*{-0.4cm}


\ct{\LARGE \bf \TITLE}
\vspace{0.6cm}

{\bf\large\ul{Suites d'instruction}}
\bgex Moyenne de trois nombres: 

\Prog{Algorithme}{5cm}{
  \texttt{Lire A, B et C}\\
  \texttt{A+B+C$\to$S}\\
  \texttt{S/3$\to$M}\\
  \texttt{Afficher M}
}
%\hspace{\fill}
\Prog{Programme TI}{3.5cm}{
  \texttt{Prompt A}\\
  \texttt{Prompt B}\\
  \texttt{Prompt C}\\
  \texttt{A+B+C$\to$S}\\
  \texttt{S/3$\to$M}\\
  \texttt{Disp M}\\
}\hfill
\Prog{Programme Casio}{4.cm}{
  \texttt{"A="?$\to$A\return}\\
  \texttt{"B="?$\to$B\return}\\
  \texttt{"C="?$\to$C\return}\\
  \texttt{A+B+C$\to$S\return}\\
  \texttt{S/3$\to$M\return}\\
  \texttt{M\disp}
}%\hfill
\Prog{Programme Python}{4.4cm}{
  \texttt{A=input("A ?")}\\
  \texttt{B=input("B ?")}\\
  \texttt{C=input("C ?")}\\
  \texttt{A+B+C$\to$S}\\
  \texttt{S/3$\to$M}\\
  \texttt{print M}
}
\enex 

\bgex
Ecrire un algorithme, et le programmer, qui demande les coordonnées de
deux points $A$ et $B$, et calcule et affiche les coordonnées du
milieu $I$ de $[AB]$ et la longueur $AB$. 
\enex


\vspace{1cm}
\noindent
\begin{minipage}{\textwidth-7.8cm}
{\bf\large\ul{Boucles itératives}}\ \ 
\bgmp[t]{7.5cm} 
Une boucle permet de répéter un ensemble d'instructions un nombre fixé
de fois.\enmp
\end{minipage}\hspace{\fill}
\bgmp[t]{5.8cm}\vspace*{-0.8cm}\begin{tabular}{|p{5.7cm}|}\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}
\enmp

\vspace{-2em}

\bgex  Affichage des carrés 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}
}
\enex

\medskip

\bgmp{7.5cm}
\bgex

Exécuter l'algorithme suivant sur le graphique ci-contre: \vsp\\
\fbox{
\bgmp{7.5cm}
\texttt{Pour i allant de 2 à 18\\
  \hspace*{0.5cm}Afficher le point (i;2)\\
  \hspace*{0.5cm}Afficher le point (i;10)\\
  Fin Pour}

\vspd
\texttt{Pour j allant de 3 à 9\\
  \hspace*{0.5cm}Afficher le point (2;j)\\
  \hspace*{0.5cm}Afficher le point (18;j)\\
  Fin Pour}

\vspd
\texttt{Pour i allant de 3 à 10\\
  \hspace*{0.5cm}Afficher le point (i;9+i/2)\\
  \hspace*{0.5cm}Afficher le point (i+8;15-i/2)\\
  Fin Pour
}
\enmp}\enex\enmp
\hspace{1cm}
\bgmp{8cm}
\psset{xunit=0.5cm,yunit=0.5cm,arrowsize=7pt}
\begin{pspicture}(0,0)(20,16)
  \pspolygon[linewidth=0.5pt,linestyle=dashed](0,0)(20,0)(20,15)(0,15)
  \psline[linewidth=1.5pt]{->}(0,0)(1,0)
  \psline[linewidth=1.5pt]{->}(0,0)(0,1)
  \rput(0.5,-0.7){$\vec{i}$}
  \rput(-0.6,0.4){$\vec{j}$}
  \rput(-0.4,-0.5){$O$}
  \multido{\i=0+1}{21}{\multido{\ii=0+1}{16}{\rput(\i,\ii){\scriptsize+}}}
\end{pspicture}
\enmp


\bgex 
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}
}
\enex

\medskip


\noindent
\begin{minipage}[b]{\textwidth-4.2cm}
{\bf\large\ul{Tests et instructions conditionnelles.}} 
Un test est une comparaison entre la valeur d'une variable et une
valeur donnée, ou entre les valeurs de deux variables. 

\vsp
Un test a deux résultats possibles: 
$0$ (faux), ou $1$ (vrai). 

%\vspd

Les instructions ne sont effectuées que \emph{si} le test indiqué est vrai. 
\end{minipage}\quad
\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}

\vspace{-0.2cm}
\bgex Test: nombre positif ? \vspd\par
\Prog{Algorithme}{5cm}{
  \texttt{Lire A}\\
  \texttt{Si A>0}\\
  \hspace*{\ProgIndent}\texttt{Afficher "A positif"}\\
  \texttt{Sinon}\\
  \hspace*{\ProgIndent}\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.4cm}{
  \texttt{A=input("A ?")}\\
  \texttt{if A$\geq$0:}\\
  \hspace*{\ProgIndent}\texttt{print "A positif"}\\
  \texttt{else:}\\
  \hspace*{\ProgIndent}\texttt{print "A negatif"}\\
}
\enex


\bgex
Soit les points $A(2;3)$ et $B(-2;6)$. 
Ecrire un algorithme, et le programmer sur calculatrice, 
qui demande les coordonnées $x$ et $y$ d'un point $M$ 
et affiche si $M$ est plus près de $A$ ou de $B$. 
\enex

\bgex
Ecrire un algorithme, et le programmer, qui demande les coordonnées de
trois points $A$, $B$ et $C$, et qui indique, après calculs, si les
points sont alignés ou non. 
\enex



\noindent
\begin{minipage}{\textwidth-5cm}
{\bf\large\ul{Boucles conditionnelles.}} 
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}\quad
\bgmp[t]{5cm}
\begin{tabular}{|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}
\enmp

\vspace{-0.5cm}

\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


\bgex
Une ville compte 120\,000 habitants. 
Sa population augmente de 4\,\% par an. 

En combien d'années sa population aura-t'elle doublée ? 

Ce nombre d'années dépend-il du nombre d'habitants initial ?
\enex

\vspace{-0.3cm}

\bgex
4000 arbres poussent dans une forêt. 
Le nouveau plan d'exploitation prévoit, 
dès l'année prochaine, l'abattage de 20\,\% des arbres
et la plantation de 1000 arbres chaque année. 

Combien d'arbres cette forêt comptera-t'elle l'année prochaine ? 
Dans 3 ans ? Dans 10 ans ? 

Le nombre d'arbres de cette forêt va-t'il se stabiliser, ou la forêt
disparaître ?
\enex

\vspace{-0.3cm}

\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 euros, de 10 euros et de 5 euros 
à fournir pour faire le montant $N$. 
\enex

\clearpage
\noindent
{\bf\large\ul{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 en propose un
autre, et le jeu se poursuit, le but étant de trouver le nombre
mystérieux le plus rapidement. 

%\vspd
\noindent
\subsection*{L'ordinateur fait deviner} 

\vspace{-1.cm}
\bgmp{8cm} 
On commence par 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}. 
\enmp\hfill
\bgmp{9cm}
\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 afficher "Trop petit"}\\
\PI\texttt{Sinon 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"}
}
\enmp

\noindent
\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"}
}
\Prog{Programme Casio}{4.5cm}{
\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}
}
\bgmp[t]{6.5cm}
\bigskip

\subsection*{L'ordinateur doit deviner} 
%{\bf L'ordinateur cherche le nombre mystérieux.}

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. 

\medskip
Essayer de trouver une stratégie pour que l'ordinateur trouve ce
nombre avec le moins de coups possible.
\enmp





\end{document}

Haut de la page Haut de la page