\documentclass[10pt]{article}


\usepackage{ammaths}
\usepackage{isn}
\usepackage{verbatim}

\begin{document}

\entete{STS}{Xcas et son module de programmation}{TP}

\textbf{Xcas\footnote{Téléchargement sur \url{http://www-fourier.ujf-grenoble.fr/~parisse/irem.html}}} est un logiciel libre de calcul formel.\\
Les exemples ci-dessous présentent la syntaxe des principales instructions de programmation de Xcas. L'entrée dans l'éditeur de programme se fait avec la commande Alt+P.

\section{La suite de Fibonacci}

Léonard  de Pise, fils  de Bonacci,  s'est intéressé  en 1202  au fameux
problème des  lapins~:~un couple donne  naissance, à partir  du deuxième
mois à un  couple chaque mois, les nouveaux couples  suivant la même loi
de reproduction~; combien y  aura-t-il de lapins (supposés immortels...)
au bout de $n$ mois~?

Il s'agit donc d'étudier la suite $(F_n)$ définie par~:

\[F_0=F_1=1\qquad F_{n+2}=F_n+F_{n+1}\]


On peut écrire la (double !) récursion directement~:

\xc

\begin{lstlisting}[caption={suite de Fibonnacci en récursif brut}]
fiborec(n):={ //déclaration de la fonction
if n<2
   then return(1);
   else fiborec(n-1)+fiborec(n-2);
end_if
}:;
\end{lstlisting}

Très facile....mais peu efficace car il faut une vingtaine de secondes à
XCAS pour calculer \verb+fibo(30)+. En  effet, la  récursion  est double 
et  nécessite une  pile très importante. Mieux vaut recourir  à une fonction
impérative\footnote{ou une fonction récursive terminale via une fonction auxiliaire.}. 

% \begin{lstlisting}[caption={suite de Fibonnacci avec une récursion terminale}]
% fiborecterm(n, j, a, b):=
% {if j==n 
%    then return(b);
%    else return(fiborecterm(n, j+1, a+b, a))
% end_if
% }:;
% 
% fibo(n):=//fonction d'enveloppe
% {return fiborecterm(n, 0, 1, 1)
% }:;
% \end{lstlisting}
% 
On obtient les 15 premiers termes en faisant \emph{seq(fiborec(j),j=0..14)}. 

\begin{lstlisting}[caption={suite de Fibonnacci en impératif avec XCAS}]
fiboimp(n):={
local q;
local fib:=[1,1];// création d'une liste dont les deux premiers termes sont 1 et 1.
for q from 2 to n-1 by 1 do
    fib[q]:=fib[q-1]+fib[q-2];
    end_for;
return(fib);
}
:;
\end{lstlisting}
La commande \emph{fiboimp(15)} donnera la liste des 15 premieres valeurs.

\pagebreak

\section{Exercices}
\exo{On peut définir $n!$ en disant que $1!=1$ et que $n!=n.(n-1)!$\\
\begin{enumerate}
 \item Ecrire une fonction récursive et une  fonction itérative pour calculer $n!$. Comparer les deux fonctions en termes d'efficacité.
 \item Utiliser la fonction précédente pour définir les fonctions $A_{n}^{p}$ et $C_{n}^{p}$.
\end{enumerate}
}


\exo{Écrire une fonction retournant le triangle de Pascal jusqu'a un entier $n$. On utilisera une matrice $n \times n$ pour représenter un tableau et on utilisera la formule de pascal $C_n^p=C_{n-1}^{p-1}+C_{n-1}^{p}$ pour calculer les termes différents de 1.}
\begin{center}\begin{minipage}{10cm}
\begin{verbatim}
        1                                                                                            
        1    1                                                                                       
        1    2    1                                                      
        1    3    3     1                                      
        1    4    6     4      1                               
        1    5    10    10     5      1                        
        1    6    15    20    15      6     1                  
        1    7    21    35    35     21     7     1            
        1    8    28    56    70     56     28    8     1      
        1    9    36    84    126    126    84    36    9    1 
\end{verbatim} 
\end{minipage}\end{center}


\exo{Modifier le programme précédent afin de remplacer tous les nombres pairs par une étoile et tous les nombres impairs par un blanc.}

\begin{center}
\includegraphics[width=16cm]{pascal.eps}
 
\end{center}



\newpage
\entete{STS}{Xcas et son module de programmation}{Solution}

\begin{lstlisting}[caption={Factorielle en impératif avec XCAS}]
factorielle(n):={
local fact:=1;// création d'une variable locale (non typée).
for q from 1 to n by 1 do
    fact:=fact*q;
    end_for;
return(fact);
}
:;
\end{lstlisting}


\begin{lstlisting}[caption={Factorielle en récursif avec XCAS}]
factoriellerec(n):={
if n<2
   then return(1);
   else return(n*factoriellerec(n-1));
end_if
}
:;
\end{lstlisting}


\begin{lstlisting}[caption={Arrangement et combinaison}]
arrangement(n,p):=
{return(factorielle(n)/factorielle(n-p));
}
:;

combinaison(n,p):=
{return(factorielle(n)/(factorielle(n-p)*factorielle(p)));
}
:;
\end{lstlisting}


\begin{lstlisting}[caption={Triangle de Pascal}]
Pascal(n):={
local T,j,i;
T:=matrix(n,n);
pour j de 0 jusque n-1 faire
     pour i de 0 jusque n-1 faire
     si j>i alors T[i,j]:="" ;
            sinon si j==0 alors T[i,j]:=1 ;
            sinon si i==j alors T[i,j]:=1;
            sinon si (i>0) et (j>0) alors
                  T[i,j]:=T[i-1,j]+T[i-1,j-1];
            fsi;fsi;fsi;fsi;
    fpour;
fpour;
retourne(T);
}
:;
\end{lstlisting}

Pour le triangle fractale, il suffit d'ajouter juste avant l'instruction \emph{return} finale : 
\begin{lstlisting}
pour i de 0 jusque n-1 faire
   pour j de 0 jusque i faire
       si irem(T[i,j],2)==0 
          alors T[i,j]:="";
          sinon T[i,j]:="*";
       fsi;
   fpour;
fpour;
\end{lstlisting}








% \exo{\emph{La conjecture de Syracuse}
% 
% La suite de Syracuse est définie par un procédé très simple : Prenons un entier. S'il est pair, nous le divisons par 2. S'il est impair, on le multiplie par 3 et on ajoute 1. Puis on recommence avec le résultat ainsi obtenu.\\
% Par exemple, à partir de 14, on construit la suite des nombres : 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2 \dots
% \medskip
% La \emph{conjecture de Syracuse}, encore appelée \emph{conjecture de Collatz}, \emph{conjecture d'Ulam}, \emph{conjecture tchèque} ou \emph{problème 3x+1} est l'hypothèse mathématique selon laquelle la suite de Syracuse de n'importe quel entier strictement positif atteint 1.
% 
% Les noms multiples de cette suite prouvent la difficulté d'en retrouver la paternité exacte. La naissance de ce problème semble se situer autour des années 1950. Cette conjecture mobilisa tant les mathématiciens durant les années 60, en pleine guerre froide, qu'une blague courut selon laquelle ce problème serait l'\oe uvre d'un complot soviétique pour ralentir la recherche américaine. Plus sérieusement, Paul Erdös dit à propos de la conjecture de Collatz : « les mathématiques ne sont pas encore prêtes pour de tels problèmes ». Il proposa une offre de 500 dollars à quiconque lui donnerait une solution.
% \medskip
% L'étude de cette suite a donné lieu à la création d'un vocabulaire très imagé : 
% On appelle \textbf{vol} l'ensemble des valeurs rencontrées par la suite de nombre et \textbf{étape} un nombre de cette suite.\\
% On appelle \textbf{altitude maximale du vol} la plus grande étape. On définit également la \textbf{durée de vol} comme le nombre d'étapes à franchir avant d'arriver pour la première fois au chiffre 1,  et la \textbf{durée de vol en altitude} comme la durée entre le moment où le vol commence, et celui où il repasse sous sa valeur initiale.
% 
% \begin{enumerate}
%  \item Écrire une fonction qui renvoie le vol d'un nombre $n$.
%  \item Modifier le programme précédent afin d'obtenir la durée de vol, la durée de vol en altitude et l'altitude maximale d'un vol.
% \end{enumerate}
% }




% \xc
% \begin{lstlisting}[caption={suite de Syracuse en impératif}]
% syracuse(n):=
% {local S:=[n];// initialisation de la liste
% local k:=0;//compteur
% local N:=n;// initialisation du premier terme
% while(N>1)
% {N:=if irem(N,2)==0// test de parité
%        then N/2 ;
%        else 3*N+1 ;
%        end_if;
%   k:=k+1;
%   S[k]:=N;
% }//fin bloc while
% return(S);
% }
% :;
% \end{lstlisting}
% 
% \vspace{1cm}
% 
% \xc
% \begin{lstlisting}[caption={suite de Syracuse en récursif}]
% syracuse(n):=
% {local S:=[n];// initialisation de la liste
% local k:=0;//compteur
% local N:=n;// initialisation du premier terme
% while(N>1)
% {N:=if irem(N,2)==0// test de parité
%        then N/2 ;
%        else 3*N+1 ;
%        end_if;
%   k:=k+1;
%   S[k]:=N;
% }//fin bloc while
% return(S);
% }
% :;
% \end{lstlisting}



\end{document}




