td algorithmique de graphes, miage par apprentissage

complexité

recherche d'un élément dans un tableau

On cherche le nombre x parmi les éléments t[0], t[1], ... t[n-1].

   i=0
   tant que i<n et t[i]≠x faire  // on parcourt le tableau jusqu'à ce qu'on trouve x
      i=i+1
   fait

A la fin i vaut n si et seulement si x n'est pas dans le tableau.
Si x est dans le tableau alors x=t[i].
Quels sont le nombre moyen et le nombre maximal d'itérations de la boucle dans le cas où x est dans le tableau, et dans le cas où il n'y est pas? On supposera que tous les éléments de t sont différents et que toutes les positions possibles a de x dans le tableau sont équiprobables.

	x est dans le tableau	x n'est pas dans le tableau
nombre d'itérations	a
nombre moyen
nombre maximal

recherche d'un élément dans un tableau trié, méthode bête

On cherche le nombre x parmi les éléments t[0]<t[1]< ... <t[n-1]

   i=0
   tant que i<n et t[i]<x faire  // on parcourt le tableau jusqu'à ce qu'on trouve x ou un élément plus grand que x.
      i=i+1
   fait
   si i<n et t[i]>x alors i=n    // si x n'est pas dans t

Quels sont le nombre moyen et le nombre maximal d'itérations de la boucle dans le cas où x est dans le tableau, et dans le cas où il n'y est pas ?

recherche d'un élément dans un tableau trié, par dichotomie

On cherche le nombre x parmi les éléments t[0]<t[1]< ... <t[n-1]

   i=0
   k=n
   tant que i+1<k faire       //  si x=t[a] alors a∈[i,k[
      j=[(i+k)/2]             //  [i,k[=[i,j[ u [j,k[  
      si x<t[j] alors k=j     //  On remplace [i,k[ par [i,j[
                sinon i=j     //                    ou  [j,k[    
   fait
   si i<k et t[i]≠x alors i=n  // si x n'est pas dans t

Quel est le nombre maximal d'itérations de la boucle ?
La longueur de l'intervalle [i,k[ est divisée par deux à chaque itération. Elle vaut n au début et 1 à la fin donc le nombre d'itérations est log₂ n

tri d'un tableau, par sélection

On veut permuter les éléments t[0], t[1], ... t[n-1] pour les mettre dans l'ordre croissant.

   m=n
   tant que m>0 faire
      j=0
      pour i=0,1,...,m-1 faire      // parmi les m éléments du tableau à trier, on détermine la position i du plus grand
         si t[i]>t[j] alors j=i
      fait
      echanger t[m-1] et t[j]       // on échange le plus grand et le dernier (Le plus grand est donc à sa place)
      m=m-1                         // on fait comme si le tableau avait un élément de moins
   fait

Quel est le nombre maximal d'itérations de la boucle interne ?

crible d'Erathostène

   pour i=2, 3, ..., n faire  // on initialise toutes les cases du tableau t à 1
      t[i]=1
   fait
   pour i=2, 3, ..., n faire
      si t[i]=1 alors        //  si i est premier
         j=i*i
         tant que j≤n faire
            t[j]=0           // on met 0 dans chacune des cases dont l'indice j est un multiple de i compris entre i² et n.
            j=j+i
         fait
      finsi
   fait

Exécuter cet algorithme à la main pour n=30. Combien de fois l'instruction j=j+i est-elle effectuée? Montrer que son temps de calcul est en Θ(n ln(ln(n))). Que se passe-t-il si on enlève le test "si t[i]=1" ?

   pour i=2, 3, ..., n faire
      t[i]=1
   fait
   pour i=2, 3, ..., n faire
         j=i*i
         tant que j≤n faire
            t[j]=0
            j=j+i
         fait
   fait

programmation en C

On veut programmer tous les algorithmes précédents en C. Il faudra mettre chacun des programmes dans un fichier différent.

premier programme

On commencera par faire marcher le programme suivant :


#include<stdio.h>
int main()
{ const int n=10;
  int t[10]={4,7,12,3,1,5,7,8,6,10};
  int i;
  for(i=0;i<n;++i) printf("%3d ",t[i]);
  for(i=0;i<n;++i)
  { t[i]+=3;
    printf("%3d ",t[i]);
  }
  printf("\n");
  for(i=0;i<n;++i) printf("%3d ",t[i]);
  return 0;
}

que l'on mettra dans le fichier ~/algo/afftab.c Vous devez utiliser exceed pour passer sous linux. Là vous devez ouvrir une fenêtre shell dans laquelle vous taperez les commandes :


md algo
cd algo
kate afftab.c &
gcc -g -Wall afftab.c
./a.out

La commande kate afftab.c ouvre une fenêtre dans laquelle l'éditeur de texte Kate vous permettra de voir et de modifier le fichier afftab.c contenant le programme précédent écrit en C. Le & au bout de cette commande signifie que l'on n'a pas besoin d'attendre la fin de son exécution (c'est-à-dire la fermeture de la fenêtre contenant Kate) pour lancer d'autres commandes.
Si l'appel au compilateur gcc (Gnu C Compiler, c'est-à-dire compilateur C de gnu) produit des messages d'erreur, vous devez corriger les erreurs dans le programme C, puis sauvegarder les modifications sur le disque, puis recompiler.
Si la compilation n'a pas produit de message d'erreur, elle a produit un fichier exécutable qui s'appelle par défaut a.out, que l'on peut exécuter par la commande ./a.out .
Modifier le programme afftab.c pour qu'il affiche trois lignes de dix nombres.

recherche dans un tableau non trié

Fermer la fenêtre de Kate. Dans la fenêtre shell taper les commandes

cp afftab.c recherche.c
kate recherche.c &
gcc -g -Wall recherche.c
./a.out

Le fichier recherche.c doit ressembler à :


#include<stdio.h>
int main()
{ const int n=10;
  int t[10]={4,7,12,3,1,5,7,8,6,10};
  int i,x;
  for(i=0;i<n;++i) printf("%3d ",t[i]);
  for(;;)  // boucle infinie
  { printf("Quel nombre recherchez-vous ? ");
    scanf("%d",&x);
    if(x<0) break; // On sort de la boucle infinie.
     
    // algorithme de recherche traduit en C
    
    if(i==n) printf("Le nombre %d n'est pas dans le tableau.\n",x);
    else     printf ...
  }
  return 0;
}

Faire marcher ce programme.

recherche dans un tableau trié

Dans la fenêtre shell taper la commande

cp recherche.c recherchetrie.c

puis éditer le fichier recherchetrie.c pour qu'il ressemble à :


