% Il faut le package d'ines
\documentclass[10pt]{article} 
\usepackage{tdtpik}
\usepackage{a4wide,french}
\usepackage{amsmath, amssymb, latexsym}
\usepackage[dvips]{epsfig}
\usepackage{picinpar}
%\CORRECTIONfalse
\CORRECTIONtrue

\setcounter{WORKnumber}{12} % Ex: 2 -> td No.2 
\course{deug} \group{}%\group{3$^{\mbox{\`eme}}$ ann\'ee}
\TD{IF122}
\theme{ {\bf R\'evisions} }
\UMLVLOGOfalse
\auteurs{}
%
\newenvironment{Pitemize}
  {\begin{list}{--}%
      {\setlength{\leftmargin}{10pt}
       \setlength{\itemsep}{0pt}% 
       \setlength{\topsep}{-4pt}%  
      }% 
  }%     
{\end{list}
\smallskip}

\newcommand{\mbf}[1]{\mathbf{#1}}

\parindent 0pt

\def\sp{\hspace*{5mm}}
\def\o{$^{\text{o}}$}

\pagestyle{empty}

\begin{document}
\maketitle
%
%%
%%% Resume du td.
%%
%
\begin{abstract}
%
\end{abstract}


%
%%
%%% DEBUT DU TRAVAIL
%%
%

\begin{exercice}
Le but de cet exercice est d'afficher tout les mots d'une certaine
longueur, construit sur 0,1 et ayant autant de 0 que de 1.
\begin{enumerate}
	\item Que fait le programme suivant :
\begin{verbatim}
void f(){
 int i1,i2;
 for(i1=0;i1<=1;i1++){
     for (i2=0;i2<=1;i2++) {
         cout << i1 << i2 << endl;
     }
 }
}
\end{verbatim}
\begin{correction}
et bien il affiche tout les mots de 2 lettres fait de 0 et de 1
\end{correction}

	\item Ecrivez une procedure qui affiche tout les mots de 4 lettres ayant autant de 0 que de 1;
\begin{correction}
On introduit 2 boucles de plus. On peut remarquer que si j'ai autant de 0 que de 1, alors j'en ai 2 !!!!!!!!!!
\begin{verbatim}
void f(){
 int i1,i2,i3,i4;
 for(i1=0;i1<=1;i1++){
     for (i2=0;i2<=1;i2++) {
        for (i3=0;i3<=1;i3++) {
            for (i4=0;i4<=1;i4++) {
	        if (i1+i2+i3+i4==2) cout << i1 << i2 << i3 << i4 << endl;
            }
        }
     }
 }
}
\end{verbatim}
\end{correction}
	\item Dans quelle mesure peut on g\'en\'eraliser ?
\begin{correction}
Pas trop comme ca, a priori il faut compliquer.
\end{correction}
	\item Le probl\`eme est \`a pr\'esent le suivant : On demande
	\`a l'utilisateur de fixer la longueur des mots, puis le
	programme doit tous les afficher. On choisit de mod\'eliser
	les mots par des listes. On suppose que l'on dispose des
	proc\'edures suivantes : {\bf ajoute\_tete(liste \&l,int i),
	ajoute\_queue(liste \&l,int i), efface\_tete(liste \&l),
	efface\_queue(liste \&l), affiche\_ordre(liste l),
	affiche\_ordre\_inverse(liste l)}. Proposez une solution. Si
	vous en avez plusieurs, comparez en la complexit\'e.
\begin{correction}
\begin{verbatim}
void affiche(int rest0, int rest1,liste m){
 liste m1,m2;
 if (rest0+rest1==0) affiche_ordre(m);
 else {
 if (rest0) {m1=ajoute_tete(m,0); affiche(rest0-1,rest1,m1);}
 delete m1;
 if (rest1) {m2=ajoute_tete(m,1); affiche(rest0,rest1-1,m2);}
 delete m2;
 }
}
void main(){
int L;
liste m=NULL;
cout <<  ``entrez la longueur des mots'';
cin >> L;
affiche(L/2,L/2,m);
}
\end{verbatim}
Alors il y a des choses de cach\'ees ici : si on avait fait le choix
d'ajouter en queue, alors il aurait fallut penser a supprimer ce qui a
ete mis en plus apres chaque appel recursif. L'affichage dans l'ordre
ou pas est indifferents, c'est une histoire de convention, mais ca
doit amener la question : dans quel ordre sont generes les mots.

Lors de la correction vous pouvez proposer aussi la seconde solution
suivante. Se pose a lors le Pb de la complexite. Dans la seconde on g\'enere les $2^L$ mots (il faut y ajouter la complexite du test) dans la premi\`ere on ne g\'enere que les $C_{L}^{L/2}$. 
\begin{verbatim}
void affiche(int longueur,liste m){
 liste m1,m2;
 if (longueur==0 && difference_01(m)==0) affiche_ordre(m);
 else {
 m1=ajoute_tete(m,0); affiche(longueur-1,m1);
 delete m1;
 m2=ajoute_tete(m,1); affiche(longueur-1,m2);
 delete m2;
 }
}
int difference_01(liste m){
 if (m==NULL) return 0;
 return ( difference_01(m->suivant) + (2* m->val -1)); // pour rigoler
}
void main(){
int L;
liste m=NULL;
cout <<  ``entrez la longueur des mots'';
cin >> L;
affiche(L/2,L/2,m);
}
\end{verbatim}
\end{correction}

	\item Il est possible d'obtenir un r\'esultat similaire sans
	utiliser la r\'ecursion. Proposez une m\'ethode originale,
	sans rentrer dans tout les d\'etails. (Que pensez vous de la representation binaire des nombres, et des op\'erateurs $>>$ et $<<$ ?
\begin{correction}
Allez, je propose de faire la chose suivante : \\
1) on construit une liste de longueur L constitu\'ee de 0's\\
2) on la voit comme un nombre binaire, et on passe au suivant en faisant + 1 ce qui permet de tous les enumerer.\\
3) on utilise un test le long de l'enumeration pour savoir si le mot est conforme.
\end{correction}
	
	\item Implementez la m\'ethode pr\'ec\'edente
\begin{correction}

Il est a rapeller que si x est un entier, x << 2 et x >> 2 sont les
decalages de bit a gauche et a droite.
\begin{verbatim}
void main(){
int L,m;
cout <<  ``entrez la longueur des mots'';
cin >> L;
for(m=0;m<2^L;m++){ if (count_01(m,L)==0) cout << m << endl;}
}

int count_01(int m,int L){
 int aux,rep=0,i; 
 for(i=0;i<L;i++){
  aux=m>>i;
  aux=aux -(aux>>1)<<1;
  if (aux==1) rep++; else rep--;
 }
return rep;
}
\end{verbatim}
\end{correction}

\end{enumerate}

\end{exercice}

\begin{exercice}
La hauteur de l'arbre vide est 0. La hauteur d'un arbre est \'egale au
maximum des hauteurs de ses fils plus 1. Un arbre est complet si
chacun de ses noeuds a des fils de m\^eme hauteur.

\begin{enumerate}
	\item quelle est la hauteur d'une feuille ?
	\item dessiner un arbre binaire complet de hauteur 2.
	\item Combien de feuilles y a t'il dans un arbre binaire complet de hauteur h ?
	\item Combien de noeuds ?
\end{enumerate}
\begin{correction}
Un arbre de hauteur $h\neq 0$ a $2^{h-1}$ feuilles : $F_1=1$ et
$F_{h+1} = F_h + F_h$ (les feuilles pour chacun de ses fils + le fait
que les fils sont complets)\\

Pour les noeuds : $N_{h+1} = N_h + F_{h+1}$ avec $N_0=0$ c'est que $N_h = \sum_{i=1}^{h} 2^{i-1}=\sum_{i=0}^{h-1} 2^i = 2^h -1$

\end{correction}

\end{exercice}

\begin{exercice}
Que fait le programme suivant :
\begin{verbatim}
int f(arbre &a) {
    if (a==NULL) {
       a=new (noeud);
       a->val =1;
       a->gauche=NULL;
       a->droite=NULL;
       return 1;
    }
    else{
     a->val =  f(a->gauche) + f(a->droite);
     return a->val;
   }
}
void main(){
arbre a=arbre_aleatoire();
int i,n,x;
cout << ``donner moi une valeur ``;
cin >> n;
 for (i=0;i<n;i++){
 cout << f(a);
 }
}
\end{verbatim}
\begin{correction}
Il fait deux choses : il agrandit l'arbre en lui rajoutant une couche
de feuilles (c'est le printemps), et chaque noeud est inform\'e du
nombre de feuilles que contient son sous arbre (large)

{\bf Passez directement \`a l'exercice qui reparle de 3. En leur
disant de modifier le code. (Je l'ai plac\'e plus loin pour ne pas
leur donner qq indication que ce soit.}

Bon, pour tester on peut commencer par a=NULL.
\end{correction}
\end{exercice}


\begin{exercice}

Une liste chain\'ee circulaire est une suite de cellules, exactement
comme une liste chain\'ee, sauf que le successeur du dernier element
est le premier element.
\begin{enumerate}
 \item Proposez un type de donn\'ee pour les listes chain\'ees
 circulaires.
 \item Ecrivez une fonction qui effectue l'union de deux listes chain\'ees circulaires.
\end{enumerate}
\begin{correction}
\begin{verbatim}
noeud * get_last(liste_c a){
     noeud *last=a;
     if (a==NULL) {cout << ``pb''; return NULL;}
     while (last->suiv != a) {last=last->suiv;}
     return last;
}
 
liste_c fusion(liste_c a, liste_c b){
   if (a==NULL) return b;
   if (b==NULL) return a;
   *cell aux= get_last(a);
   aux->suiv=b;
   aux= get_last(b);
   aux->suiv=a;
   return a;  // ou aux, ou b
}
\end{verbatim}
\end{correction}
\end{exercice}

\begin{exercice}
La proc\'edure suivante a pour arguments $max1,max2$ qui sont pass\'e
en reference. On veut que l'appel de cette proc\'edure modifie ces
variables pour qu'elles contiennent les deux plus grandes valeurs du
tableau A. (ces deux valeurs peuvent \^etre \'egales).  Le dernier
param\`etre repr\'esente la taille du tableau. Pour \'eviter de
nombreuses solutions, (et pour en avoir de simples) on vous impose de
n'utiliser que l'equivalent d'une boucle, au plus. Donner une version
iterative et une version recursive.


\begin{verbatim}
void plusgrandes (int& max1, int& max2, int A[], int n)
\end{verbatim}
\begin{correction}
\begin{verbatim}
void plusgrandes (int& max1, int& max2, int A[], int n){
  int i;
  if (n<2) cout << ``question idiote'';
  else{
      if (A[0] < A[1]) {
         max1=A[1]; max2=A[0];}
      else {
         max1=A[0]; max2=A[1];}

      for (i=2;i<n;i++){   // on commence a 2
         if (A[i]>max2){  // remarquez que je compare a max2 et pas a max1
            if (A[i]<max1) max2=A[i];
            else {
            max2=max1;max1=A[i];
            }
         }
      }
}
\end{verbatim}

Moins d'une boucle ca va etre dur, on essaye de la cacher :
\begin{verbatim}
void plusgrande (int& max1, int& max2, int A[], int n){
 if (n<2) cout << ``question idiote'';
 else{
   if (n==2){
      if (A[0] < A[1]) {
         max1=A[1]; max2=A[0];}
      else {
         max1=A[0]; max2=A[1];}
   else{
      plusgrande(max1,max2,A+1,n-1);
      if (A[0] >max2){  // remarquez que je compare a max2 et pas a max1
         if (A[0]<max1) max2=A[0];
         else {max2=max1;max1=A[0];
         }
      } // sinon on ne fait rien
   }
}
\end{verbatim}

\end{correction}
\end{exercice}

\begin{exercice}
Modifier le programme de l'exercice 3 de sorte que chaque noeud contienne \`a pr\'esent le nombre de noeuds internes du sous arbre dont il est racine.

\begin{correction}
\begin{verbatim}
a->val =1; ----> a->val =0;
return 1;  ----> return 0;

a->val = 1 + f(a->gauche)+ f(a->droite);
\end{verbatim}
\end{correction}
\end{exercice}




\begin{exercice}
Supposez qu'on veuille r\'ealiser les deux op\'erations {\sf find}($a$) et
{\sf delete\_min} sur un ensemble $S$, qui correspondent \`a la
recherche d'un \'el\'ement $a$ et \`a la suppression du minimum.

Pour les structures de donn\'ees suivantes indiquez si le temps
d'\'ex\'ecution des deux op\'erations {\sf find} et {\sf delete\_min} est
constant, logarithmique, lin\'eaire, exponentiel. La r\'eponse doit \^etre
aussi pr\'ecise que possible (par exemple, si le temps est
logarithmique, la r\'eponse <<lin\'eaire>> est consid\'er\'ee comme \'etant
impr\'ecise).

\begin{enumerate}
\item liste non tri\'ee, tri\'ee
\item tableau, tableau tri\'e
\item tas-min, 
\item arbre 2-3-4
\item table de hachage
\end{enumerate}
\begin{correction}

Il y une remarque particuliere a faire pour les tableau tries : il est
precise que l'on ne s'interesse qu'a find et delete. Cette remarque
permet d'enrichir le tableau avec l'indice $i$ du plus petit
element. Cette <<ruse>> permet de ne pas faire le decalage
correspondant a la suppression.  Ainsi la suppression du min se fait
en temps constant : on ne dit que $i++$, la recherche se fait de facon
dichotomique sur le reste et est donc en log.

la suppresion pour les arbre 2-3-4 n'est pas facile, et la
justification a du etre rapelle en cours.


\begin{tabular}{|l|l|l|}
\hline\\
		& find & del\_min\\
 liste non tri\'ee & n & n\\
 liste tri\'ee		& n & 1\\
 tableau		& n & n\\
 tableau tri\'e  	& log & n ou 1\\
 tas-min 		& n	& log n\\
 arbre 2-3-4		&log 	& log ?\\
 table de hachage	& 1	& n\\
\end{tabular}

\end{correction}

\end{exercice}

\begin{exercice}
Ecrivez une fonction qui \'echange l'un des minimums et l'un des
maximums dans un arbre.
\begin{correction}
\begin{verbatim}
arbre max(arbre a){
   if (a==NULL) {cout << ``erreur''; return NULL;}
   arbre x=a,y=a,rep=a;
   if (a->gauche != NULL) {
      x=max(a->gauche);
      if (x->val > a->val) rep = x;
   }
   if (a->droite != NULL) {
      y=max(a->droite);
      if (y->val > x=rep->val) rep=y;
   }
   return rep;
}
arbre min(arbre a){
   if (a==NULL) {cout << ``erreur''; return NULL;}
   arbre x=a,y=a,rep=a;
   if (a->gauche != NULL) {
      x=min(a->gauche);
      if (x->val < a->val) rep = x;
   }
   if (a->droite != NULL) {
      y=min(a->droite);
      if (y->val < x=rep->val) rep=y;
   }
   return rep;
}
arbre echange(arbre a){
 arbre m,M;
 m=min(a);
 M=max(a);
 int aux=m->val;
 m->val=M->val;
 M->val=aux;
}  
\end{verbatim}
\end{correction}
\end{exercice}


\begin{exercice}
On suppose que la racine de l'abr {a} a bien deux fils. Ecrire une
proc\'edure qui \'echange le sous arbre de racine min avec le sous
arbre de racine max. Comment faire dans le cas d'un arbre ?
\begin{correction}
\begin{verbatim}
void echange(arbre a){
 cell *pere_min=a;
 cell *pere_max=a;
 while (pere_min->gauche->gauche) pere_min=pere_min->gauche;
 while (pere_max->droite->droite) pere_max=pere_max->droite;

 cell *aux=pere_min;
 pere_min=pere_max;
 pere_max=aux;
}
\end{verbatim}
Dans le cas d'un arbre : cela n'a pas de sens d'effectuer cette operation. En effet, si l'un est sous arbre de l'autre, l'echange donne des choses aberantes non ?
\end{correction}
\end{exercice}


\begin{exercice}
Donner une version iterative d'un programme
\end{exercice}


\end{document}

