\documentclass[a4paper,11pt]{article}
\textheight 23 cm
%\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{makeidx}
\usepackage{times}
%\usepackage{mathptmx}
%Uncomment next line for pdflatex and use includegraphics with eps file
% for latex2html don't use the option [width=\textwidth]
% check that xfig files are exported magnif 100%
\usepackage{ifpdf}
\ifpdf
 \usepackage[pdftex,colorlinks]{hyperref}
\else
 %\usepackage[ps2pdf,breaklinks=true,colorlinks=true,linkcolor=red,citecolor=green]{hyperref}
 \usepackage{pst-plot}
\fi
\usepackage{pst-plot}
\usepackage{graphicx}

%\def\@evenhead{\thepage\hfill{\footnotesize\textit{\leftmark}}}
%\def\@oddhead{\footnotesize{\textit{\rightmark}}\hfill\thepage}
%\usepackage{hp}
%HEVEA\@def@charset{US-ASCII}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{latexsym}

\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}

\title{Les exercices d'algorithmiques au baccalaur\'eat s\'erie S}
\makeindex
\author{Ren\'ee De Graeve}

\begin{document}
\maketitle
%\chapter{Les exercices d'algorithmiques au baccalaur\'eat s\'erie S}

Site web, page p\'edagogique et forum de Xcas~:
\begin{itemize}
\item \verb|www-fourier.ujf-grenoble.fr/~parisse/giac_fr.html|
\item \verb|www-fourier.ujf-grenoble.fr/~parisse/irem.html|
\item {\tt http://xcas.e.ujf-grenoble.fr/XCAS}
\end{itemize}
Se reporter en {\bf section 7} pour \'ecrire, compiler et ex\'ecuter
un programme {\tt Xcas}.

\section{Trois exercices classiques}
\subsection{La s\'erie harmonique}
On consid\`ere la suite $u_n=\sum_{j=1}^n\frac{1}{j}$.
\begin{enumerate}
\item Montrer que $u_{2n}-u_{n}$ est une somme de $n$ termes et que chaque terme
est sup\'erieur ou \'egal \`a $\frac{1}{2n}$. En d\'eduire que pour tout $n$, 
on a 
\[ u_{2n}-u_{n}\geq\frac{1}{2}\]
\item En d\'eduire que $u_n$ tend vers $+\infty$ quand $n$ tend vers $+\infty$.
\item On \'ecrit comme au 1,
\[u_{16}=\sum_{j=1}^{16}\frac{1}{j}=1+\frac{1}{2}+(\frac{1}{3}+\frac{1}{4})+(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8})+\sum_{j=9}^{16}\frac{1}{j}\]
Montrer que $u_{16}>3$.
\item \'Ecrire un algorithme permettant de trouver la plus petite valeur de $n$ pour laquelle $3<u_n$.
\item \'Ecrire un algorithme permettant de trouver la plus petite valeur de $n$ pour laquelle $p\leq u_n$ avec $p\in \R$. Tester ce programme pour $p=3,5,10,11$
\end{enumerate} 
{\bf La solution}\\
$u_{2n}-u_{n}=\displaystyle \frac{1}{n+1}+..+\frac{1}{n+n}$ et on a :
$\displaystyle\frac{1}{n+n}\leq \frac{1}{n+k}$ pour $k=1..n$. \\
$u_{2n}-u_{n}$ a donc $n$ termes et chaque terme est sup\'erieur ou \'egal \`a
$\displaystyle \frac{1}{2n}$ donc \\
$\displaystyle u_{2n}-u_{n}\geq \frac{n}{2n}=\frac{1}{2}$.\\
Donc  $u_{2n}-u_{n}$ ne tend pas vers z\'ero quand $n$ tend vers $+\infty$ donc $u_n$ n'est pas convergente. Comme $u_n$ est croissante et non convergente, 
$u_n$ n'est pas born\'ee donc $u_n$ tend vers $+\infty$ quand $n$ tend vers 
$+\infty$\\
{\bf L'algorithme en langage naturel}
\begin{verbatim}
Entree :         p entier
Variables :      j entier,S reel
Initialisation : Affecter a S la valeur 0
                 Affecter a j la valeur 0 
Traitement :     Tant que S<p faire
                   Affecter a j la valeur j+1
                   Affecter a S la valeur S+1/j
                 FinTantque
Sortie :         j
\end{verbatim}
{\bf La solution en langage {\tt Xcas}}
\begin{verbatim}
harmonique(p):={
  local j, S;
  S:=0;
  j:=0;
  tantque S<p faire
    j:=j+1;
    S:=S+1/j;
  ftantque;
  retoune j;
}:;
\end{verbatim}
On tape :
{\tt harmonique(3)} \hspace*{1.1cm}
On obtient :
{\tt 11}\\
On tape :
{\tt harmonique(5)} \hspace*{1.1cm}
On obtient :
{\tt 83}\\
On tape :
{\tt harmonique(10)}\hspace*{1cm}
On obtient :
{\tt 12367}\\
On tape : {\tt harmonique(11)}\hspace*{1cm}
On obtient :
{\tt 33617}

\subsection{Le compte bancaire}
Lors de la naissance de Pierre son grand-p\`ere d\'epose sur un compte bancaire
100 euros. \`A chaque anniversaire de Pierre, il d\'epose sur ce compte 
100 euros auquel il ajoute le double de l'age de Pierre.
\begin{itemize}
\item \'Ecrire un algorithme permettant de trouver le montant se trouvant sur 
son compte le lendemain des 10 ans de Pierre
\item Modifier l'algorithme pr\'ec\'edent pour d\'eterminer \`a quel age Pierre pourra acheter un objet de 2000 euros ? de $P$ euros ?
\item Modifier les algorithmes pr\'ec\'edents lorsque le compte o\`u est 
d\'epos\'e l'argent rapporte 2.5\% l'an (net d'impots, de taxes et de droit de 
succession !).
\end{itemize}
{\bf La solution en langage naturel}\\
Montant du compte lorsque Pierre a $n$ ans :
\begin{verbatim}
Entree :         n entier
Variables :      S reel, j entier
Initialisation : Affecter a S la valeur 100
Traitement :     Pour j allant de 1 a n faire 
                     Affecter a S la valeur S+100+2*j
                 FinPour
Sortie :         S
\end{verbatim}
Somme disponible>P et age correspondant de Pierre 
\begin{verbatim}
Entree :         P reel
Variables :      S reel, j entier
Initialisation : Affecter a S la valeur 100
                 Affecter a j la valeur 0
Traitement :     Tantque S<P 
                   Affecter a j la valeur j+1
                   Affecter a S la valeur S+100+2*j
                 FinTantque
Sortie :         S,j
\end{verbatim}
Si le compte rapporte 2.5\% par an, on \'ecrira dans le traitement des deux 
algorithmes pr\'ec\'edents :
{\tt Affecter \`a S la valeur S*1.0.25+100+2*j}\\
(au lieu de {\tt Affecter \`a S la valeur S+100+2*j})\\
\'Eventuellement on renverra la valeur de $S$ arrondie avec seulement 2 
chiffres apr\`es la virgule ({\tt evalf(S,2)}).\\
{\bf La solution en langage {\tt Xcas}}
\begin{verbatim}
banque(n):={
  // Montant du compte lorsque Pierre a n ans 
  local S,j;
  S:=100;
  pour j de 1 jusque n faire
    S:=S+100+2*j;
  fpour;
  retourne S;
}:;
banques(P):={
  // Somme disponible>=P et age correspondant de Pierre 
  local S,j;
  S:=100;
  j:=0;
  tantque S<P faire
    j:=j+1;
    S:=S+100+2*j;
  ftantque;
  retourne S,j;
}:;
banquier(n):={
  // On applique un interet de 2.5 pour cent 
  // Montant du compte lorsque Pierre a n ans 
  local S,j;
  S:=100;
  pour j de 1 jusque n faire
    S:=S*1.025+100+2*j;
  fpour;
  retourne evalf(S,2);
}:;
banquiers(P):={
  // On applique un interet de 2.5 pour cent 
  // Somme disponible>=P et age correspondant de Pierre 
  local S,j;
  S:=100;
  j:=0;
  tantque S<P faire
    j:=j+1;
    S:=S*1.025+100+2*j;
  ftantque;
  retourne evalf(S,2),j;
}:;
\end{verbatim}
On tape :
{\tt banque(10)}\\
On obtient :
{\tt 1210}\\
On tape :
{\tt banques(2000)}\\
On obtient :
{\tt 2106,17}\\
On tape :
{\tt banquier(10)}\\
On obtient :
{\tt 1367.02}\\
On tape :
{\tt banquiers(2000)}\\
On obtient :
{\tt 2027.75,14}

\subsection{La suite de Syracuse}
Soit $a$ un entier positif. On veut \'etudier la suite de 
Syracuse d\'efinie par :
\[
\left\{
\begin{array}{rcll}
u_0&=&a\\
u_n&=&u_{n-1}/2 & \mbox{si $u_{n-1}$ est pair }\\
u_n&=&3u_{n-1}+1 & \mbox{ si $u_{n-1}$ est impair}.
\end{array}
\right.
\]
Cette suite se termine toujours par 1, 4, 2, 1... mais on ne sait pas 
le d\'emontrer !!!
\begin{itemize}
\item
\'Ecrire un algorithme permettant de trouver la premi\`ere valeur $n$ de $k$
 pour laquelle $u_k=1$.
\item Modifier cet algorithme afin de connaitre en plus la plus grande valeur
$m$ prise par $u_k$ lorsque $k=0..n$.
\item Tester ce programme pour $a=3$, $a=5$, $a=7$ , $a=75\ $ et $a=97$. 
\item Tracer dans un rep\`ere orthogonal, pour $a=1...100$,
les points de coordonn\'ees $(a,n)$ (en rouge) et les points de coordonn\'ees 
$(a,m)$ (en noir).
\end{itemize} 
{\bf La solution en langage naturel}\\
Algorithme qui renvoie la premi\`ere valeur de $k$
 pour laquelle $u_k=1$.
\begin{verbatim}
Entree :         a
Variables :      k
Initialisation : Affecter a k la valeur 0
Traitement :     Tant que a different de 1 faire
                   Si a est pair alors 
                     Affecter a a la valeur a/2
                   Sinon
                     Affecter a a la valeur 3a+1
                   FinSi
                   Affecter a k la valeur k+1
                 FinTantque
Sortie :         k
\end{verbatim}
Algorithme qui renvoie $m$  la plus grande valeur
 prise par $u_k$ lorsque $k=0..n$ et $n$ est la premi\`ere valeur de $k$
 pour laquelle $u_k=1$
\begin{verbatim}
Entree :         a
Variables :      k,m
Initialisation : Affecter a m la valeur a
                 Affecter a k la valeur 0 
Traitement :     Tant que a different de 1 faire
                   Si a est pair alors 
                     Affecter a a la valeur a/2
                   Sinon
                     Affecter a a la valeur 3a+1
                     Si a>m alors Affecter a m la valeur a
                   FinSi
                   Affecter a k la valeur k+1
                 FinTantque
Sortie :         k,m
\end{verbatim}
{\bf La solution en langage {\tt Xcas}}
\begin{verbatim}
syracuse(a):={
  local k,m;
  k:=0;
  m:=a;
  tantque a!=1 faire
    si irem(a,2)==0 alors 
      a:=iquo(a,2); 
    sinon
      a:=a*3+1;
      si a>m alors m:=a; fsi;
    fsi;
    k:=k+1;
  ftantque;
retourne k,m;
}:;
\end{verbatim}
On tape :
{\tt syracuse(3)}\hspace*{1cm}
On obtient :
{\tt 7,16}\\
On tape :
{\tt syracuse(5)}\hspace*{1cm}
On obtient :
{\tt 5,16}\\
On tape :
{\tt syracuse(7)}\hspace*{1cm}
On obtient :
{\tt 16,52}\\
On tape :
{\tt syracuse(62)}\hspace*{0.8cm}
On obtient :
{\tt 107,9232}\\
On tape :
{\tt syracuse(63)}\hspace*{0.8cm}
On obtient :
{\tt 107,9232}\\
On tape :
{\tt syracuse(75)}\hspace*{0.8cm}
On obtient :
{\tt 14,340}\\
On tape :
{\tt syracuse(97)}\hspace*{0.8cm}
On obtient :
{\tt 118,9232}\\
On tape le programme qui affiche en rouge les points $(a,n)$ et en noir les 
points $(a,m)$ lorsque $a=1..100$.
\begin{verbatim}
syracuse100():={
  local a,n,m,L;
  L:=NULL;
  pour a de 1 jusque 100 faire
    n,m:=syracuse(a);
    L:=L,point(a,n,affichage=rouge),point(a,m,affichage=noir);
  fpour;
  retourne L;
}:;
\end{verbatim}
On tape :
{\tt syracuse100()} et on obtient :\\
\ \\
\includegraphics[width=\textwidth]{syracuse}
En changeant le rep\`ere, on peut voir des points tels que point(97,9232)\\
\ \\
\includegraphics[width=\textwidth]{syracuse1}

\section{En 2009 Centre \'etrangers}
On consid\`ere la fonction $f(x)=xe^x-1$ sur $\R$.
\begin{itemize}
\item Calculer $f(0$ et $f(1)$.\\
En \'etudiant les variations de $f$ sur $\R$, montrer que $f(x)=0$ 
admet une solution unique dans [0;1].
\item On consid\`ere l'algorithme :
\begin{verbatim}
Entree :         f la fonction pr\'ec\'edente 
                 n un entier
Variables :      a,b,m,p
Initialisation : Affecter a a la valeur 0
                 Affecter a b la valeur 1 
Traitement :     Tant que b-a>10^-n faire
                   Affecter a m la valeur (a+b)/2
                   Affecter a p la valeur f(a)*f(m)
                   Si p>0 
                     Affecter a a la valeur m
                   Sinon
                     Affecter a b la valeur m
                   FinSi 
                 FinTantque
Sortie :         a,b
\end{verbatim}
On fait fonctionner cet algorithme avec $n=1$.\\
Donner les valeurs que prennent successivement les diff\'erents param\`etres. 
\item Que d\'etermine cet algorithme ? \\
Quelle influence le nombre $n$ a-t-il sur le r\'esultat obtenu ?
\end{itemize}
{\bf La solution}\\
On a $f(0)=-1$ et $f(1)\simeq 1.71828182846$\\
Sur $]-\infty;0]$ $f(x)=xe^x-1\leq -1<0$  donc $f$ ne s'annule pas.\\ 
La fonction $f$ est continue et est strictement croissante sur $[0;+\infty[$ 
puisque sa deriv\'ee  $f'(x)=e^x(x+1)$ est n\'egative sur $]-\infty;-1[$ et 
positive sur $]-1;+\infty[$.\\
Donc d'apr\`es le th\'eor\`eme des valeurs interm\'ediaires $f(x)=0$ a une 
solution unique comprise entre 0 et 1 puisque $f(0)<0$ et $f(1)>0$.\\
L'algorithme trouve un encadrement de longueur inf\'erieure \`a $10^{-n}$ de 
cette solution : a chaque \'etape on partage l'intervalle $[a;b]$ en deux 
(dichotomie). Si $m$ est le milieu  de $[a;b]$, on regarde si $f(a)$ et $f(m)$ 
sont de m\^eme signe : si oui, $m$ peut remplacer $a$ et sinon $m$ peut 
remplacer $b$ et le z\'ero se trouve toujours entre $a$ et $b$.\\
Lorsque $n=1$ cet encadrement est de longueur $0,1$\\
{\bf Initialisation : } $a$=0 et $b$=1\\
{\bf Etape 1 : } $m$=0.5, $p=f(0)f(0.5)=0.17563936465$, $a$=0.5, $b$=1\\
{\bf Etape 2 : } $m$=0.75, $p=f(0.5)f(0.75)=-0.103232038761$, $a$=0.5, $b$=0.75\\
{\bf Etape 3 : } $m$=0.625, $p=f(0.5)f(0.625)=-0.02944659346$,$a$=0.5, $b$=0.625\\
{\bf Etape 4 : } $m$=0.5625, $p=f(0.5)f(0.5625)=0.002244979408$,$a$=0.5625, $b$=0.625\\
{\bf R\'esultat : } 0.5625,0.625\\
Arr\^et du tantque car ($b-a$)<0.1 et le r\'esultat est donc 0.5625,0.625.\\
{\bf La traduction en langage {\tt Xcas}}
\begin{verbatim}
dichotomie(f,n):={
  local a,b,m,p;
  a:=0.; b:=1.;
  tantque b-a>10^-n faire
    m:=(a+b)/2;
    p:=f(a)*f(m);
    si p>0 alors 
      a:=m;
    sinon
      b:=m;
    fsi;
  ftantque;
  retourne a,b;
}:;
\end{verbatim}
On tape :
{\tt f(x):=x*e\^x-1 :; dichotomie(f,1)}\\
On obtient :
{\tt x->x*exp(x)-1; 0.5625,0.6250}\\
Pour visualiser les \'etapes interm\'ediaires indiqu\'ees ci-dessus, on tape\\
{\tt debug(dichotomie(f,1))}\\
puis on clique plusieurs fois sur le bouton {\tt sst}.
Pour avoir une pr\'ecision plus grande, on tape :
{\tt dichotomie(f,2)}\\
On obtient :
{\tt 0.5625,0.5703125}\\
On tape :
{\tt dichotomie(f,5)}\\
On obtient :
{\tt 0.567138671875,0.56714630127}

\section{En 2010 Am\'erique du sud}
\begin{itemize}
\item On consid\`ere l'algorithme :
\begin{verbatim}
Entree :         n un entier
Variables :      u,S,j
Initialisation : Affecter a u la valeur 1
                 Affecter a S la valeur 1 
                 Affecter a j la valeur 0 
Traitement :     Tant que j<n faire
                   Affecter a u la valeur 2u+1-j
                   Affecter a S la valeur S+u
                   Affecter a j la valeur j+1
                 FinTantque
Sortie :         u,S
\end{verbatim}
Justifier que pour $n=3$, le r\'esultat de cet algorithme  est  11,21 
\item On consid\`ere les suites $u_n$ et $S_n$ d\'efinies par :\\
$u_0=1$ et $u_{n+1}=2u_n+1-n$\\
$S_n=u_0+u_+...+u_n$.\\
Que repr\'esente les valeurs donn\'ees par cet algorithme ?
\item Le but de cette question est de trouver $u_n$  en fonction de $n$
Modifier l'algorithme pour qu'il renvoie aussi $u_n-n$.
Montrer que $u_n-n=2^n$
\item Calculer $1+2+...+n\ $ et $\ 1+2+2^2+...+2^n$. \\
En d\'eduire $S_n$ en fonction de $n$.
\end{itemize}
\ \\
{\bf La solution}\\
Pour $n=3$, on a :\\
{\bf Initialisation : } u=1, S=1, j=0\\
{\bf Etape 1 : } u=3, S=4, j=1\\
{\bf Etape 2 : } u=6, S=10, j=2\\
{\bf Etape 3 : } u=11, S=21, j=3\\
{\bf R\'esultat : } 11,21\\
Arr\^et du tantque car j>=3 et le r\'esultat est donc 11,21.\\
Dans le corps du tantque on calcule $u,S$ et $j$ et on a $u=u_j$ et $S=S_j$.\\
Lorsque $j=n$ le tantque s'arr\^ete et renvoie $u_n,S_n$.\\ 
Faire attention \`a l'ordre des instructions : le nouveau $u$ (qui est $u_{j+1}=2u_j+1-j$) se calcule \`a partir de l'ancien $u$ et de l'ancien $j$.\\
\ \\
{\bf La traduction en langage {\tt Xcas}}
\begin{verbatim}
suiteserie(n):= {
  local u,S,j;
  u:=1;
  S:=1;
  j:=0;
  tantque j<n faire
    u:=2u+1-j;
    S:=S+u;
    j:=j+1;
  ftantque;
  retourne u,S;
}:;
\end{verbatim}
On veut trouver $u_n$ en fonction de $n$, on modifie l'algorithme pour qu'il 
renvoie aussi $u_n-n$, on modifie seulement l'avant-derni\'ere ligne
en  {\tt retourne u,S-n,S;}
\begin{itemize}
\item Pour $n=0$, on a :\\
{\bf Initialisation : } u=1, S=1, j=0\\
{\bf R\'esultat : } 1,1,1
\item
Pour $n=1$, on a :\\
{\bf Initialisation : } u=1, S=1, j=0\\
{\bf Etape 1 : } u=3, S=4, j=1\\
{\bf R\'esultat : } 3,2,4
\item
Pour $n=2$, on a :\\
{\bf Initialisation : } u=1, S=1, j=0\\
{\bf Etape 1 : } u=3, S=4, j=1\\
{\bf Etape 2 : } u=6, S=10, j=2\\
{\bf R\'esultat : } 6,4,10
\item
Pour $n=3$, on a :\\
{\bf Initialisation : } u=1, S=1, j=0\\
{\bf Etape 1 : } u=3, S=4, j=1\\
{\bf Etape 2 : } u=6, S=10, j=2\\
{\bf Etape 3 : } u=11, S=21, j=3\\
{\bf R\'esultat : } 11,8,21
\end{itemize}
Il semble que $u_n-n=2^n$.\\
Montrons le par r\'ecurrence~: pour $n=0$ $u_0-0=1=2^0$ et 
$u_{n+1}-(n+1)=2u_n+1-n-(n+1)=2(u_n-n)$.\\
De plus $1+2+..+n=n(n+1)/2$ et $1+2+2^2+..+2^n=2^{n+1}-1$,
donc 
\[ S_n=\frac{n(n+1)}{2}+2^{n+1}-1 \]
On v\'erifie pour $n=3$ $u_3=2^3+3=8+3=11$ et $S_3=6+2^4-1=16+5=21$\\
On a bien $u_5=2^5+5=32+5=37$ et $S_5=5*3+64-1=78$\\
On tape :
{\tt suiteserie(3)}\hspace*{1cm}
On obtient :
{\tt 11,21}\\
On tape :
{\tt suiteserie(5)}\hspace*{1cm}
On obtient :
{\tt 37,78}\\
\ \\
{\bf Remarque}
Il me semble pr\'ef\'erable d'\'ecrire cet algorithme avec un {\tt pour}.\\
Mais attention aux indices!!! \\
On doit utiliser la relation de r\'ecurrence sous la forme :
\begin{center}
$u_n=2u_{n-1}+2-n$ ou bien $u_{n+1}=2u_n+2-(n+1)$ 
\end{center}
car dans le corps du 
{\tt pour} on calcule successivement :\\
$u_1,S_1$ lorsque $j=1$, $u_2,S_2$ 
lorsque $j=2$,... et $u_n,S_n$ lorsque $j=n$.\\
Alors que pr\'ec\'edement avec {\tt tantque},
on utilise la relation $u_{n+1}=2u_n+1-n$ car on
calcule successivement $u_1,S_1$ lorsque $j=0$, $u_2,S_2$ 
lorsque $j=1$ et $u_n,S_n$ lorsque $j=n-1$ et c'est pourquoi la condition 
d'arr\^et du {\tt tantque} est {\tt j<n}.\\
On tape :
\begin{verbatim}
suiteserie1(n):= {
  local u,S,j;
  u:=1;
  S:=1;
  pour j de 1 jusque n faire
    u:=2u+2-j;
    S:=S+u;
  fpour;
  retourne u,u-n,S;
}:;
\end{verbatim}

\section{En 2011 La R\'eunion}
On consid\`ere la fonction $f(x)=4e^{x/2}-5$ sur $\R$.\\
On note $C_f$ le graphe de  $f$ dans un rep\`ere orthogonal
\begin{itemize}
\item  Calculer $f(0)$ et $f(1)$.\\
En \'etudiant les variations de $f$ sur $\R$, montrer que $f(x)=0$ 
admet une solution unique dans [0;1].
\item On consid\`ere l'algorithme :
\begin{verbatim}
Entree :         f la fonction precedente
                 p un reel >0
Variables :      a,b
Initialisation : Affecter a a la valeur 0
                 Affecter a b la valeur -1 
Traitement :     Tant que b<0 faire
                   Affecter a a la valeur a+p
                   Affecter a b la valeur f(a)
                 FinTantque
Sortie :         a-p,a
\end{verbatim}
Que fait cet algorithme ?\\
Que renvoie ce programme lorsque $p=1$ ? $p=0.1$ ? $p=0.01$ ? $p=0.001$ ?
\end{itemize}
{\bf La solution et traduction en langage {\tt Xcas}}\\
On a $f(0)=-1$ et $f(1)\simeq 1.5948850828$\\
La fonction $f$ est continue et est strictement croissante sur $\R$ puisque sa 
deriv\'ee qui vaut $f'(x)=2e^{x/2}$ est positive.\\
Donc d'apr\`es le th\'eor\`eme des valeurs interm\'ediaires $f(x)=0$ a une 
solution unique comprise entre 0 et 1 puisque $f(0)<0$ et $f(1)>0$.\\
L'algorithme trouve un encadrement de longueur $p$ de cette solution.\\
Lorsque $p=1$ cet encadrement est $0,1$\\
Lorsque $p=0.1$ cet encadrement est $0.4,0.5$ car $f(0.4)\simeq -0.114388967359$<0 et $f(0.5)\simeq 0.136101666751$>0\\
Lorsque $p=0.1$ cet encadrement est $0.44,0.45$ car $f(0.44)\simeq -0.0156930776507$<0 et $f(0.45)\simeq 0.00929086476731$>0\\
Avec {\tt Xcas}, on tape pour d\'efinir la fonction $f$ :\\
{\tt f(x):=4*exp(x/2)-5}\\
On tape la traduction de l'algorithme avec {\tt Xcas} :
\begin{verbatim}
zeroapprox(f,p):={
  local a,b;
  a:=0;
  b:=f(a);
  tantque b<0 faire 
    a:=a+p;
    b:=f(a);
  ftantque;
  retourne a-p,a
}:;
\end{verbatim}
On tape :
{\tt zeroapprox(f,0.1)}\hspace*{1cm}
On obtient :
{\tt 0.4,0.5}\\
On tape :
{\tt zeroapprox(f,0.01)}\hspace*{0.8cm}
On obtient :
{\tt 0.44,0.45}\\
On tape :
{\tt zeroapprox(f,0.001)}\\
On obtient :
{\tt 0.445999999998,0.446999999998}\\
On tape :
{\tt zeroapprox(f,0.0001)}\\
On obtient :
{\tt 0.446199999974,0.446299999974}\\
On remarquera que cet algorithme est 
valable pour toutes les fonctions continues $f$ qui v\'erifient
$f(0)<0$ et $f(1)>0$ (on calcule alors une valeur approch\'ee de
la plus petite racine de $f$).\\ 
{\bf Remarque} 
Ce programme est moins performant que le programme de dichotomie vu 
pr\'ec\'edemment.

\section{En 2012 France}
Soit $(u_n )$ la suite d\'efinie pour tout entier strictement positif par :
$$u_n = 1 +\frac{1}{2}+\frac{1}{3}...+\frac{1}{n}-\ln(n)$$
\begin{enumerate}
\item On consid\`ere l'algorithme suivant :
\begin{verbatim}
Entree :         l'entier n
Variables :      j est un entier
                 u est un reel
Initialisation : Affecter a u la valeur 0
Traitement :     Pour j variant de 1 a n
                   Affecter a u la valeur u +1/j
                 fPour
Sortie :         Afficher u
\end{verbatim}
Donner la valeur exacte affich\'ee par cet algorithme lorsque l???utilisateur 
entre la valeur $n=3$.
\item Recopier et compl\'eter l'algorithme pr\'ec\'edent afin qu'il affiche la 
valeur de $u_n$ lorsque l'utilisateur entre la valeur de $n$.
\item Voici les r\'esultats fournis par l'algorithme modifi\'e, arrondis \`a
$10^{-3}$.\\
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
$n$&6&7&8&9&10&100&1000&1500&2000\\
\hline
$u_n$&0.658&0.647&0.638&0.632&0.626&0.582&0.578&0.578&0.577\\
\hline
\end{tabular}
\`A l'aide de ce tableau, formuler des conjectures sur le sens de variation de 
la suite $(u_n)$ et son \'eventuelle convergence.
\end{enumerate}
{\bf La solution et la traduction avec {\tt Xcas}}\\
Le but de l'exercice est de trouver une approximation de la constante 
d'Euler :\\
$\gamma=\lim_{n \rightarrow +\infty}(1+\frac{1}{2}+\frac{1}{3}...+\frac{1}{n}-\ln(n))$.\\
On montre dans un premier temps que cette limite existe car
\begin{itemize}
\item $u_n$ est d\'ecroissante, en effet 
$\displaystyle u_{n+1}-u_n=\frac{1}{n+1}+\ln(\frac{n}{n+1})$  et\\
l'\'etude de $\displaystyle f(x)=\frac{1}{x+1}+\ln(\frac{x}{x+1})$ montre que 
$f$ est n\'egative sur $[1;+\infty[$
\item
de plus $u_n$ est minor\'ee par 0. En effet pour $p\in \N^*$,on a~:
\[ \int_{p}^{p+1}\frac{dx}{x} \leq \int_{p}^{p+1}\frac{dx}{p} 
\ \Rightarrow \ \ln(p+1)-\ln(p) \leq \frac{1}{p} \]
En sommant cette in\'egalit\'e pour $p=1..n\ $ on a :\\
\[ \ln(n+1) \leq 1+\frac{1}{2}+\frac{1}{3}...+\frac{1}{n} \]
donc~:
\[
0<\ln(1+1/n) \leq 1+\frac{1}{2}+\frac{1}{3}...+\frac{1}{n-1}+\frac{1}{n}-\ln(n) \]
\end{itemize}
Ainsi $u_n$ est d\'ecroissante et minor\'ee par 0 elle a donc une limite 
positive appel\'ee "constante d'Euler".\\
{\bf L'algorithme} calcule $1+\frac{1}{2}+\frac{1}{3}...+\frac{1}{n}$\\
Pour $n=3$\\
{\bf Initialisation : } u=0\\
{\bf Etape 1 : } j=1, u=1\\
{\bf Etape 2 : } j=2, u=3/2\\
{\bf Etape 3 : } j=3, u=11/6\\
{\bf Resultat : } 11/6 ou 1.83333333333\\
On modifie l'algorithme pour qu'il affiche la suite $\displaystyle u_n=1+\frac{1}{2}+...+\frac{1}{n}-\ln(n)$, pour cela, il suffit de modifier la sortie :
\begin{verbatim}
Entree :         l'entier n
Variables :      j et n sont des entiers naturels
                 u est un reel
Initialisation : Affecter a u la valeur 0
Traitement :     Pour j variant de 1 a n
                   Affecter a u la valeur u +1/j
                 fPour
Sortie :        Afficher u-ln(n)
\end{verbatim}
{\bf La traduction avec {\tt Xcas}}\\
On retourne une valeur num\'erique gr\^ace \`a {\tt evalf(u)} qui transforme le
rationnel $u$ en un nombre d\'ecimal. 
\begin{verbatim}
csteuler(n):={
  local j, u;
  u:=0;
  pour j de 1 jusque n faire
    u:=u+1/j;
  fpour;
  retourne evalf(u)-ln(n);
}:;
\end{verbatim}
On tape :
{\tt csteuler(10)}\\
On obtient :
{\tt 0.626383160974}\\
On tape :
{\tt csteuler(100)}\\
On obtient :
{\tt 0.582207331651}\\
On tape :
{\tt csteuler(1000)}\\
On obtient :
{\tt 0.577715581568}\\
On tape :
{\tt csteuler(2000)}\\
On obtient :
{\tt 0.577465644068}\\
On tape :
{\tt csteuler(20000)}\\
On obtient :
{\tt 0.577240664693}\\
Cela montre que la constante d'Euler est proche de 0.577240664693.\\
On tape pour v\'erifier ({\tt Xcas} connait cette constante)~:\\
{\tt evalf(euler\_gamma)}\\
On obtient :\\
{\tt 0.5772156649018}\\
{\bf Remarque}
Les deux variantes de {\tt csteuler} \'ecrites ci-dessous font \`a chaque 
\'etape un calcul num\'erique car on a mis {\tt 1./j} au lieu de {\tt
  1/j}. 
La fonction
{\tt csteuler0} calcule la somme des $\frac{1}{k}$ pour $k$ allant de 1 \`a $n$, alors que
{\tt csteuler1} calcule la somme des $\frac{1}{k}$ pour $k$ allant de $n$ \`a 1
\begin{verbatim}
csteuler0(n):={
  local j,u;
  u:=0;
  pour j de 1 jusque n faire
    u:=u+1./j;
  fpour;
  retourne u-ln(n);
} :;
csteuler1(n):={
  local j,u;
  u:=0;
  pour j de n jusque 1 pas -1 faire
    u:=u+1./j;
  fpour;
  retourne u-ln(n);
}:;
\end{verbatim}
On tape :
{\tt csteuler0(2000)}\\
On obtient :
{\tt 0.577465643831}\\
On tape :
{\tt csteuler1(2000)}\\
On obtient :
{\tt 0.577465644032}\\
On tape :
{\tt csteuler(2000)}\\
On obtient :
{\tt 0.577465644068}\\
Il faut comprendre la diff\'erence des r\'esultats obtenus entre les 
fonctions {\tt csteuler0}, {\tt csteuler1} et {\tt csteuler} :\\
{\tt csteuler1} donne un r\'esultat meilleur que {\tt csteuler0} car il 
commence par ajouter des petits nombres donc la somme conserve plus de  
d\'ecimales.\\
Le r\'esultat de {\tt csteuler} est encore meilleur car il ne fait 
l'approximation d\'ecimale qu'\`a la fin du programme.

\section{D'autres algorithmes sur ce mod\`ele}
\subsection{Calcul de $1+2+..+n^2$}
Soit la suite $u_n=1+4+..+n^2$.\\
\'Ecrire un algorithme qui calcule $u_n$ en fonction de $n$.\\
Puis calculer successivement $u_n/n$ et $u_n/(n(n+1))$ pour $n=1..10$\\
Montrer que $\displaystyle u_n=\frac{n(n+1)(2n+1)}{6}$\\
{\bf La solution}\\
On \'ecrit l'algorithme~:
\begin{verbatim}
Entree :         l'entier n
Variables :      j est un entier
                 S est un reel
Initialisation : Affecter a S la valeur 0
Traitement :     Pour j variant de 1 ?? n
                   Affecter a S la valeur S+j^2
                 fPour
Sortie :        Afficher S
\end{verbatim}
{\bf Avec {\tt Xcas}} :
\begin{verbatim}
Scarre(n):={
  local j,S;
  S:=0;
  pour j de 1 jusque n faire
    S:=S+j^2;
  fpour;
  retourne S;
}:;
\end{verbatim}
On tape :
{\tt Scarre(p)\$(p=0..10)}\\
On obtient :\\
{\tt 0,1,5,14,30,55,91,140,204,285,385}\\
Pour avoir la s\'equence des valeurs retourn\'ees pour $p$ variant de
0 \`a 10, on tape :
{\tt seq(Scarre(p)/p,p,0,10)}\\
On obtient :\\
{\tt [1,5/2,14/3,15/2,11,91/6,20,51/2,95/3,77/2]}\\
On tape :
{\tt seq(p*(p+1)*(2p+1)/6),p,1,10)}\\
et on obtient le r\'esultat pr\'ec\'edent.\\
Il reste donc \`a d\'emontrer par r\'ecurrence que :\\
$\displaystyle u_n=1+2^2+..+n^2=\frac{n(n+1)(2n+1)}{6}$

\subsection{Calcul de $\displaystyle 1+\frac{1}{2^2}+..+\frac{1}{n^2}$}
\'Ecrire un algorithme qui calcule $u_n=1+\frac{1}{2^2}+..+\frac{1}{n^2}$ en 
fonction de $n$.\\
{\bf La solution :} on \'ecrit l'algorithme :
\begin{verbatim}
Entree :         l'entier n>=1
Variables :      j un entier, S un r??el
Initialisation : Affecter a S la valeur 0
Traitement :     Pour j variant de 1 a n
                   Affecter a S la valeur S+1/j^2
                 fPour
Sortie :         Afficher S
\end{verbatim}
{\bf Avec {\tt Xcas}}
\begin{verbatim}
Scarre(n):={
  local j,S;
  S:=0;
  pour j de 1 jusque n faire
    S:=S+1/j^2;
  fpour
  retourne S;
}:;
\end{verbatim}
On tape :
{\tt Sseq(invcarre(p),p=1..9)}\\
On obtient :
{\tt 1,5/4,49/36,205/144,5269/3600,5369/3600,\\266681/176400,1077749/705600,9778141/6350400}\\
On tape :
{\tt evalf(seq(Sinvcarre(p)),p=0..9)}\\
On obtient  :
{\tt 1.0,1.25,1.36111111111,1.42361111111,1.46361111111,\\
1.49138888889,1.51179705215,1.52742205215,1.53976773117,}\\
On tape (on admet que $u_n$ tend vers $\pi^2/6$ quand $n$ tend vers $+\infty$) :\\
{\tt sqrt(6.*Sinvcarre(1000))}\\
On obtient :
{\tt 3.14063805621}

\subsection{Calcul des termes de la suite de Fibonacci}
 La suite de Fibonacci $u_n$ est d\'efinie par :\\
$u_0=1,\ u_1=1,\ u_{n+2}=u_{n+1}+u_n$ pour $n\in \N$\\
\'Ecrire un algorithme qui calcule $u_n$ en fonction de $n$.\\
{\bf La solution :} on \'ecrit l'algorithme :
\begin{verbatim}
Entree :         l'entier n.
Variables :      j,a,b,c sont des entiers
Initialisation : Affecter a a la valeur 1
                 Affecter a b la valeur 1
Traitement :     Pour j variant de 2 a n
                   Affecter a c la valeur a+b
                   Affecter a a la valeur b
                   Affecter a b la valeur c
                 fPour
Sortie :         Afficher b
\end{verbatim}
{\bf Avec {\tt Xcas}}
\begin{verbatim}
fibo(n):={
  local j,a,b,c;
  a:=1;
  b:=1;
  pour j de 2 jusque n faire
    c:=a+b;
    a:=b;
    b:=c;
  fpour;
  retourne b;
}:;
\end{verbatim}
On tape :
{\tt seq(fibo(p),p=0..10)}\\
On obtient les 11 premiers termes de la suite de Fibonacci :\\
{\tt 1,1,2,3,5,8,13,21,34,55,89}\\
On tape :
{\tt fibo(101)/fibo(100)}\\
On obtient :\\
{\tt 927372692193078999176/573147844013817084101}\\
On tape :
{\tt evalf(fibo(101)/fibo(100)),(1+sqrt(5))/2.}\\
On obtient :
{\tt 1.61803398875, 1.61803398875}\\
Il reste \`a montrer que $\displaystyle v_n=\frac{u_{n+1}}{u_n}$ tend vers \`a 
$\displaystyle \frac{1+\sqrt 5}{2}$ qui est le nombre d'or.

\section{\'Ecrire, compiler et ex\'ecuter un programme {\tt Xcas}}
\begin{itemize}
\item Ouvrir un niveau \'editeur de programme soit en tapant {\tt Alt+p}, soit 
avec le menu {\tt Prg$\blacktriangleright$Nouveau programme}. Une
boite de dialogue s'ouvre pour faciliter la d\'efinition d'une
nouvelle fonction.
\item Taper le programme en utilisant les boutons \verb|Fonctions|,
  \verb|Test| et \verb|Boucles| (assistant de cr\'eation d'une fonction,
d'un test ou d'une boucle)  ou le menu {\tt Ajouter} de l'\'editeur. 
Le nom du programme et de ses 
arguments ne doit pas \^etre un mot-clef ou une commande de {\tt Xcas}, ces 
mots apparaissent en bleu et brun.
\item Cliquer sur {\tt OK} ou appuyer sur {\tt F9}, pour compiler le 
programme.
\item Dans une ligne de commandes, taper le nom du programme suivi 
entre parenth\`eses par les valeurs des param\`etres s\'epar\'ees par des 
virgules et appuyer sur {\tt Enter}
\end{itemize}
\end{document}