#include<stdio.h>
int main()
{ const int n=10;
  int t[10]={4,7,12,3,1,5,7,8,6,10};
  int i,x,j,m;
  for(i=0;i<n;++i) printf("%3d ",t[i]);
  for(m=n;m>0;m--)  //  tri du tableau t
  {
    ...
  }
  ... // affichage du tableau trié
  for(;;)  // boucle infinie
  { printf("Quel nombre recherchez-vous ? ");
    scanf("%d",&x);
    if(x<0) break; // On sort de la boucle infinie.
     
    // algorithme de recherche dans un tableau trié traduit en C
    
    if(i==n) printf("Le nombre %d n'est pas dans le tableau.\n",x);
    else ...
  }
  return 0;
}

Faire marcher ce programme.

recherche dichotomique

Copier le fichier recherche.c dans dichotomie.c. Le modifier et le faire marcher.

crible d'Erathostène

Ecrire le crible d'Erathostène en C dans un fichier premiers.c qui contiendra


#include<stdio.h>
int main()
{ int n;
  printf("Jusqu'où voulez-vous chercher les nombres premiers ? ");
  scanf("%d",&n);
  { int t[n+1], i,j;
    ...
    printf("Il y a %d nombres premiers inférieurs à %d. Le plus grand d'entre eux est %d.\n",i,n,j);
   ...

Quand le programme est au point tapez les commandes

echo 10 | time ./a.out
echo 100 | time ./a.out
echo 1000 | time ./a.out
echo 10000 | time ./a.out
echo 100000 | time ./a.out
echo 1000000 | time ./a.out
echo 10000000 | time ./a.out

Noter les temps.
Pour que le programme marche efficacement pour de grandes valeurs de n, il y a des changements à faire :
1) Il faut remplacer int t[n+1]; par char t[n+1]; Ainsi le tableau t est quatre fois plus petit, car un caractère prend un octet alors qu'un entier en prend quatre.
2) Il faut insérer if(j>n) break; juste après j=i*i; De cette manière la boucle externe sur i s'arrête dès que i dépasse √n et donc j ne dépasse pas n de beaucoup. Si on ne fait pas cela, pour i=46349, j=i*i=-2146737495≤n et l'exécution de t[j]=0; provoque une exception.
3) Enfin on peut rajouter l'option -O2 à la compilation. Le compilateur optimise le code généré. La compilation est plus lente, mais l'exécution du programme est plus rapide.
Remesurer les temps d'exécution après avpoir compilé par

gcc -g -Wall -O2 premiers.c

Recommencer en remplaçant if(t[i]==1) par if(1 || t[i]==1). Le temps augmente énormément puisqu'il passe de n*ln(ln(n)) à n*ln(n). Pour n=1000000 le temps passe de 0.05s à 0.25s

fonctions et tableaux

Le fichier pp1.c contient


#include"proctab.c"
int main()
{ int n=10,t[n];
  printf("Tapez %d nombres\n",n);
  liretab(t,n);
  afftab(t,n);
  tritab(t,n);
  retourne(t,n);
  afftab(t,n);
  return 0;
}

Compléter le fichier proctab.c


#include<stdio.h>
void afftab(...
void liretab(...
void tritab(...
void retourne(...

de telle sorte qu'une exécution de pp1 ressemble par exemple à


cc -g -Wall pp1.c
./a.out
Tapez 10 nombres
23 12 4  7 2   8

 3 10 15 1
23 12 4 7 2 8 3 10 15 1
23 15 12 10 8 7 4 3 2 1

La procédure liretab(t,n) lit n nombres dans le fichier d'entrée (a priori le clavier) et les range dans t[0], t[1], ... t[n-1]. Elle n'écrit rien sur le fichier de sortie. Autrement dit elle ne contient que des scanf( ) et pas de printf( ).
La procédure afftab(t,n) écrit les n nombres t[0], t[1], ... t[n-1] dans le fichier de sortie (a priori l'écran). Elle ne lit rien dans le fichier d'entrée. Autrement dit elle ne contient que des printf( ) et pas de scanf( ).
Les procédures tritab(t,n) et retourne(t,n) ne font ni entrée ni sortie dans un fichier. Autrement dit elles ne contiennent ni scanf( ) ni printf( ). Elles permutent seulement les n nombres t[0], t[1], ... t[n-1].
tritab les range dans l'ordre croissant.
retourne échange t[0] et t[n-1], puis t[1] et t[n-2], etc..
Pour les essais, pour éviter de taper plusieurs fois les dix nombres, on peut les mettre dans un fichier nommé données par exemple par


echo 23 12 4 7 2 8 3 10 15 1 > données

près cela on peut exécuter


./a.out < données
23 12 4 7 2 8 3 10 15 1
23 15 12 10 8 7 4 3 2 1

Pour la mise au point du programme, s'il donne un résultat faux, on pourra évidemment rajouter un appel à afftab entre le tri et le retournement du tableau, pour savoir laquelle de ces deux procédures est fausse.

malloc

On veut faire marcher le programme pp2.c qui est une variante de pp1.c. Faire

cp pp1.c pp2.c

et modifier pp2.c pour qu'il contienne :

#include"proctab.c"
int main()
{ int n,*t;
  t=liretabn(&n);
  afftab(t,n);
  tritab(t,n);
  retourne(t,n);
  afftab(t,n);
  free(t);
  return 0;
}

Dans le fichier proctab.c, il faut rajouter la fonction

int *liretabn(int *adn)
...

qui doit :
demander combien de nombres on veut lire,
lire la réponse et la ranger dans n (c'est-à-dire dans *adn),
appeler malloc pour réserver la place pour un tableau de n entiers,
appeler liretab, pour ranger n nombres dans le nouveau tableau,
et enfin rendre l'adresse de ce nouveau tableau.

tri fusion récursif

Dans le programme précédent, remplacer tritab(t,n); par trifusion(t,n); et rajouter dans proctab.c les trois procédures :


void copietab(int n, int t[n], int u[n]) ... // copie t[0], t[1], ... t[n-1] dans u[0], u[1], ... u[n-1]
void fusion(int n, int p, int t[n], int u[p], int v[n+p]) ... 
void trifusion(int t[], int n)
{ if(n>1)
  { int m=n/2, p=n-m, *u=t+m;
    trifusion(t,m);
    trifusion(u,p);
    { int v[n];
      fusion(m,p,t,u,v);
      copietab(n,v,t);
    }
  }
}

La procédure fusion(n,p,t,u,v) suppose que le tableau t contient n nombres triés dans l'ordre croissant et que le tableau u contient p nombres triés dans l'ordre croissant. Elle doit intercaler ses deux suites de nombres, pour obtenir une suite croissante de n+p nombres qu'elle range dans le tableau v. Elle utilise l'algorithme suivant :

tant que les deux suites t et u sont non vides faire
   On compare le premier élément de t avec le premier élément de u.
   On prend le plus petit des deux, on l'enlève de la suite à laquelle il appartient (t ou u)
   et on le rajoute au bout de v.
fait
Si une des deux suites t ou u est non vide, on la rajoute au bout de v.

La procédure trifusion(t,n) trie les n éléments du tableau t. Pour cela on considère que tableau t de taille n=p+m, est constitué d'une première partie, t, de taille m, suivie d'une deuxième partie de taille p. On trie chacune de ces deux parties par un appel récursif. Puis on fusionne ses deux parties triées dans un nouveau tableau v de taille n. On recopie v dans t et on libère la place utilisée par le tableau v. Tout cela n'est utile que si le tableau t contient plusieurs éléments. S'il n'en contient qu'un, il est déjà trié, il n'y a rien à faire.
Quels sont les temps de calcul de copietab, fusion et trifusion ?
Montrer que lors de l'exécution de copietab(n,t,u); la boucle est effectuée n fois.
Montrer que lors de l'exécution de fusion(m,p,t,u,v);, le nombre de totale d'itérations de toutes les boucles est m+p (A chaque itération, on range un élément dans v).
On appelle f(n) le nombre totale d'itérations des boucles contenues dans fusion et copietab, effectuée lors d'un appel à trifusion(t,n). Cela représente donc le temps nécessaire pour trier un tableau de n éléments.
Montrer que f(0)=0 et que f(n)=f(n/2 arrondi à l'entier inférieur)+ f(n/2 arrondi à l'entier supérieur)+2n si n>0.
Calculer à la main, ou avec un programme, les nombres f(0), f(1), f(2), ... f(20).
Montrer que si n=2^k alors f(n)=2kn=2n log₂n.
Vérifier que f(2), f(3), f(4) sont en progression arithmétique.
Vérifier que f(4), f(5), f(6), f(7), f(8) sont en progression arithmétique.
Vérifier que f(8), f(9), f(10), f(11), f(12), f(13), f(14), f(15), f(16) sont en progression arithmétique.
En admettant que f(2^k), f(2^k+1), f(2^k+2), ... ,f(2^k+1) est une progression arithmétique, calculer f(2²⁵), f(2²⁶) et f(50 000 000).

tours de Hanoï

On dispose de trois tiges verticales et d'un certains nombres de rondelles. Les rondelles sont toutes de diamètre différent et ont un trou au centre, qui permet de les enfiler sur les tiges. On n'a pas le droit de poser une grosse rondelle sur une plus petite, cela risquerait de l'abimer.
Au début du jeu toutes les rondelles sont sur la tige de gauche. On va déplacer les rondelles une par une : Un mouvement élémentaire consiste à prendre une rondelle au sommet d'une tige, à l'enlever de cette tige et à la poser sur une autre tige, qui ne contient évidemment que des rondelles plus grosses. Le but du jeu est de mettre toutes les rondelles sur la tige de droite.
On raconte que ce jeu est pratiqué par des moines bouddhistes dans un monastère près de Hanoï. Ils ont une quarantaine de rondelles. Chaque année pour fêter le retour du printemps, ils font une grande cérémonie au cours de laquelle ils déplacent une rondelle. Selon eux, lorsqu'ils auront placé toutes les rondelles sur la tige de droite, ce sera la fin du monde.
En fait, pour déplacer les n plus petites rondelles de la tige A vers la tige B, en les posant parfois temporairement sur la tige C, il suffit de
1) faire d'abord une suite de mouvements élémentaires qui amèneront les n-1 plus petites rondelles sur la tige C,
2) puis déplacer la rondelle numéro n de la tige A à la tige B,
3) et enfin faire une suite de mouvements élémentaires qui amèneront les n-1 plus petites rondelles sur la tige B.
Bien sûr si n vaut zéro, il n'y a rien à faire.

déplacer les 3 plus petites rondelles de la tige A à la tige C	déplacer les 2 plus petites rondelles de la tige A à la tige B	déplacer la plus petite rondelle de la tige A à la tige C	déplacer 0 rondelle de la tige A à la tige B
			R1 va de A à C
			déplacer 0 rondelle de la tige B à la tige C
		R2 va de A à B
		déplacer la plus petite rondelle de la tige C à la tige B	déplacer 0 rondelle de la tige C à la tige A
			R1 va de C à B
			déplacer 0 rondelle de la tige A à la tige B
	R3 va de A à C
	déplacer les 2 plus petites rondelles de la tige B à la tige C	déplacer la plus petite rondelle de la tige B à la tige A	déplacer 0 rondelle de la tige B à la tige C
			R1 va de B à A
			déplacer 0 rondelle de la tige C à la tige A
		R2 va de B à C
		déplacer la plus petite rondelle de la tige A à la tige C	déplacer 0 rondelle de la tige A à la tige B
			R1 va de A à C
			déplacer 0 rondelle de la tige B à la tige C

On peut donc écrire une procédure hanoi(A,B,C,n) qui affiche la liste des mouvements élémentaires nécessaires pour déplacer les n plus petites rondelles de la tige A vers la tige B. Dans la description précédente la première et la troisième étapes se feront par des appels récursifs :

typedef char *tige;
void hanoi(tige depart,tige arrivee,tige autre,int n)
{
  if(n>0)
  {
    hanoi(
    printf(
    hanoi(
  }
}
int main()
{
  hanoi("la tige de gauche","la tige de droite","la tige du milieu",4);
  return 0;
}

Le programme précédent doit écrire

La rondelle 1 va de la tige de gauche à la tige du milieu
La rondelle 2 va de la tige de gauche à la tige de droite
La rondelle 1 va de la tige du milieu à la tige de droite
La rondelle 3 va de la tige de gauche à la tige du milieu
La rondelle 1 va de la tige de droite à la tige de gauche
La rondelle 2 va de la tige de droite à la tige du milieu
La rondelle 1 va de la tige de gauche à la tige du milieu
La rondelle 4 va de la tige de gauche à la tige de droite
La rondelle 1 va de la tige du milieu à la tige de droite
La rondelle 2 va de la tige du milieu à la tige de gauche
La rondelle 1 va de la tige de droite à la tige de gauche
La rondelle 3 va de la tige du milieu à la tige de droite
La rondelle 1 va de la tige de gauche à la tige du milieu
La rondelle 2 va de la tige de gauche à la tige de droite
La rondelle 1 va de la tige du milieu à la tige de droite

On peut mieux voir comment se déroule l'exécution du programme précédent en le rendant plus bavard :

typedef char *tige;
void hanoi(tige depart,tige arrivee,tige autre,int n)
{
  printf("%*s\e[31mdebut de hahoi(%s,%s,%s,%d)\e[30m\n",3*(4-n),"",depart,arrivee,autre,n);
  if(n>0)
  {
    hanoi(
    printf(
    hanoi(
  }
  printf("%*s\e[31mfin de hahoi(%s,%s,%s,%d)\e[30m\n",3*(4-n),"",depart,arrivee,autre,n);
}
int main()
{
  hanoi("gauche","droite","milieu",4);
  return 0;
}

Ce programme écrit

debut de hanoi(gauche,droite,milieu,4)
   debut de hanoi(gauche,milieu,droite,3)
      debut de hanoi(gauche,droite,milieu,2)
         debut de hanoi(gauche,milieu,droite,1)
            debut de hanoi(gauche,droite,milieu,0)
            fin   de hanoi(gauche,droite,milieu,0)
            1 va de gauche à milieu
            debut de hanoi(droite,milieu,gauche,0)
            fin   de hanoi(droite,milieu,gauche,0)
         fin   de hanoi(gauche,milieu,droite,1)
         2 va de gauche à droite
         debut de hanoi(milieu,droite,gauche,1)
            debut de hanoi(milieu,gauche,droite,0)
            fin   de hanoi(milieu,gauche,droite,0)
            1 va de milieu à droite
            debut de hanoi(gauche,droite,milieu,0)
            fin   de hanoi(gauche,droite,milieu,0)
         fin   de hanoi(milieu,droite,gauche,1)
      fin   de hanoi(gauche,droite,milieu,2)
      3 va de gauche à milieu
      debut de hanoi(droite,milieu,gauche,2)
         debut de hanoi(droite,gauche,milieu,1)
            debut de hanoi(droite,milieu,gauche,0)
            fin   de hanoi(droite,milieu,gauche,0)
            1 va de droite à gauche
            debut de hanoi(milieu,gauche,droite,0)
            fin   de hanoi(milieu,gauche,droite,0)
         fin   de hanoi(droite,gauche,milieu,1)
         2 va de droite à milieu
         debut de hanoi(gauche,milieu,droite,1)
            debut de hanoi(gauche,droite,milieu,0)
            fin   de hanoi(gauche,droite,milieu,0)
            1 va de gauche à milieu
            debut de hanoi(droite,milieu,gauche,0)
            fin   de hanoi(droite,milieu,gauche,0)
         fin   de hanoi(gauche,milieu,droite,1)
      fin   de hanoi(droite,milieu,gauche,2)
   fin   de hanoi(gauche,milieu,droite,3)
   4 va de gauche à droite
   debut de hanoi(milieu,droite,gauche,3)
      debut de hanoi(milieu,gauche,droite,2)
         debut de hanoi(milieu,droite,gauche,1)
            debut de hanoi(milieu,gauche,droite,0)
            fin   de hanoi(milieu,gauche,droite,0)
            1 va de milieu à droite
            debut de hanoi(gauche,droite,milieu,0)
            fin   de hanoi(gauche,droite,milieu,0)
         fin   de hanoi(milieu,droite,gauche,1)
         2 va de milieu à gauche
         debut de hanoi(droite,gauche,milieu,1)
            debut de hanoi(droite,milieu,gauche,0)
            fin   de hanoi(droite,milieu,gauche,0)
            1 va de droite à gauche
            debut de hanoi(milieu,gauche,droite,0)
            fin   de hanoi(milieu,gauche,droite,0)
         fin   de hanoi(droite,gauche,milieu,1)
      fin   de hanoi(milieu,gauche,droite,2)
      3 va de milieu à droite
      debut de hanoi(gauche,droite,milieu,2)
         debut de hanoi(gauche,milieu,droite,1)
            debut de hanoi(gauche,droite,milieu,0)
            fin   de hanoi(gauche,droite,milieu,0)
            1 va de gauche à milieu
            debut de hanoi(droite,milieu,gauche,0)
            fin   de hanoi(droite,milieu,gauche,0)
         fin   de hanoi(gauche,milieu,droite,1)
         2 va de gauche à droite
         debut de hanoi(milieu,droite,gauche,1)
            debut de hanoi(milieu,gauche,droite,0)
            fin   de hanoi(milieu,gauche,droite,0)
            1 va de milieu à droite
            debut de hanoi(gauche,droite,milieu,0)
            fin   de hanoi(gauche,droite,milieu,0)
         fin   de hanoi(milieu,droite,gauche,1)
      fin   de hanoi(gauche,droite,milieu,2)
   fin   de hanoi(milieu,droite,gauche,3)
fin   de hanoi(gauche,droite,milieu,4)

Soit h_n le nombre de déplacements élémentaires effectués par la procédure hanoi. On a h₀=0 et h_n=2h_n-1+1. On en déduit donc que h_n=2ⁿ-1.
On constate aussi qu'un déplacement sur deux concerne la rondelle numéro 1, qui ne revient jamais en arrière : elle tourne autour des trois tiges dans le sens gauche->milieu->droite->gauche si n est pair, et dans l'autre sens si n est impair. Parmi les autres déplacements élémentaires, un sur deux concerne la rondelle 2 qui tourne dans l'autre sens que la rondelle 1. Parmi les autres déplacements élémentaires, un sur deux concerne la rondelle 3 qui tourne dans l'autre sens que la rondelle 2. Etc. . Si on numérote les déplacements élémentaires de 1 à 2ⁿ-1, alors le numéro de la rondelle déplacée est la valuation dyadique du numéro du déplacement, augmentée de 1. Par exemple le déplacement numéro 56=7x2³ concerne la rondelle numéro 3+1. C'est le quatrième déplacement de cette rondelle ( 4=(7+1)/2 ). On sait dans quel sens tourne cette rondelle, puisque cela dépend uniquement de la parité du nombre de rondelles plus grandes qu'elle. On peut donc facilement en déduire quelle tige elle quitte et quelle tige elle rejoint. On peut donc écrire un programme itératif.

fonctions

Compléter le programme :


typedef int nombre;
#define format "%d"
nombre somme(int n,nombre t[n])
...
int main()
{ int n=5;
  nombre t[]={4,2,7,3,6};
  ...
  printf("La somme des %d éléments du tableau est "format"\n",n,somme(n,t));
  printf("Le plus grand est "format"\n",maxi(n,t));
  ...
  a=4;
  b=6;
  echange(&a,&b); printf("a="format" b="format"\n",a,b);
  tri2   (&a,&b); printf("a="format" b="format"\n",a,b);
  ...

Avant le programme principal, on doit mettre des fonctions qui :
-calcule la somme des éléments d'un tableau,
-donne la valeur du plus grand élément d'un tableau,
-donne la position du plus grand élément d'un tableau,
-donne la moyenne des éléments d'un tableau,
-donne la moyenne et la variance des éléments d'un tableau,
-échange deux nombres,
-trie deux nombres,
-trie trois nombres,
-calcule le pgcd de deux entiers,
-calcule f(n) défini par f(0)=0 et f(n)=f(n/2 arrondi inférieurement)+f(n/2 arrondi supérieurement)+2n.
Le programme doit encore marcher si on remplace les deux premières lignes par


typedef int double;
#define format "%f"

Le programme principal est uniquement là pour tester les fonctions. Il doit être le plus simple possible.
Les fonctions ne doivent faire ni entrée ni sortie (Elle ne doivent contenir ni printf ni scanf).
Toute fonction peut appeler une fonction définie avant elle. Par exemple, la fonction qui calcule la moyenne et la variance peut appeler celle qui calcule la moyenne, qui elle-même peut appeler celle qui calcule la somme. La fonction qui trie deux nombres peut appeler celle qui échange deux nombres, (quand ils ne sont pas dans le bon ordre). La fonction qui trie trois nombres peut se réduire à trois appels de la fonction qui trie deux nombres.
On rappelle que la variance est la moyenne des carrés des écarts à la moyenne. C'est aussi la différence entre la moyenne des carrés et le carré de la moyenne.
La moyenne et la variance doivent être des doubles, même si les nombres sont des entiers.

tris et compilation séparée

Compléter les fichiers testtri.c trin2.c trirapide.c trifusionit.c trifusionrec.c trishell.c rechtrien.c rechdichoit.c rechdichorec.c pour que l'on puisse faire

cc -Wall -g -O2 -c trirapide.c 
cc -Wall -g -O2 -c trin2.c 
cc -Wall -g -O2 -c trifusionit.c 
cc -Wall -g -O2 -c trifusionrec.c 
cc -Wall -g -O2 -c trishell.c 
cc -Wall -g -O2 -c rechtrien.c
cc -Wall -g -O2 -c rechdichoit.c
cc -Wall -g -O2 -c rechdichorec.c
cc -Wall -g -O2 -c testri.c
cc testri.o trirapide.o rechdichoit.o
echo 100000 | time ./a.out

testtri.c contiendra :


#include<stdio.h>
#include<stdlib.h>
void tri(int n,double t[n]);
int recherche(int n,double t[n],double x);
void aff(int n,double t[n])
...
double somme(int n,double t[n])
...
int main()
{ int n;
  printf("Combien ...");
  scanf("%d",&n);
  { double t[n], s1, s2;
    int i, x=0;
    for(i=0;i<n;++i) t[i]=x=5*x+1;
    s1=somme(n,t);
    tri(n,t);
    s2=somme(n,t);
    for(i=1;i<n;++i) if(t[i-1]>=t[i]) printf("Ce n'est pas trié\n"),exit(1);
    if(s1!=s2) printf("La somme a changé\n"),exit(1);
    // test de recherche
    i=n/3;
    if(recherche(n,t,t[i])!=i) printf("recherche n'a pas trouvé %f.\n",t[i]),exit(1);
    if(recherche(n,t,99.9)!=n) printf("recherche a trouvé 99.9.\n"),exit(1);
    printf("C'est bon.\n");
  }
  return 0;
}

Les tris en n ln(n) comme le tri rapide ou le tri fusion doivent mettre moins d'une seconde pour trier un tableau de 100000 éléments. Le tri en n² doit mettre environ une minute.
L'option -O2 à la compilation divise en gros par deux le temps d'exécution.
trifusionit.c contiendra :


/*
  pour l=1, 2, 4, 8, etc tant que i<n faire
    pour j=0, 2*l, 4*l, 6*l, etc tant que j+l<n faire
      fusionner les deux morceaux t[j..j+l-1] et t[j+l..min(j+l+l,n)-1]
    fait
  fait
*/
... 
}

trishell.c contiendra :


/*
  pour tous les entiers k inférieurs à n produit d'une puissance de 2 par une puissance de 3 pris dans l'ordre décroissant faire
    pour tout les entiers i de 0 à n-k-1 faire
      si t[i]>t[i+k] alors
        echanger t[i] et t[i+k]
      finsi
    fait
  fait
*/
void tri(int n,double t[n])
{ int k,i;
  double x;
  for(k=n;--k;) if(1162261467%(k/(k&-k))==0)
  for(i=0;i+k<n;++i) if...
}

k&-k est la plus grande puissance de 2 qui divise k. Donc k/(k&-k) est le nombre obtenu en divisant k par 2 tant que l'on peut, jusqu'à ce que l'on obtienne un nombre impair. Pour savoir si ce nombre est une puissance de 3 il suffit de vérifier s'il divise 3¹⁹. On pourrait aussi appliquer l'algorithme suivant :

  pour k=n-1,n-2, ... ,3,2,1 faire
    i:=k
    tant que i est pair faire
      i/=2
    fait
    tant que i est divisible par 3 faire
      i/=3
    fait
    si i==1 alors
      pour tous les entiers i de 0 à n-k-1 faire
        si t[i]>t[i+k] alors
          echanger t[i] et t[i+k]
        finsi
      fait
   finsi
  fait

trirapide.c contiendra :


/*
  si il y a plusieurs éléments dans le tableau alors
    choisir un élément x du tableau (par exemple le premier)
    on fait pointer deb sur le premier élément du tableau
    on fait pointer fin sur le dernier élément du tableau
    tant que deb<fin faire
      on fait avancer deb jusqu'au premier élément >=x
      on fait reculer fin jusqu'au premier élément <=x
      si deb<fin alors
        on échange t[deb] et t[fin]
         on avance deb
         on recule fin
      finsi
    fait
    on trie le début du tableau t[  .. deb-1]
    on trie la fin du tableau t[fin+1.. ]
  finsi
*/
void tri(int n,double t[n])
{ if(n>1)
  { int deb=0,fin=n-1;
    double x=t[0], y;
    for(;;)
    { while(t[deb]<x) deb++;
      while(t[fin]>x) fin--;
      if(fin<=deb) break;
      y=t[fin], t[fin]=t[deb], t[deb]=y;
      fin--, deb++;
    }
//     0..deb-1    fin=deb   fin+1..n-1
//     0..deb-1=fin      deb=fin+1..n-1
    tri(deb,t);
    tri(n-fin-1,t+fin+1);
  }
}

listes chaînées

Compléter le programme suivant :

#include<stdio.h>
#include<stdlib.h>
typedef struct chainon chainon, *liste;
struct chainon{int val; liste suite;};
void aff(liste l)// affiche sur l'écran tous les éléments de la liste, itérativement
{//...
}
liste nouv(int val, liste suite)// rend un pointeur sur un nouveau noeud (alloué par malloc) contenant val et suite
[...    // par exemple  p=nouv(2,p);  ajoute 2 en tête de la liste p.
}
liste copie(liste l) {return l ? nouv(l->val,copie(l->suite)) : 0;}
int   somre(liste l) {return l ?      l->val+somre(l->suite)  : 0;}
int   somit(liste l) // même résultat que somre mais itérativement (sans appel récursif)
{//...
}
void add1(liste l) {for(;l;l=l->suite) l->val++;}
liste eipoc(liste l)// fait une copie de la liste dans l'ordre inverse, itérativement
{//...
}
liste retourne(liste l)// retourne la liste en gardant les mêmes chaînons, itérativement
{//...
}
void retour(liste *l) {*l=retourne(*l);}
void affrec(liste l) // affiche sur l'écran tous les éléments de la liste, récursivement
{/*...*/}
void ffa   (liste l) // affiche la liste à l'envers
{/*...*/}
typedef struct {liste tete,fin;} lliste;
// tete pointe sur le premier chainon et fin sur le dernier.
// La liste est vide ssi tete==0, et dans ce cas fin n'est pas défini.
void ajoutetete(lliste *a,int x)
{ //..
}
void ajoutefin(lliste *a,int x)
{ //..
}
int enlevetete(lliste *a,int *x)
{ //..
}
liste fusionrec(liste a,liste b) // fusionne les liste a et b, qui sont déjà triées en une liste triée, en réutilisant les mêmes chainons
{ //..
}
liste fusionit(liste a,liste b)
{ //..
}
liste trifusion(liste l)
{ liste p=0,r=0;
  while(l)
  { liste q=l; l=q->suite, // on enleve un chainon q en tete de l
    q->suite=p, p=r, r=q;  // on le met en tete de p, puis on echange p et r
  }
  return !p ? r : fusion(trifusion(p),trifusion(r));
}
int main(){ liste l=nouv(3,nouv(7,nouv(5,nouv(1,0)))), k=copie(l), m=l;
  affrec(l), ffa(l), printf("\n");
  aff(l), aff(k), aff(m);
  printf("%d=%d\n",somre(l),somit(l));
  add1(l);
  aff(l), aff(k), aff(m=eipoc(m));
  lliste ll={0,0};
  int x,y;
  for(x=0;x<10;x++) (x&1 ? ajoutetete : ajoutefin)(&ll,x), aff(ll.tete);
  while(enlevetete(&ll,&x) && enlevetete(&ll,&y)) ajoutefin(&ll,x+y-3), aff(ll.tete);
  for(x=1;x;x=(x*2+1)%11) l=nouv(x,l);
  aff(l);
  retour(&l);
  aff(l);
  aff(l=trifusion(l));
  return 0;
}

corrigé

représentation des graphes

On a deux façons de représenter un graphe (non orienté) :
par la liste de toutes ses arètes : un tableau d'arètes,
en donnant la liste de voisins de chaque sommet (une liste par sommet) : un tableau de listes chaînées.
On veut écrire les procédures qui passent d'une représentation à l'autre.

#include<stdio.h>
#include<stdlib.h>
typedef struct arete{int origine,extremite;} arete;
typedef struct chainon *listesom;
struct chainon{int s; listesom suite;};

listesom nouv(int s,listesom suite)
{ listesom a=malloc(sizeof(*a));
  a->s=s;
  a->suite=suite;
  return a;
}

void cherchevoisins(int n,int a, arete ar[a], listesom voisins[n])// construit voisins
{ int i;
  for(i=0;i<n;i++) voisins[i]=0;
  for(i=0;i<a;i++)
  { int s=ar[i].origine, t=ar[i].extremite;
    voisins[s]=nouv(t,voisins[s]);
    voisins[t]=nouv(s,voisins[t]);
  }
}

int main()
{ int n=4, a=5;
  arete ar[]={{0,1},{1,2},{2,3},{3,0},{2,0}};
  listesom voisins[n];
  cherchevoisins(n,a,ar,voisins);
  { int i;
    listesom p;
    for(i=0;i<n;i++)
    { printf("%d a pour voisins :",i);
      for(p=voisins[i];p;p=p->suite) printf(" %d",p->s);
      printf("\n");
    }
  }
  return 0;
}

Si le graphe est orienté, on peut construire pour chaque sommet la liste de ses successeurs et la liste de ses prédécesseurs.

#include<stdio.h>
#include<stdlib.h>
typedef struct arete{int origine,extremite;} arete;
typedef struct chainon *listesom;
struct chainon{int s; listesom suite;};

listesom nouv(int s,listesom suite)
{ listesom a=malloc(sizeof(*a));
  a->s=s;
  a->suite=suite;
  return a;
}

void succpred(int n,int a, arete ar[a], listesom succ[n], listesom pred[n])// construit voisins
{ int i;
  for(i=0;i<n;i++) succ[i]=pred[i]=0;
  for(i=0;i<a;i++)
  { int s=ar[i].origine, t=ar[i].extremite;
    succ[s]=nouv(t,succ[s]);
    pred[t]=nouv(s,pred[t]);
  }
}

void affliste(listesom a) {for(;a;a=a->suite) printf(" %d",a->s);}

int main()
{ int n=4, a=5;
  arete ar[]={{0,1},{1,2},{2,3},{3,0},{2,0}};
  listesom succ[n],pred[n];
  succpred(n,a,ar,succ,pred);
  { int i;
    for(i=0;i<n;i++)
    { printf("%d a pour successeurs :",i); affliste(succ[i]); 
      printf(" et pour prédécesseurs :" ); affliste(pred[i]); 
      printf("\n");
    }
  }
  return 0;
}

Pour chercher tous les sommets que l'on peut atteindre à partir du sommet s0 on peut appliquer l'algorithme suivant

  on marque s0
  l={s0}
  tant que l n'est pas vide
     on enlève un élément x de l
     pour chacun des successeurs y de x faire
       si y n'est pas marqué alors
         on marque y
         on ajoute y à l
       finsi
     fait
  fait

l est la liste des sommets que l'on a marqués, mais dont on n'a pas encore marqué les successeurs.
On peut faire cela sans utiliser la liste l, avec une procédure récursive qui marque un sommet et s'appelle récursivement pour tous les successeurs de ce sommet non encore marqués.

#include<stdio.h>
#include<stdlib.h>
typedef struct arete{int origine,extremite;} arete;
typedef struct chainon *listesom;
struct chainon{int s; listesom suite;};

listesom nouv(int s,listesom suite)
{ listesom a=malloc(sizeof(*a));
  a->s=s;
  a->suite=suite;
  return a;
}

void succpred(int n,int a, arete ar[a], listesom succ[n], listesom pred[n])// construit voisins
{ int i;
  for(i=0;i<n;i++) succ[i]=pred[i]=0;
  for(i=0;i<a;i++)
  { int s=ar[i].origine, t=ar[i].extremite;
    succ[s]=nouv(t,succ[s]);
    pred[t]=nouv(s,pred[t]);
  }
}

void affliste(listesom a) {for(;a;a=a->suite) printf(" %d",a->s);}

void parcours(int c, listesom succ[], int marque[])
{ listesom p;
  marque[c]=1;
  for(p=succ[c];p;p=p->suite) if(!marque[p->s]) parcours(p->s,succ,marque);
}

int main()
{ int n=4, a=5;
  arete ar[]={{0,1},{1,2},{2,3},{3,0},{2,0}};
  listesom succ[n],pred[n];
  succpred(n,a,ar,succ,pred);
  { int i;
    for(i=0;i<n;i++)
    { printf("%d a pour successeurs :",i); affliste(succ[i]); 
      printf(" et pour prédécesseurs :" ); affliste(pred[i]); 
      printf("\n");
    }
  }
  { int i, marque[n];
    for(i=0;i<n;i++) marque[i]=0;
    parcours(i=2,succ,marque);
    printf("A partir du sommet %d on peut atteindre les sommets",i);
    for(i=0;i<n;i++) if(marque[i]) printf(" %d",i);
    printf("\n");
  } 
  return 0;
}

révisions


#include<stdio.h>
#include<stdlib.h>

int f1(int n,int p)
{ return p<0   ? 0               :
         2*p>n ? f1(n,n-p)       :
         p     ? f1(n-1,p-1)*n/p :
                 1;
}

int f2(int n,int p)
{ return p<0 || p>n ? 0                     :
         n          ? f2(n-1,p)+f2(n-1,p-1) :
                      1;
}

int f3(int n,int p)
{ if(n-p<p) p=n-p;
  if(p<0) return 0;
  { int t[p+1], i,j;
    for(i=0;i<=p;i++) t[i]=0;
    t[0]=1;
    for(j=n;j;j--) for(i=p;i;i--) t[i]+=t[i-1];
    return t[p];
  }
}

typedef struct chainon *liste;
struct chainon{int x; liste suite;};
typedef struct {liste tete,queue;} lliste;

liste nouv(int x,liste suite)
{ liste a=malloc(sizeof(*a));
  a->x=x;
  a->suite=suite;
  return a;
}

void ajt(lliste *a,int x)
{ a->tete=nouv(x,a->tete);
  if(!a->tete->suite) a->queue=a->tete;
}

void ajq(lliste *a,int x)
{ if(a->tete) a->queue=a->queue->suite=nouv(x,a->queue);
  else        a->queue=a->tete        =nouv(x,0);
}

int pop(lliste *a)
{ liste t=a->tete;
  int x=t->x;
  a->tete=t->suite;
  free(t);
  return x;
}

int main()
{ lliste a={0,0};
  int t[]={ 4 , 8 , 3 , 2 , 7 },x,y,i;
  int n=14,p=10;
  printf("%d %d %d\n",f1(n,p),f2(n,p),f3(n,p));
  for(i=0;i<5;i++) ajq(&a,t[i]);
  for(i=0;i<4;i++) x=pop(&a), y=pop(&a),
    printf("%d+%d=%d\n",x,y,x+y), ajq(&a,x+y);
  return 0;
}

1) Qu'écrit ce programme quand on l'exécute ?
2) Indiquez tous les appels de fonctions et toutes les opérations (*, /, + et -) faits lors du calcul de f1(4,2), f2(4,2) et f3(4,2). Donnez les valeurs successives de t à chaque itération de la boucle sur j.
3) Donnez un équivalent simple du temps de calcul des fonctions f1(n,p), f2(n,p) et f3(n,p). Justifiez cette réponse. (Expliquez comment vous l'avez trouvée).
4) Ecrivez une version non récursive de f1.
5) Qu'écrit le programme si on met for(i=0;i<5;i++) ajt(&a,t[i]); à la place de for(i=0;i<5;i++) ajq(&a,t[i]); ?
6) Ecrivez une fonction int popq(lliste *a) qui enlève le dernier chaînon de la liste. Quel est son temps de calcul ? (Vous pouvez l'écrire en pseudo-langage, si vous n'y arrivez pas en C).

parcours (en largeur ou profondeur) d'un graphe

La procédure suivante parcourt tous les sommets d'un graphe orienté donné, que l'on peut atteindre à partir d'un sommet donné.

procédure parcours_en_profondeur_ou_largeur_d'abord(s:sommet)
  pour chacun des sommets i faire
     on note que i n'a pas encore été visité    O(n)
  fait
  l=(s)     // liste des sommets déjà visités, dont on n'a pas encore visité les successeurs
  on note que s a été visité
  tant que l n'est pas vide faire
     Soit i le dernier ou le premier élément de l.
     Si i a un successeur j qui n'a pas encore été visité alors  O(a)
       on ajoute j à la fin de l     O(n)
       on note que j a été visité    O(n)
     sinon
       en enlève i de l 
     finsi
  fait
fin procédure

Autrement dit, on part d'une liste qui au début ne contient que le sommet de départ. Puis tant que la liste n'est pas vide si le prochain élément à examiner à encore un successeur qui n'est pas encore rentré dans la liste, alors on ajoute ce successeur à la liste, sinon on enlève ce prochain de la liste.

temps de calcul

On n'insère jamais deux fois le même sommet dans la liste. Donc l'instruction "on ajoute j à la fin de l" est faite au plus une fois pour chaque valeur de j. Elle est donc faite un nombre de fois inférieur au nombre n de sommets.
Pour chaque sommet i visité, on ne regarde qu'une fois chacun de ses successeurs j. Le nombre de couples (i,j) considérés, est donc inférieur au nombre a d'arcs du graphe.

écriture en C

La taille de la liste l ne dépasse jamais le nombre de sommets du graphe. On peut donc facilement gérer la liste l en utilisant un tableau de taille n.
On supposera qu'il existe n sommets numérotés de 0 à n-1. On peut donc regrouper dans un tableau de n éléments tous les booléens indiquant si on a visité un sommet ou non. De même, pour chaque sommet on a la liste chaînée des successeurs de ce sommet. Ces n listes peuvent être regroupées dans un tableau.
Dans le programme C suivant, pour que les procédures itératives de parcours ressemblent plus à la procédure récursive vue précédemment, on passe le tableau marque en argument, et l'initialisation de ce tableau est sortie de la procédure.

#include<stdio.h>
#include<stdlib.h>
typedef struct arete{int origine,extremite;} arete;
typedef struct chainon *listesom;
struct chainon{int s; listesom suite;};

listesom nouv(int s,listesom suite)
{ listesom a=malloc(sizeof(*a));
  a->s=s;
  a->suite=suite;
  return a;
}

void succpred(int n,int a, arete ar[a], listesom succ[n], listesom pred[n])// construit voisins
{ int i;
  for(i=0;i<n;i++) succ[i]=pred[i]=0;
  for(i=0;i<a;i++)
  { int s=ar[i].origine, t=ar[i].extremite;
    succ[s]=nouv(t,succ[s]);
    pred[t]=nouv(s,pred[t]);
  }
}

void affliste(listesom a) {for(;a;a=a->suite) printf(" %d",a->s);}

void parcours(int c, listesom succ[], int marque[])   //  récursif en profondeur d'abord
{ listesom p;
  marque[c]=1;
  for(p=succ[c];p;p=p->suite) if(!marque[p->s]) parcours(p->s,succ,marque);
}

void parcours_ite_prof(int s, listesom succ[], int n, int marque[n])   //  itératif en profondeur d'abord
{ listesom p;
  int l[n], nl,i,j;
  marque[s]=1;    // on note que s a été visité
  l[0]=s, nl=1;   // l=(s)
  while(nl)       // tant l n'est pas vide
  { i=l[nl-1];    // on met dans i le dernier élément de l
    for(p=succ[i];p && marque[p->s];p=p->suite) ;  // On cherche le prochain successeur de i non visité.
    succ[i]=p;
    if(p) marque[l[nl++]=p->s]=1; //  on note que ce successeur a été visité et on l'ajoute la fin de la liste l
    else  nl--;                   //  on enlève i de la liste l
  }               // fait
}

void parcours_ite_larg(int s, listesom succ[], int n, int marque[n])   //  itératif en largeur d'abord
{ listesom p;
  int l[n], dl,fl,i,j;
  marque[s]=1;       // on note que s a été visité
  l[0]=s, dl=0, fl=1;// l=(s)
  while(dl<fl)       // tant l n'est pas vide
  { i=l[dl++];       // on enlève le premier élément de l et on le met dans i
    for(p=succ[i];p;p=p->suite)  // pour chaque successeur j (=p->s) de i faire
     if(!marque[j=p->s])         //     si j n'a pas encore été visité alors
    { marque[j]=1;               //         on note que j a été visité
      l[fl++]=j;                 //         on ajoute j à la fin de la liste l
    }                            //     finsi fait
  }                  // fait
}

int main()
{ int n=4, a=5;
  arete ar[]={{0,1},{1,2},{2,3},{3,0},{2,0}};
  listesom succ[n],pred[n],suc[n];
  succpred(n,a,ar,succ,pred);
  { int i;
    for(i=0;i<n;i++)
    { printf("%d a pour successeurs :",i); affliste(succ[i]); 
      printf(" et pour prédécesseurs :" ); affliste(pred[i]); 
      printf("\n");
    }
  }
  { int i, marque[n],k;
    for(k=0;k<3;k++)
    { for(i=0;i<n;i++) marque[i]=0, suc[i]=succ[i];
      i=2;
      switch(k)
      { case 0:parcours         (i,succ,  marque); break;
        case 1:parcours_ite_prof(i,suc ,n,marque); break;
        case 2:parcours_ite_larg(i,succ,n,marque); break;
      }   
      printf("A partir du sommet %d on peut atteindre les sommets",i);
      for(i=0;i<n;i++) if(marque[i]) printf(" %d",i);
      printf("\n");
    }
  } 
  return 0;
}

Dans le programme pécédent on peut modifier la procédure de parcours en largeur d'abord, pour lui faire calculer la distance du sommet de départ à chacun des autres sommets et construire un arbre formé de chemins de longueur minimale allant du sommet de départ à chacun des autres sommets.


void parcours_ite_larg(int s, listesom succ[], int n, int marque[n],int pere[n], int dist[n])   //  récursif en largeur d'abord
{ listesom p;
  int l[n], dl,fl,i,j;
  marque[s]=1;       // on note que s a été visité
  l[0]=s, dl=0, fl=1;// l=(s)
  pere[s]=-1, dist[s]=0;// s n'a pas de père puisque c'est la racine de l'arbre, la distance de s à s et 0.
  while(dl<fl)       // tant l n'est pas vide
  { i=l[dl++];       // on enlève le premier élément de l et on le met dans i
    for(p=succ[i];p;p=p->suite)  // pour chaque successeur j (=p->s) de i faire
     if(!marque[j=p->s])         //     si j n'a pas encore été visité alors
    { marque[j]=1;               //         on note que j a été visité
      l[fl++]=j;                 //         on ajoute j à la fin de la liste l
      dist[j]=dist[i]+1, pere[j]=i;
    }                            //     finsi fait
  }                  // fait
}

int main()
{ int n=4, a=5;
  arete ar[]={{0,1},{1,2},{2,3},{3,0},{2,0}};
  listesom succ[n],pred[n];
  succpred(n,a,ar,succ,pred);
  { int i;
    for(i=0;i<n;i++)
    { printf("%d a pour successeurs :",i); affliste(succ[i]); 
      printf(" et pour prédécesseurs :" ); affliste(pred[i]); 
      printf("\n");
    }
  }
  { int d=2, i, marque[n],k,pere[n],dist[n];
    for(k=0;k<3;k++)
    { for(i=0;i<n;i++) marque[i]=0;
      switch(k)
      { case 0:parcours         (d,succ,  marque); break;
        case 1:parcours_ite_prof(d,succ,n,marque); break;
        case 2:parcours_ite_larg(d,succ,n,marque,pere,dist); break;
      }   
      printf("A partir du sommet %d on peut atteindre les sommets",i);
      for(i=0;i<n;i++) if(marque[i]) printf(" %d",i);
      printf("\n");
    }
    k=1;
    printf("Le chemin le plus court de %d à %d (à l'envers) est :",d,k);
    for(;k>=0;k=pere[k]) printf(" %d",k);
    printf("\n");
  } 
  return 0;
}