Pascal, premier semestre, DEUG deuxième année, MASS 2004--2005

lundi 4 octobre et mercredi 6 octobre 2004 : portée des identificateurs et évolution de la pile
lundi 11 octobre 2004 fonctions récursives
lundi 18 octobre 2004 tours de Hanoï
lundi 25 octobre 2004 tri par fusion récursif
lundi 8 novembre 2004 : analyse de la complexité des algorithmes
lundi 15 novembre 2004 : crible d'Eratosthène
lundi 22 novembre 2004 : nombres amis
lundi 29 novembre 2004 : pointeurs et listes chaînées
lundi 6 décembre 2004 : listes chaînées
lundi 13 décembre 2004 : tri fusion de listes chaînées
lundi 3 janvier 2005 : pile et file d'attente
lundi 10 janvier 2005 : fonction d'Ackermann

suivant sommaire

lundi 4 octobre et mercredi 6 octobre 2004 : portée des identificateurs et évolution de la pile

program pp;
function fact(n:integer):integer;
var i,p:integer;
begin
  p:=1;
  for i:=1 to n do p:=p*i;
  fact:=p
end;
function binomiale(n,i:integer):integer;
begin
  binomiale:=fact(n) div fact(i) div fact(n-i)
end;
const n=3;
var i:integer;
begin
  for i:=0 to n do write(binomiale(n,i):4);
  readln
end.

Le programme précédent écrit :

    1   3   3   1

Le programme principal affiche une ligne du triangle de Pascal, en appelant quatre fois la fonction binomial( , ) qui appelle elle même trois fois la fonction fact( ), qui est donc appelée douze fois en tout. En fait on calclue 6 fois fact(3), 2 fois fact(2), 2 fois fact(1) et 2 fois fact(0). L'instruction p:=p*i est exécutée 24 fois.
On peut regarder l'évolution du contenu de la pile, qui contient toutes les variables des procédures en cours d'exécution, et les adresses de retour à la fin de l'exécution de ces procédures.
Dans le programmes précédents, les fonctions n'utilisent aucune variable globale et ont tous leur arguments passés par valeur. Donc elles ne modifient pas la valeur des variables qui existaient avant leur appel. Elles sont donc propres.
suivant précédent sommaire

lundi 11 octobre 2004 fonctions récursives

On peut calculer le pgcd de deux nombres en utilisant les relations pgcd(a,b)=pgcd(a-b,b)=pgcd(a,b-a) pour se ramener à des nombres plus petits. Cela donne par exemple :
pgcd(35,49)=pgcd(35,49-35)=pgcd(35,14)=pgcd(35-14,14)=pgcd(21,14)=pgcd(21-14,14)=pgcd(7,14)=pgcd(7,14-7)=pgcd(7,7)=7
On peut traduire cet algorithme par la fonction suivante, qui est récursive, c'est-à-dire qui s'appelle elle-même.

function pgcd(a,b:integer):integer;
begin
  if a=0 then pgcd:=b else
  if b=0 then pgcd:=a else
  if a=b then pgcd:=a else
  if a<b then pgcd=pgcd(a,b-a)
         else pgcd=pgcd(a-b,b)
end;

Cette façon de procéder peut être très lente dans certains cas :
pgcd(10001,3)=pgcd(9998,3)=pgcd(9995,3)=pgcd(9992,3)=...=pgcd(8,3)=pgcd(5,3)=pgcd(2,3)=pgcd(2,1)=pgcd(1,1)=1
On peut l'améliorer nettement en utilisant le reste de la division du plus grand nombre par le plus petit au lieu de leur différence. pgcd(a,b)=pgcd(a mod b,b)=pgcd(a,b mod a) Les deux exemples précédents deviennent :
pgcd(35,49)=pgcd(35,14)=pgcd(7,14)=pgcd(7,0)=7 pgcd(10001,3)=pgcd(2,3)==pgcd(2,1)=pgcd(0,1)=1

function pgcd(a,b:integer):integer;
begin
  if a=0 then pgcd:=b else
  if b=0 then pgcd:=a else
  if a=b then pgcd:=a else
  if a<b then pgcd=pgcd(a,b mod a)
         else pgcd=pgcd(a mod b,b)
end;

La règle pgcd(a,a)=a n'est plus jamais utilisée récursivement. Elle n'est utilisée que dans le cas où on calcule le pgcd d'un nombre et de lui même. En enlevant cette règle, on aura un calcul plus rapide dans le cas général où les deux opérandes sont différents (on gagnera le temps de la comparaison de a et b, et sinon on aura un calcul un petit peu plus long mais qui marche quand même. On fera pgcd(10,10)=pgcd(10,0)=10.

function pgcd(a,b:integer):integer;
begin
  if a=0 then pgcd:=b else
  if b=0 then pgcd:=a else
  if a<b then pgcd=pgcd(a,b mod a)
         else pgcd=pgcd(a mod b,b)
end;

Dans les calculs précédents, on remplace le plus grand des deux nombres par son reste modulo l'autre, qui est un nombre strictement plus petit que le diviseur. Donc le plus grand des deux nombres est alternativement, le premier, puis le second, puis le premier, etc. . Si après avoir remplacé le plus grand des deux nombres par son reste dans la division par l'autre, on échange les deux nombres, alors le plus grand sera toujours le premier (ou le second comme on veux). On peut donc écrire la fonction en supposant que son premier argument est toujours le plus grand. Cela gagne la moitié des cas. Il n'y a plus que deux cas au lieu de quatre, et donc un seul if :

function pgcd(a,b:integer):integer;
begin
  if b=0 then pgcd:=a
         else pgcd=pgcd(b,a mod b)
end;

Cette fonction marche dans le cas où a≥b. Par exemple :
pgcd(49,35)=pgcd(35,14)=pgcd(14,7)=pgcd(7,0)=7 pgcd(10001,3)=pgcd(3,2)==pgcd(2,1)=pgcd(1,0)=1
Mais elle marche aussi si a<b :
pgcd(35,49)=pgcd(49,35 mod 49)=pgcd(49,35)=pgcd(35,14)=pgcd(14,7)=pgcd(7,0)=7
En effet quand on divise 35 par 49 le quotient est 0 et le reste est 35. (35=0*49+35)
Si on n'échange pas les deux nombres la fonction ne marche pas :

function pgcd(a,b:integer):integer;
begin
  if b=0 then pgcd:=a
         else pgcd=pgcd(a mod b,b)
end;

donne en effet :pgcd(49,35)=pgcd(14,35)=pgcd(14,35)=pgcd(14,35)=...
La récursivité ne s'arrête jamais. La pile d'exécution déborde et le programme se termine en erreur, après un certain temps.
Toutes les explications précédentes s'appliquent si on ne considère que des nombres entiers positifs. Mais en fait la fonction pgcd précédente marche aussi avec des nombres négatifs, par exemple :
pgcd(49,-35)=pgcd(-35,14)=pgcd(14,-7)=pgcd(-7,0)=-7 pgcd(-49,35)=pgcd(35,-14)=pgcd(-14,7)=pgcd(7,0)=7 pgcd(-49,-35)=pgcd(-35,-14)=pgcd(-14,-7)=pgcd(-7,0)=-7 En effet mod donne un résultat du même signe que le dividende sans tenir compte du signe du diviseur. La fonction pgcd rend donc un résultat qui est du signe d'un de ses deux arguments, le premier ou le second, suivant que le nombre d'appels récursifs est pair ou impair. On peut donc améliorer cela en rendant toujours un résultat positif :

function pgcd(a,b:integer):integer;
begin
  if b=0 then pgcd:=abs(a)
         else pgcd=pgcd(a mod b,b)
end;

version itérative

Au lieu de faire un appel récusrsif ``terminal'' (c'est la dernière instruction de la fonction au niveau d'appel courant) qui va donner le résultat de la fonction en utilisant d'autres variables dans la pile au niveau d'appel suivant, on peut remplacer les deux arguments a et b par les valeurs des arguments du niveau d'appel suivant (b et a mod b) et retourner au début de la procédure :

function pgcd(a,b:integer):integer;
label debut;
begin
  debut:
  if b=0 then pgcd:=abs(a)
         else begin a:=a mod b; échanger a et b; goto debut end
end;

Au lieu de mettre un if dont un des cas se termine par un retour sur ce if, il vaut évidemment mieux mettre un while

function pgcd(a,b:integer):integer;
begin
  while b<>0 do
  begin
    a:=a mod b;
    échanger a et b
  end;
  pgcd:=abs(a)
end;

L'échange des valeurs de a et b se fait en utilisant une troisième variable.

function pgcd(a,b:integer):integer;
var c:integer;
begin
  while b<>0 do
  begin
    c:=a mod b;
    a:=b;
    b:=c
  end;
  pgcd:=abs(a)
end;

somme des n premiers éléments d'un tableau

type tab=array[1..100] of integer;
fuction sommeit(var t:tab;n:integer):integer; (* version itérative *)
var i,s:integer;
begin
  s:=0;
  for i:=1 to n do s:=s+t[i];
  sommeit:=s
end;
fuction sommere(var t:tab;n:integer):integer; (* version récursive *)
begin
  if n&lt;=0 then sommere:=0
          else sommere:=t[n]+sommere(t,n-1)
end;

suivant précédent sommaire

lundi 18 octobre 2004

const n=20;
type tab=array[1..n] of integer;

function sommere(var t:tab;n:integer):integer;
begin
  if n=0 then sommere:=0
         else sommere:=t[n]+sommere(t,n-1)
end;

function sommeit(var t:tab;n:integer):integer;
var i,s:integer;
begin
  s:=0;
  for i:=1 to n do s:=s+t[i];
  sommeit:=s
end;

procedure initab(var t:tab;t0,pas:integer);
var i:integer;
begin
  for i:=1 to n do t[i]:=(t0+pas*i) mod 11
end;

procedure afftab(var t:tab);
var i:integer;
begin
  for i:=1 to n do write(t[i],' ');
  writeln
end;

function produitre(var t:tab;n:integer):integer;
begin
  if n=0 then produitre:=1
         else produitre:=t[n]*produitre(t,n-1)
end;

function produitit(var t:tab;n:integer):integer;
var i,s:integer;
begin
  s:=1;
  for i:=1 to n do s:=s*t[i];
  produitit:=s
end;

function max2(a,b:integer):integer;
begin
  if a<b then max2:=b
         else max2:=a
end;

function maxre(var t:tab;n:integer):integer;
begin
  if n=1 then maxre:=     t[1]
         else maxre:=max2(t[n],maxre(t,n-1))
end;

function maxit(var t:tab;n:integer):integer;
var i,s:integer;
begin
  s:=t[1];
  for i:=2 to n do s:=max2(s,t[i]);
  maxit:=s
end;

function min2(a,b:integer):integer;
begin
  if a>b then min2:=b
         else min2:=a
end;

function minre(var t:tab;n:integer):integer;
begin
  if n=1 then minre:=     t[1]
         else minre:=min2(t[n],minre(t,n-1))
end;

function minit(var t:tab;n:integer):integer;
var i,s:integer;
begin
  s:=t[1];
  for i:=2 to n do s:=min2(s,t[i]);
  minit:=s
end;

function pgcd2(a,b:integer):integer;
begin
  if b=0 then pgcd2:=abs(a)
         else pgcd2:=pgcd2(b,a mod b)
end;

function pgcdre(var t:tab;n:integer):integer;
begin
  if n=1 then pgcdre:=      t[1]
         else pgcdre:=pgcd2(t[n],pgcdre(t,n-1))
end;

function pgcdit(var t:tab;n:integer):integer;
var i,s:integer;
begin
  s:=t[1];
  for i:=2 to n do s:=pgcd2(s,t[i]);
  pgcdit:=s
end;

function ppcm2(a,b:integer):integer;
begin
  ppcm2:=a div pgcd2(a,b) * b
end;

function ppcmre(var t:tab;n:integer):integer;
begin
  if n=1 then ppcmre:=      t[1]
         else ppcmre:=ppcm2(t[n],ppcmre(t,n-1))
end;

function ppcmit(var t:tab;n:integer):integer;
var i,s:integer;
begin
  s:=t[1];
  for i:=2 to n do s:=ppcm2(s,t[i]);
  ppcmit:=s
end;

var t:tab;
begin
  initab(t,4,3);
  afftab(t);
  writeln('somme des 3 premiers nombres : ',sommere(t,3),' ou ',sommeit(t,3));
  writeln('produit des 3 premiers nombres : ',produitre(t,3),' ou ',produitit(t,3));
  writeln('plus grand des 4 premiers nombres : ',maxre(t,4),' ou ',maxit(t,4));
  writeln('plus petit des 4 premiers nombres : ',minre(t,4),' ou ',minit(t,4));
  writeln('pgcd des 4 premiers nombres : ',pgcdre(t,4),' ou ',pgcdit(t,4));
  writeln('ppcm des 5 premiers nombres : ',ppcmre(t,5),' ou ',ppcmit(t,5));
  readln
end.

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.
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 :

type tige=string;
procedure hanoi(depart,arrivee,autre:tige;n:integer);
begin
  if n>0 then
  begin
    hanoi(depart,autre,arrivee,n-1);
    writeln('La rondelle ',n,' va de ',depart,' à ',arrivee);
    hanoi(autre,arrivee,depart,n-1)
  end
end;
begin
  hanoi('la tige de gauche','la tige de droite','la tige du milieu',4)
end.

Le programme précédent écrit

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 :

type tige=string;
procedure hanoi(depart,arrivee,autre:tige;n:integer);
begin
  writeln('':3*(4-n),'debut de hanoi(',depart,',',arrivee,',',autre,',',n,')');
  if n>0 then
  begin
    hanoi(depart,autre,arrivee,n-1);
    writeln('':3*(5-n),n,' va de ',depart,' à ',arrivee);
    hanoi(autre,arrivee,depart,n-1);
  end;
  writeln('':3*(4-n),'fin   de hanoi(',depart,',',arrivee,',',autre,',',n,')');
end;
begin
  hanoi('gauche','droite','milieu',4)
end.

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)

On peut aussi regarder l'évolution de la pile pendant l'exécution du programme :

debut de hanoi(gauche,droite,milieu,4)      pp g d m 4 
 debut de hanoi(gauche,milieu,droite,3)     pp g d m 4 h1 g m d 3 
  debut de hanoi(gauche,droite,milieu,2)    pp g d m 4 h1 g m d 3 h1 g d m 2 
   debut de hanoi(gauche,milieu,droite,1)   pp g d m 4 h1 g m d 3 h1 g d m 2 h1 g m d 1 
    debut de hanoi(gauche,droite,milieu,0)  pp g d m 4 h1 g m d 3 h1 g d m 2 h1 g m d 1 h1 g d m 0 
    fin   de hanoi(gauche,droite,milieu,0)  pp g d m 4 h1 g m d 3 h1 g d m 2 h1 g m d 1   
    1 va de gauche à milieu
    debut de hanoi(droite,milieu,gauche,0)  pp g d m 4 h1 g m d 3 h1 g d m 2 h1 g m d 1 h2 d m g 0 
    fin   de hanoi(droite,milieu,gauche,0)  pp g d m 4 h1 g m d 3 h1 g d m 2 h1 g m d 1   
   fin   de hanoi(gauche,milieu,droite,1)   pp g d m 4 h1 g m d 3 h1 g d m 2   
   2 va de gauche à droite
   debut de hanoi(milieu,droite,gauche,1)   pp g d m 4 h1 g m d 3 h1 g d m 2 h2 m d g 1 
    debut de hanoi(milieu,gauche,droite,0)  pp g d m 4 h1 g m d 3 h1 g d m 2 h2 m d g 1 h1 m g d 0 
    fin   de hanoi(milieu,gauche,droite,0)  pp g d m 4 h1 g m d 3 h1 g d m 2 h2 m d g 1   
    1 va de milieu à droite
    debut de hanoi(gauche,droite,milieu,0)  pp g d m 4 h1 g m d 3 h1 g d m 2 h2 m d g 1 h2 g d m 0 
    fin   de hanoi(gauche,droite,milieu,0)  pp g d m 4 h1 g m d 3 h1 g d m 2 h2 m d g 1   
   fin   de hanoi(milieu,droite,gauche,1)   pp g d m 4 h1 g m d 3 h1 g d m 2   
  fin   de hanoi(gauche,droite,milieu,2)    pp g d m 4 h1 g m d 3   
  3 va de gauche à milieu
  debut de hanoi(droite,milieu,gauche,2)    pp g d m 4 h1 g m d 3 h2 d m g 2 
   debut de hanoi(droite,gauche,milieu,1)   pp g d m 4 h1 g m d 3 h2 d m g 2 h1 d g m 1 
    debut de hanoi(droite,milieu,gauche,0)  pp g d m 4 h1 g m d 3 h2 d m g 2 h1 d g m 1 h1 d m g 0 
    fin   de hanoi(droite,milieu,gauche,0)  pp g d m 4 h1 g m d 3 h2 d m g 2 h1 d g m 1   
    1 va de droite à gauche
    debut de hanoi(milieu,gauche,droite,0)  pp g d m 4 h1 g m d 3 h2 d m g 2 h1 d g m 1 h2 m g d 0 
    fin   de hanoi(milieu,gauche,droite,0)  pp g d m 4 h1 g m d 3 h2 d m g 2 h1 d g m 1   
   fin   de hanoi(droite,gauche,milieu,1)   pp g d m 4 h1 g m d 3 h2 d m g 2   
   2 va de droite à milieu
   debut de hanoi(gauche,milieu,droite,1)   pp g d m 4 h1 g m d 3 h2 d m g 2 h2 g m d 1 
    debut de hanoi(gauche,droite,milieu,0)  pp g d m 4 h1 g m d 3 h2 d m g 2 h2 g m d 1 h1 g d m 0 
    fin   de hanoi(gauche,droite,milieu,0)  pp g d m 4 h1 g m d 3 h2 d m g 2 h2 g m d 1   
    1 va de gauche à milieu
    debut de hanoi(droite,milieu,gauche,0)  pp g d m 4 h1 g m d 3 h2 d m g 2 h2 g m d 1 h2 d m g 0 
    fin   de hanoi(droite,milieu,gauche,0)  pp g d m 4 h1 g m d 3 h2 d m g 2 h2 g m d 1   
   fin   de hanoi(gauche,milieu,droite,1)   pp g d m 4 h1 g m d 3 h2 d m g 2   
  fin   de hanoi(droite,milieu,gauche,2)    pp g d m 4 h1 g m d 3   
 fin   de hanoi(gauche,milieu,droite,3)     pp g d m 4   
 4 va de gauche à droite
 debut de hanoi(milieu,droite,gauche,3)     pp g d m 4 h2 m d g 3 
  debut de hanoi(milieu,gauche,droite,2)    pp g d m 4 h2 m d g 3 h1 m g d 2 
   debut de hanoi(milieu,droite,gauche,1)   pp g d m 4 h2 m d g 3 h1 m g d 2 h1 m d g 1 
    debut de hanoi(milieu,gauche,droite,0)  pp g d m 4 h2 m d g 3 h1 m g d 2 h1 m d g 1 h1 m g d 0 
    fin   de hanoi(milieu,gauche,droite,0)  pp g d m 4 h2 m d g 3 h1 m g d 2 h1 m d g 1   
    1 va de milieu à droite
    debut de hanoi(gauche,droite,milieu,0)  pp g d m 4 h2 m d g 3 h1 m g d 2 h1 m d g 1 h2 g d m 0 
    fin   de hanoi(gauche,droite,milieu,0)  pp g d m 4 h2 m d g 3 h1 m g d 2 h1 m d g 1   
   fin   de hanoi(milieu,droite,gauche,1)   pp g d m 4 h2 m d g 3 h1 m g d 2   
   2 va de milieu à gauche
   debut de hanoi(droite,gauche,milieu,1)   pp g d m 4 h2 m d g 3 h1 m g d 2 h2 d g m 1 
    debut de hanoi(droite,milieu,gauche,0)  pp g d m 4 h2 m d g 3 h1 m g d 2 h2 d g m 1 h1 d m g 0 
    fin   de hanoi(droite,milieu,gauche,0)  pp g d m 4 h2 m d g 3 h1 m g d 2 h2 d g m 1   
    1 va de droite à gauche
    debut de hanoi(milieu,gauche,droite,0)  pp g d m 4 h2 m d g 3 h1 m g d 2 h2 d g m 1 h2 m g d 0 
    fin   de hanoi(milieu,gauche,droite,0)  pp g d m 4 h2 m d g 3 h1 m g d 2 h2 d g m 1   
   fin   de hanoi(droite,gauche,milieu,1)   pp g d m 4 h2 m d g 3 h1 m g d 2   
  fin   de hanoi(milieu,gauche,droite,2)    pp g d m 4 h2 m d g 3   
  3 va de milieu à droite
  debut de hanoi(gauche,droite,milieu,2)    pp g d m 4 h2 m d g 3 h2 g d m 2 
   debut de hanoi(gauche,milieu,droite,1)   pp g d m 4 h2 m d g 3 h2 g d m 2 h1 g m d 1 
    debut de hanoi(gauche,droite,milieu,0)  pp g d m 4 h2 m d g 3 h2 g d m 2 h1 g m d 1 h1 g d m 0 
    fin   de hanoi(gauche,droite,milieu,0)  pp g d m 4 h2 m d g 3 h2 g d m 2 h1 g m d 1   
    1 va de gauche à milieu
    debut de hanoi(droite,milieu,gauche,0)  pp g d m 4 h2 m d g 3 h2 g d m 2 h1 g m d 1 h2 d m g 0 
    fin   de hanoi(droite,milieu,gauche,0)  pp g d m 4 h2 m d g 3 h2 g d m 2 h1 g m d 1   
   fin   de hanoi(gauche,milieu,droite,1)   pp g d m 4 h2 m d g 3 h2 g d m 2   
   2 va de gauche à droite
   debut de hanoi(milieu,droite,gauche,1)   pp g d m 4 h2 m d g 3 h2 g d m 2 h2 m d g 1 
    debut de hanoi(milieu,gauche,droite,0)  pp g d m 4 h2 m d g 3 h2 g d m 2 h2 m d g 1 h1 m g d 0 
    fin   de hanoi(milieu,gauche,droite,0)  pp g d m 4 h2 m d g 3 h2 g d m 2 h2 m d g 1   
    1 va de milieu à droite
    debut de hanoi(gauche,droite,milieu,0)  pp g d m 4 h2 m d g 3 h2 g d m 2 h2 m d g 1 h2 g d m 0 
    fin   de hanoi(gauche,droite,milieu,0)  pp g d m 4 h2 m d g 3 h2 g d m 2 h2 m d g 1   
   fin   de hanoi(milieu,droite,gauche,1)   pp g d m 4 h2 m d g 3 h2 g d m 2   
  fin   de hanoi(gauche,droite,milieu,2)    pp g d m 4 h2 m d g 3   
 fin   de hanoi(milieu,droite,gauche,3)     pp g d m 4   
fin   de hanoi(gauche,droite,milieu,4)

Lors de l'appel de la procédure hanoi on ajoute dans la pile l'adresse de retour suivie des quatre variables depart, arrivee, autre et n. On les enlève de la pile à la fin de l'exécution de la procédure. On utilise alors l'adresse de retour que l'on enlève de la pile pour savoir quelle est la prochaine instruction à exécuter. pp représente l'appel de hanoi situé dans le programme principal, h1 et h2 représentent les deux appels récursifs situés dans la procédure hanoi.
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. Cela donne le programme itératif suivant :

const tige:array[0..2] of string=('de gauche','de droite','du milieu');
      n=4;
var i,j:integer;
begin
  for i:=1 to 1 shl n-1 do
  begin
    j:=0;
    while not odd(i shr j) do inc(j); (* 2^j est la plus grande puissance de 2 qui divise i *)
    writeln('La rondelle ',j+1,' va de la tige ',tige[(i-1 shl j) shl (1 and n) mod 3],
                                   ' à la tige ',tige[(i+1 shl j) shl (1 and n) mod 3])
  end
end.

suivant précédent sommaire

lundi 25 octobre 2004 tri par fusion récursif

fusion et tri

On veut trier un tableau d'entiers, c'est-à-dire les permuter pour les mettre dans l'ordre croissant. On peut faire pour cela une suite de ``fusions'' de parties déjà triées. Pour fusionner deux listes triées en une nouvelle liste triée on peut appliquer l'algorithme suivant :
Tant qu'aucune des deux listes n'est vide, on compare le premier élément de la première liste avec le premier élément de la deuxième liste. On l'enlève de la liste où il était et on le rajoute à la fin de la nouvelle liste. Quand une des listes est vide on met l'autre à la fin de la nouvelle liste.

 1 5 9 12
 2 4 6 7
 -

 5 9 12
 2 4 6 7
 1

 5 9 12
 4 6 7
 1 2

 5 9 12
 6 7
 1 2 4

 9 12
 6 7
 1 2 4 5

 9 12
 7
 1 2 4 5 6

 9 12
 -
 1 2 4 5 6 7

 12
 -
 1 2 4 5 6 7 9

 -
 -
 1 2 4 5 6 7 9 12

tri récursif

Le tri peut se faire récursivement : pour trier un tableau de plusieurs nombres (t[d..f]), on le coupe en deux morceaux qui ont à peu près la même longueur (t[d..m]) et (t[m+1..f]) en prenant m=(d+f)div 2. On trie chacun des deux morceaux (par un appel récursif) puis on fusionne les deux morceaux.
Dans le programme suivant la procédure fusion(a,b,c,da,fa,db,fb,dc) fusionne a[da..fa] et b[db..fb] dans c[dc..fc] avec fc=dc+(fa-da)+(fb-db)+1. Cette procédure marche évidemment si les trois zones de mémoire impliquées sont disjointes. Mais elle marche encore si une des deux zones de départ est la fin de la zone de destination (On peut avoir b=c et bf=cf). Par contre elle ne marche pas si une des deux zones de départ est le début de la zone de destination (si da=dc alors a et c doivent être des tableaux différents). C'est pourquoi, dans le programme suivant, on copie t[d..m] dans a[d..m] avant de faire la fusion. En plus du tableau t que l'on trie, on a donc besoin d'un autre tableau a. Dans la première version de la procédure de tri, tri1, le tableau a est une variable locale de tri1 qui est donc créée à chaque fois que l'on rentre dans tri1 et détruite à chaque fois qu'on en sort. Comme tri1 est récursive, il y a plusieurs appel de tri1 actifs en même temps (Il en a log₂n) et il y a donc plusieurs exemplaires de a. C'est un gaspillage de mémoire, on pourrait utiliser un seul a, toujours le même. Pour cela il ne faut pas le déclarer comme une variable locale de tri1, mais à l'extérieur de tri1. C'est ce qui est fait dans la deuxième version de la procédure de tri : tri2 est une procédure non récursive, dans laquelle on déclare la variable a, et qui contient une procédure récursive tri1 qui utilise la variable globale a sans la redéclarer.

program pp;
const n=10;
type tab=array[1..n] of integer;
procedure fusion(var a,b,c:tab;da,fa,db,fb,dc:integer);
begin
  while (da<=fa) and (db<=fb) do
  if a[da]<b[db] then
  begin
    c[dc]:=a[da];
    dc:=dc+1;
    da:=da+1
  end            else
  begin
    c[dc]:=b[db];
    dc:=dc+1;
    db:=db+1
  end;
  while da<=fa do
  begin
    c[dc]:=a[da];
    dc:=dc+1;
    da:=da+1
  end;
  while db<=fb do
  begin
    c[dc]:=b[db];
    dc:=dc+1;
    db:=db+1
  end
end;

procedure copie(var a,b:tab;d,f:integer);
begin
  for d:=d to f do b[d]:=a[d]
end;

procedure tri1(var t:tab;d,f:integer);
var a:tab;
    m:integer;
begin
  if d<f then
  begin
    m:=(d+f) div 2;
    tri1(t,d,m);
    tri1(t,m+1,f);
    copie(t,a,d,m);
    fusion(a,t,t,d,m,m+1,f,d)
  end
end;

procedure tri2(var t:tab;d,f:integer);
var a:tab;
procedure tri1(d,f:integer);
var m:integer;
begin (* tri1 *)
  if d<f then
  begin
    m:=(d+f) div 2;
    tri1(d,m);
    tri1(m+1,f);
    copie(t,a,d,m);
    fusion(a,t,t,d,m,m+1,f,d)
  end
end; (* tri1 *)
begin (* tri2 *)
  tri1(d,f)
end; (* tr2 *)

function min(a,b:integer):integer; begin if a<b then min:=a else min:=b end;

procedure tri3(var t:tab;d,f:integer);
var a:tab;
    L,da:integer;
begin
  L:=1;
  while d+L<=f do
  begin
    da:=d;
    while da+L<=f do
    begin
      copie(t,a,da,da+L-1);
      fusion(a,t,t,da,da+L-1,da+L,min(da+L+L-1,f),da);
      da:=da+L+L
    end;
    L:=L+L
  end
end;

procedure afftab(var a:tab);
var i:integer;
begin
  for i:=1 to n do write(a[i]:4);
  writeln
end;

var a:tab;
    i:integer;
begin
  for i:=1 to n do a[i]:=i*3 mod n;
  afftab(a);
  tri1(a,1,n);
  afftab(a);
  for i:=1 to n do a[i]:=i*3 mod n;
  afftab(a);
  tri2(a,1,n);
  afftab(a);
  for i:=1 to n do a[i]:=i*3 mod n;
  afftab(a);
  tri3(a,1,n);
  afftab(a)
end.

Le programme précédent écrit

   3   6   9   2   5   8   1   4   7   0
   0   1   2   3   4   5   6   7   8   9
   3   6   9   2   5   8   1   4   7   0
   0   1   2   3   4   5   6   7   8   9
   3   6   9   2   5   8   1   4   7   0
   0   1   2   3   4   5   6   7   8   9

temps de calcul

On peut évaluer le temps de calcul de ces procédures : Dans la procédure fusion, à chacune des itérations d'une des boucles, un élément est écrit dans le tableau de destination. On peut donc considérer que le temps pris par une fusion est à peu près proportionnel à la taille du tableau trié obtenu. De même le temps pris par la procédure copie est à peu près proportionnel à la taille de la zone copiée, qui est à peu près la moitié de la longueur de la zone à trier. Dans un appel à tri1, à part l'appel à ces deux procédures, et les deux appels récursifs qui prennent aussi beaucoup de temps, il n'y a que le passage des arguments, un test pour savoir s'il y a plusieurs nombres à trier et le calcul m:=(d+f) div 2 qui prennent un temps constant que l'on va donc négliger. En notant f_n le temps pris pour le tri d'un tableau de n éléments, on a donc les relations :
f_2n=2n+2f_n et f_2n+1=2n+1+f_n+f_n+1 et f₁=0.
qui permettent de calculer f_n pour tout n et en particulier pour toute puissance de 2. En effet
f_2^k=2^k+2f_2^k-1 donc f_2^k/2^k=1+f_2^k-1/2^k-1. Donc f_2^k/2^k=k+f₁/1=k. Autrement dit. f_2^k=k 2^k.
Soit g_n=f_n+1-f_n.

i    1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
f_i   0   2   5   8  12  16  20  24  29  34  39  44  49  54  59  64
g_i   2   3   3   4   4   4   4   5   5   5   5   5   5   5   5   5

g_2n=f_2n+1-f_2n= (2n+1+f_n+1+f_n)-(2n+2f_n)= 1+f_n+1-f_n= 1+g_n
g_2n+1=f_2n+2-f_2n+1= (2n+2+2f_n+1)-(2n+1+f_n+1+f_n)= 1+f_n+1-f_n= 1+g_n
Autrement dit g_n=1+g_[n/2]. Donc g_n=1+g_[n/2]=2+g_[n/4]=... =[log₂n]+g₁=[log₂n]+2
On a donc montré que pour tout k, la suite f_2^k=k 2^k, f_2^k+1, f_2^k+2,... f_2^k+1 est une progression arithmétique de raison k+2.
Autrement dit si 2^k≤n≤2^k+1 alors f_n=(k+2)n-2^k+1.
Cela montre que f_n=O(n ln(n)).

comparaison avec le tri par selection

Pour de grands tableaux cette méthode de tri est beaucoup plus rapides que les méthodes en O(n²) comme le tri à bulle ou le tri par sélection. Par exemple pour un tableau de 1000 éléments, le tri par fusion se fera avec 1000 log₂1000= 10000 itérations des boucles élémentaires de la procédure fusion. Le tri par sélection se ferait avec 1000x1000/2=500000 itérations d'une boucle élémentaire. Le tri par fusion est donc environ 50 fois plus rapide.

tri par fusion non récursif

Le tri par fusion peut aussi se faire sans récursivité : On considère au début que le tableau est constitué d'une succession de zones triées de longueur 1. Puis on fusionne ces zones 2 par 2, pour obtenir une succession de zones triées de longueur 2. Puis on fusionne ces zones 2 par 2, pour obtenir une succession de zones triées de longueur 4. Puis on fusionne ces zones 2 par 2, pour obtenir une succession de zones triées de longueur 8. Etc. jusqu'à ce que la longueur des zones triées dépasse la longueur du tableau. C'est ce que fait la procédure tri3.
suivant précédent sommaire

lundi 8 novembre 2004 : analyse de la complexité des algorithmes

Dans le programme précédent on peut effectivement compter les itérations des boucles de la procédure fusion en ajoutant un compteur que l'on incrémente à chaque itération.

type tab=array[1..n] of integer;
var nbit:integer; (* ligne ajoutée *)
procedure fusion(var a,b,c:tab;da,fa,db,fb,dc:integer);
begin
  while (da<=fa) and (db<=fb) do
  if a[da]<b[db] then
  begin
    inc(nbit); (* ligne ajoutée *)
    c[dc]:=a[da];
    dc:=dc+1;
    da:=da+1
  end            else
  begin
    inc(nbit); (* ligne ajoutée *)
    c[dc]:=b[db];
    dc:=dc+1;
    db:=db+1
  end;
  while da<=fa do
  begin
    inc(nbit); (* ligne ajoutée *)
    c[dc]:=a[da];
    dc:=dc+1;
    da:=da+1
  end;
  while db<=fb do
  begin
    inc(nbit); (* ligne ajoutée *)
    c[dc]:=b[db];
    dc:=dc+1;
    db:=db+1
  end
end;

Le programme principal devient :

begin
  for i:=1 to n do a[i]:=i*3 mod n;
  afftab(a);
  nbit:=0; (* ligne ajoutée *)
  tri1(a,1,n);
  writeln('nombre d''iterations : ',nbit); (* ligne ajoutée *)
  afftab(a);
  for i:=1 to n do a[i]:=i*3 mod n;
  afftab(a);
  nbit:=0; (* ligne ajoutée *)
  tri2(a,1,n);
  writeln('nombre d''iterations : ',nbit); (* ligne ajoutée *)
  afftab(a);
  for i:=1 to n do a[i]:=i*3 mod n;
  afftab(a);
  nbit:=0; (* ligne ajoutée *)
  tri3(a,1,n);
  writeln('nombre d''iterations : ',nbit); (* ligne ajoutée *)
  afftab(a)
end.

On constate ainsi que pour trier un tableau de 10 éléments les procédures récursives de tri par fusion, utilisent bien f₁₀ c'est-à-dire 34 itérations des boucles de fusion, tandis que la procédure itérative, en utilise 36 : Elle n'est pas optimale, car elle fusionne parfois ensemble des morceaux triés de tailles très différentes.

notations o (petit o), O (grand o), Ω (grand oméga) et Θ (grand théta)

Soit f et g deux fonctions de R dans R définies au voisinage de l'infini.

o

On dira que f=o(g) au voisinage de l'infini si
∀ A>0, ∃ B, ∀ x>B, |f(x)|≤A|g(x)|
Si on suppose que g ne s'annule pas au voisinage de l'infini, cela signifie que lim f(x)/g(x)=0.
On dira aussi que f est négligeable devant g.
Par exemple :
x²=o(x³)
2x⁴-5x³+10x²-6x+1=o(3x⁷+2x⁴)
ln x=o(x)
x³(ln x)²=o(x⁵)
Plus généralement x^a(ln x)^b=o(x^a'(ln x)^b') si a<a' ou si a=a' et b<b'

O

On dira que f=O(g) au voisinage de l'infini si
∃ A>0, ∃ B, ∀ x>B, |f(x)|≤A|g(x)|
Si on suppose que g ne s'annule pas au voisinage de l'infini, cela signifie que lim sup f(x)/g(x)<∞, c'est-à-dire que f/g reste borné au voisinage de l'infini.
Par exemple :
Si f=o(g) alors f=O(g).
3x²+x+100=O(x²)
2x⁴-5x³+10x²-6x+1=O(x⁴)
x²(2+sin(x))=O(x²)

Ω

On dira que f=Ω(g) au voisinage de l'infini si g=O(f), c'est-à-dire si
∃ A>0, ∃ B, ∀ x>B, |f(x)|≥A|g(x)|
Si on suppose que g ne s'annule pas au voisinage de l'infini, cela signifie que lim inf f(x)/g(x)<0, c'est-à-dire que f/g ne s'approche pas de 0 au voisinage de l'infini.
Par exemple :
3x²+x+100=Ω(x²)
2x⁴-5x³+10x²-6x+1=Ω(x⁴)
x²sin(x)=Ω(x²)

Θ

On dira que f=Θ(g) au voisinage de l'infini si f=O(g) et g=O(f), c'est-à-dire si
∃ A>0, ∃ A'>0, ∃ B, ∀ x>B, A'|g(x)|≥|f(x)|≥A|g(x)|
Si on suppose que g ne s'annule pas au voisinage de l'infini, cela signifie que que f/g ne s'approche pas de 0 ni de l'infini au voisinage de l'infini.
Par exemple :
3x²+x+100=Θ(x²)
2x⁴-5x³+10x²-6x+1=Θ(x⁴)
x²(2+sin(x))=Θ(x²)

temps de calcul, exemple des tris

En général on évalue la vitesse d'un algorithme, en donnant son temps de calcul en fonction de la taille des données.
Par exemple pour trier un tableau de n éléments,
le tri par sélection prend un temps Θ(n²),
le tri Shell en prenant une suite de pas vérifiant x_i+1=[(5x_i+1)/11] prend un temps Θ(n^5/4),
le tri Shell en prenant comme pas tous les 2ⁱ3^j prend un temps Θ(n(ln n)²),
le tri par fusion prend un temps Θ(n ln(n)).
C'est ce qu'on fait de mieux pour trier un tableau en faisant une suite de comparaisons de deux de ses éléments. En effet si un tableau est mélangé aléatoirement, les n! ordres possibles étant tous équiprobables, alors après chaque comparaisons, le nombre d'ordres possibles restant est en moyenne au mieux divisé par deux. Donc pour tout algorithme de tri par comparaison l'espérance du nombre de comparaisons nécessaires pour déterminer l'ordre croissant est supérieure à log₂(n!)=Θ(n ln n).
Cependant il existe des méthodes de tri sans comparaison, qui prennent un temps Θ(n).
Si le temps de calcul d'un algorithme est Θ(n ln n), ce temps de calcul est plus ou moins égal à n ln n multiplié par une constante. En fait on ne précise pas cette constante car elle dépend du soin que l'on a pris à écrire le programme qui exécute cet algorithme, du langage utilisé (le programme s'exécutera beaucoup plus vite avec un langage compilé comme pascal ou C, qu'avec un langage interprété comme java), de l'ordinateur utilisé (tous les deux ans les ordinateurs sont deux fois plus rapides), des options utilisées lors de la compilation, des autres programmes qui tournent en même temps sur le même ordinateur, etc. . Mais ce n'est très grave de ne pas connaître cette constante. En effet, supposons que l'on puisse résoudre un même problème avec deux algorithmes différents, qui ont des temps de calcul égaux à A n ln n et B n², avec une petite constante B et une grande constante A. Alors pour des données de petite taille, l'algorithme en B n² sera peut-être plus rapide, mais pour n suffisamment grand, on est sûr que A n ln n sera plus petit que B n².

temps de calcul des opérations sur les vecteurs et les matrices

opération	temps de calcul
addition de deux vecteurs	Θ(n)
addition de deux matrices	Θ(n²)
multiplication d'une matrice par un vecteur	Θ(n²)
multiplication de deux matrices	Θ(n³)
inversion d'une matrice	Θ(n³)

L'addition de deux vecteurs de taille n contient une boucle qui est faite n fois :

for i:=1 to n do c[i]:=a[i]+b[i]

L'addition de deux matrices carrées n x n contient deux boucles imbriquées :

for i:=1 to n do for j:=1 to n do c[i,j]:=a[i,j]+b[i,j]

Pour chacune des n itérations de la boucle externe (pour chaque valeur de i), on exécute n fois la boucle interne (pour chaque valeur de j). L'instruction c[i,j]:=a[i,j]+b[i,j] est donc exécutée n² fois, une fois pour chacun des couples (i,j).
Si le vecteur C=A B est le produit de la matrice A par le vecteur B, alors c_i=∑_j=1..na_i,jb_j. Pour chacun des n² couples (i,j) on doit donc calculer le produit a_i,jb_j. Chaque multiplication est suivie d'une addition. Il y a donc en tout 2n² opérations (additions ou multiplications). En fait l'instruction s:=s+a[i,j]*b[j] est exécutée n² fois.

for i:= 1 to n do
begin
  s:=0;
  for j:=1 to n do s:=s+a[i,j]*b[j];
  c[i]:=s
end

Si la matrice C=A B est le produit des deux matrices A et B, alors c_i,k=∑_j=1..na_i,jb_j,k. On peut donc calculer le produit a_i,jb_j,k, pour chacun des n³ triplets (i,j,k). Chaque multiplication est suivie d'une addition. Il y a donc en tout 2n³ opérations (additions ou multiplications). En fait l'instruction s:=s+a[i,j]*b[j,k] est exécutée n³ fois. Elle se trouve à l'intérieur de trois boucles imbriquées :

for i:= 1 to n do for k:= 1 to n do
begin
  s:=0;
  for j:=1 to n do s:=s+a[i,j]*b[j,k];
  c[i,k]:=s
end

En fait Volker Strassen a trouvé en 1969 un algorithme plus efficace pour multiplier deux matrices carrées. On peut obtenir le produit de deux matrices 2x2 en faisant seulement sept multiplications (et non pas huit) et 18 additions ou soustractions :

  a  b      e  f     i  j
  c  d  *   g  h  =  k  l
 i=ae+bg= (b-d)(g+h) + (a+d)(e+h) + d(g-e) - (a+b)h
 j=af+bh=                           a(f-h) + (a+b)h
 k=ce+dg=                           d(g-e) + (c+d)e
 l=cf+dh= (c-a)(e+f) + (a+d)(e+h) + a(f-h) - (c+d)e

En découpant chacune des deux matrices n x n en quatre blocs de n/2 x n/2, on peut donc obtenir le produit de ces deux matrices en utilisant seulement sept multiplications de matrices n/2 x n/2. En appliquant cet algorithme récursivement, on peut donc faire le produit de deux matrices 2^k x 2^k avec seulement 7^k multiplications (au lieu de (2^k)³=8^k ). Autrement dit le produit de deux matrices n x n prend un temps Θ(n^{(ln 7)/(ln 2)}).
Plus de détails.
De la même manière on peut aussi calculer l'inverse d'une matrice n x n en un temps Θ(n^{(ln 7)/(ln 2)}).
suivant précédent sommaire

lundi 15 novembre 2004 : crible d'Eratosthène

Dans les quatre programmes qui suivent, la fonction premier rend vrai ou faux, selon que son argument est un nombre premier ou non. Autrement dit, l'expression premier(a) est vraie si et seulement si le nombre entier a est premier. Par exemple premier(37) vaut vrai alors que premier(38) vaut faux.
Le programme principal prend chacun des entiers de 2 à n, vérifie s'il est premier ou non, en appelant la fonction premier, et l'affiche s'il est bien premier. Autrement dit le programme affiche la liste de tous les nombres premiers inférieurs ou égaux à n. La plus grande partie du temps de calcul est passée dans la fonction premier et plus précisément dans sa boucle for. On peut donc estimer le temps de calcul total du programme, par T(n)=∑_2≤a≤nf(a), où f(a) représente le nombre d'itérations de la boucle for lors de l'évaluation de premier(a).
Dans ce premier programme, f(a)=a-2 donc T(n)=0+1+2+...+(n-2)=(n-1)(n-2)/2∼ n²/2.
Ainsi, ce programme affiche tous les nombres premiers jusqu'à n en un temps Θ(n²). Pour n=100000 il met 8 minutes et 32 secondes.

const n=100000;
type nombre=longint;
function premier(p:nombre):boolean;
var d:nombre;
begin
  premier:=true;
  for d:=2 to p-1 do if p mod d=0 then premier:=false
end;
var p:nombre;
begin
  for p:=2 to n do if premier(p) then write(p,' ');
  writeln
end.

Dans le programme précédent, on teste si chacun des entiers d compris entre 2 et p-1 divise p ou non. A la fin de la boucle on rend vrai si on n'a trouvé aucun diviseur et faux si on en a trouvé un, mais dans tous les cas on continue la boucle jusqu'à p-1. On peut évidemment arrêter la boucle dès qu'on a trouvé un diviseur. Dans ce cas f(a) vaut a-2 si a est premier et sinon f(a) est égal au plus petit diviseur premier de a, qui est en général beaucoup plus petit que a et en tout cas inférieur à √a. Puisque la proportion des nombres premiers parmi les entiers de 1 à n est 1/ln n, la somme des f(a) pour a premier est à peu près n²/(2ln n), tandis que la somme des f(a) pour a composé est inférieure à n√n, et est donc négligeable. Donc T(n)∼n²/(2ln n). On a gagné un facteur ln n sur le temps de calcul.
Le programme suivant affiche tous les nombres premiers jusqu'à n en un temps Θ(n²/ln n). Pour n=100000 il met 54 secondes.

const n=100000;
type nombre=longint;
function premier(p:nombre):boolean;
var d:nombre;
begin
  premier:=false;
  for d:=2 to p-1 do if p mod d=0 then exit;
  premier:=true
end;
var p:nombre;
begin
  for p:=2 to n do if premier(p) then write(p,' ');
  writeln
end.

Quand un nombre a est composé, il possède un diviseur inférieur à sa racine carrée. Au lieu de chercher un diviseur parmi les nombres de 2 à a-1 on peut donc se contenter de le chercher entre 2 et √a. On peut donc partir du premier programme et remplacer for d:=2 to p-1 do par for d:=2 to round(sqrt(p)) do. Alors f(a)∼√a et T(n)∼∑_2≤a≤n√a ∼∫₀ⁿ√a da=(2/3)n^3/2.
Le programme suivant affiche tous les nombres premiers jusqu'à n en un temps Θ(n^3/2). Pour n=100000 il met 5,4 secondes.

const n=100000;
type nombre=longint;
function premier(p:nombre):boolean;
var d:nombre;
begin
  premier:=true;
  for d:=2 to round(sqrt(p)) do if p mod d=0 then premier:=false
end;
var p:nombre;
begin
  for p:=2 to n do if premier(p) then write(p,' ');
  writeln
end.

Par rapport à la première version, l'amélioration de la deuxième version, gagne un facteur ln n sur le temps de calcul, tandis que l'amélioration de la troisième version, gagne un facteur √n. En combinant les deux améliorations, on gagne les deux facteurs.
Le programme suivant affiche tous les nombres premiers jusqu'à n en un temps Θ(n^3/2/ln n). Pour n=100000 il met 0,8 seconde. La moitié de ce temps est prise par le write.

const n=100000;
type nombre=longint;
function premier(p:nombre):boolean;
var d:nombre;
begin
  premier:=false;
  for d:=2 to trunc(sqrt(p)) do if p mod d=0 then exit;
  premier:=true
end;
var p:nombre;
begin
  for p:=2 to n do if premier(p) then write(p,' ');
  writeln
end.

Pour améliorer encore le temps de calcul de ce programme, il faut changer de méthode. On abandonne la procédure premier et on va utiliser le crible d'Eratosthène. On écrit la liste de tous les nombres entiers de 2 à n. Puis on barre tous les nombres qui sont produits de deux entiers plus petits. A la fin, les nombres qui ne sont pas barrés sont les nombres premiers. En fait on ne barre pas vraiment les nombres : On utilise un tableau de booléens. t[a] est vrai tant que le nombre a n'a pas été barré, il reste potentiellement premier. t[a] devient faux quand on barre a, parce qu'on a trouvé une de ses factorisations, on sait alors qu'il n'est pas premier.
Dans le programme suivant, toutes les instructions sont exécutées au plus n fois, sauf l'instruction t[p*d]:=false qui se trouve dans deux boucles for imbriquées. Pour les très grandes valeurs de n, ce sont donc les exécutions de cette instruction qui prennent la plus grosse partie du temps de calcul. Il suffit donc de les compter pour avoir une estimation du temps de calcul total pris par le programme. Pour chaque valeur de p la boucle interne est faite ⌊n/p⌋-1 fois.
T(n)=∑_2≤p≤n⌊n/p⌋-1 ∼∫_eⁿ(n/p)dp=n ln n
Le programme suivant affiche tous les nombres premiers jusqu'à n en un temps Θ(n ln n). Pour n=100000 il met 0,40 seconde. Ce temps est principalement passé dans le write(p,' '). Il ne passe que 0,12 seconde en dehors de l'affichage.

const n=100000;
type nombre=longint;
var t:array[2..n] of boolean;
    d,p:nombre;
begin
  for p:=2 to n do t[p]:=true;
  for p:=2 to n do for d:=2 to n div p do t[p*d]:=false;
  for p:=2 to n do if t[p] then write(p,' ');
  writeln
end.

Dans le programme précédent, on barre deux fois le nombre 35, une fois pour p=5 et d=7, et une autre fois pour p=7 et d=5. On peut donc économiser la moitié du temps de calcul en imposant p≤d. Il suffit pour cela de remplacer for d:=2 to n div p do par for d:=p to n div p do
Le programme suivant affiche tous les nombres premiers jusqu'à n en un temps Θ(n ln n). Pour n=100000 il met 0,35 seconde. Ce temps est principalement passé dans le write(p,' '). Il ne passe que 0,07 seconde en dehors de l'affichage.

const n=100000;
type nombre=longint;
var t:array[2..n] of boolean;
    d,p:nombre;
begin
  for p:=2 to n do t[p]:=true;
  for p:=2 to n do for d:=p to n div p do t[p*d]:=false;
  for p:=2 to n do if t[p] then write(p,' ');
  writeln
end.

Dans la première version de ce programme, le nombre 210 est barré 14 fois, car 210=2x105=3x70=5x42=6x35=7x30=10x21=14x15=15x14=21x10=30x7=35x6=42x5=70x3=105x2. Dans la deuxième version on ne garde que les 7 premières décompositions en imposant p≤d. On peut ne garder que les 4 décompositions 2x105=3x70=5x42=7x30 en imposant que p est premier. Pour cela il suffit de rajouter if t[p] then entre les deux for. En effet au moment où on barre tous les multiples de p, on a déjà barré tous les multiples des nombres plus petits, et donc si p est composé, alors il est déjà barré en tant que multiple d'un nombre plus petit.
T(n)=∑_{2≤p≤n p premier}⌊n/p⌋-1 ∼∫₁ⁿ(n/p)(dp/ln p)=n ln ln n
Le programme suivant affiche tous les nombres premiers jusqu'à n en un temps Θ(n ln ln n). Pour n=100000 il met 0,38 seconde. Ce temps est principalement passé dans le write(p,' '). Il ne passe que 0,05 seconde en dehors de l'affichage.

const n=100000;
type nombre=longint;
var t:array[2..n] of boolean;
    d,p:nombre;
begin
  for p:=2 to n do t[p]:=true;
  for p:=2 to n do if t[p] then for d:=2 to n div p do t[p*d]:=false;
  for p:=2 to n do if t[p] then write(p,' ');
  writeln
end.

On peut évidemment combiner les améliorations de la seconde et de la troisième version.
Le programme suivant affiche tous les nombres premiers jusqu'à n en un temps Θ(n ln ln n). Pour n=100000 il met 0,35 seconde. Ce temps est principalement passé dans le write(p,' '). Il ne passe que 0,03 seconde en dehors de l'affichage.

const n=100000;
type nombre=longint;
var t:array[2..n] of boolean;
    d,p:nombre;
begin
  for p:=2 to n do t[p]:=true;
  for p:=2 to n do if t[p] then for d:=p to n div p do t[p*d]:=false;
  for p:=2 to n do if t[p] then write(p,' ');
  writeln
end.

suivant précédent sommaire

lundi 22 novembre 2004 : nombres amis

Pour un entier a on définit σ(a) comme la somme de tous les diviseurs de a et σ'(a) comme la somme de tous les diviseurs de a autres que a. Par exemple σ(22)=1+2+11+22=36 et σ'(22)=1+2+11=14. On dira qu'un nombre a est parfait si σ'(a)=a. On dira que deux nombres a et b sont amis si σ'(a)=b et σ'(b)=a.
Le programme suivant affiche tous les nombres parfaits et tous les couples de nombres amis inférieurs à n en un temps Θ(n²). Pour n=100000 il met 11 minutes et 9 secondes. Pour n=1000000 il met 19 heures.
La plus grande partie du temps de calcul est passée dans la fonction sigmap et plus précisément dans sa boucle for. On peut donc estimer le temps de calcul total du programme, par T(n)=∑_2≤a≤nf(a), où f(a) représente le nombre d'itérations de la boucle for lors de l'évaluation de sigmap(a).
Dans ce premier programme, f(a)=a-1 donc T(n)=0+1+2+...+(n-1)=(n-1)n/2∼ n²/2.

const n=100000;
type nombre=longint;
function sigmap(a:nombre):nombre;
var s,d:nombre;
begin
  s:=0;
  for d:=1 to a-1 do if a mod d=0 then s:=s+d;
  sigmap:=s
end;
var a,b:nombre;
begin
  for a:=2 to n do
  begin
    b:=sigmap(a);
    if b=a then writeln(a,' est parfait.');
    if b<a then if sigmap(b)=a then writeln(a,' et ',b,' sont amis.')
  end
end.

Quand d décrit tous les diviseurs de a inférieurs à √a, alors a/d décrit tous les diviseurs supérieurs à √a. On peut donc améliorer le programme le précédant de telle sorte que f(a)∼√a et T(n)∼∑_2≤a≤n√a ∼∫₀ⁿ√a da=(2/3)n^3/2.
Il faut simplement faire attention à bien compter 1 mais pas a parmi les diviseurs, et à ne pas compter deux fois √a quand a est un carré parfait.
Le programme suivant affiche tous les nombres parfaits et tous les couples de nombres amis inférieurs à n en un temps Θ(n^3/2). Pour n=100000 il met 3,19 seconde. Pour n=1000000 il met une minute et 40 secondes.

const n=100000;
type nombre=longint;
function sigmap(a:nombre):nombre;
var s,r,d:nombre;
begin
  s:=1;
  r:=round(sqrt(a));
  for d:=2 to r do if a mod d=0 then s:=s+d+a div d;
  if a=r*r then s:=s-r;
  sigmap:=s
end;
var a,b:nombre;
begin
  for a:=2 to n do
  begin
    b:=sigmap(a);
    if b=a then writeln(a,' est parfait.');
    if b<a then if sigmap(b)=a then writeln(a,' et ',b,' sont amis.')
  end
end.

Si a et b sont premiers entre eux alors σ(ab)=σ(a)σ(b). Par exemple σ(60)=1+3+5+15+2+6+10+30+4+12+20+60=(1+3+5+15)(1+2+4)=σ(15)σ(4). D'autre part, si p est premier, σ(p^k)=1+p+p²+...+p^k. Par exemple, σ(5⁴)=1+5+25+125+625.
On peut donc facilement calculer σ(a) quand on connaît la décomposition de a en produit de nombres premiers. Par exemple, σ(600)=σ(2³5²3)=(1+2+4+8)(1+5+25)(1+3)= 15x31x4=1860.
Si on sait que p est un diviseur premier de a et que p^k est sa plus grande puissance qui divise a, alors σ(a)=(1+p+p²+...+p^k)σ(a/p^k) C'est la formule qui est utilisée dans le programme suivant par la procédure récursive sigma. Cette procédure prend dans t[a] un facteur premier de a. Le programme principal commence donc par remplir le tableau t en utilisant le crible d'Eratosthène. Pendant ce crible, l'élément de tableau t[a] contient a tant qu'on a pas trouvé de diviseur de a, puis on y range successivement tous les diviseurs premiers de a que l'on trouve. A la fin si t[a] vaut toujours a, c'est que a est premier.
Le temps pris par le crible d'Eratosthène est Θ(n ln ln n). Le temps pris par le calcul de σ(a) peut être estimé par le nombre total d'itérations de la boucle repeat ... until (en les comptant aussi lors des appels récursifs). Il est égal au nombre de facteurs d'une décomposition de a en produit de nombres premiers. Par exemple pour 600=2x2x2x3x5x5 c'est 6. La valeur moyenne de ce nombre pour tous les entiers de 1 à n est à peu près de ln ln n. Donc le temps total pris par les calculs des σ(a) est donc Θ(n ln ln n). Mais comme les appels de fonctions prennent du temps, et qu'il y a deux instructions entre repeat et until, on comprend que le temps pris par les calculs des σ(a) est six fois plus grand que le temps pris par le crible.
Le programme suivant affiche tous les nombres parfaits et tous les couples de nombres amis inférieurs à n en un temps Θ(n ln ln n). Pour n=100000 il met 0,2 seconde. Pour n=1000000 il met 2,4 secondes.

const n=100000;
type nombre=longint;
var t:array[1..n] of nombre;
function sigma(a:nombre):nombre;
var s,p:nombre;
begin
  if a=1 then sigma:=1 else
  begin
    p:=t[a];
    s:=1;
    repeat
      s:=s*p+1;
      a:=a div p
    until a mod p<>0;
    sigma:=s*sigma(a)
  end
end;
function sigmap(a:nombre):nombre; begin sigmap:=sigma(a)-a end;
var p,a,b:nombre;
begin
  for p:=1 to n do t[p]:=p;
  for p:=2 to n do if t[p]=p then for b:=p to n div p do t[p*b]:=p;
  for a:=2 to n do
  begin
    b:=sigmap(a);
    if b=a then writeln(a,' est parfait.');
    if b<a then if sigmap(b)=a then writeln(a,' et ',b,' sont amis.')
  end
end.

Si p est premier, pour tout k≥0 on a σ(p^k)=1+p+p²+...+p^k donc
σ(p)=1+p et
σ(p^k+2)=(1+p)σ(p^k+1)-pσ(p^k).
Si b n'est pas divisible par p on a donc :
σ(b p)=(1+p)σ(b) et
σ(b p^k+2)=(1+p)σ(b p^k+1)-pσ(b p^k).
Si p est nombre premier qui divise a, il y a donc deux cas :
Ou bien p² ne divise pas a et alors σ(a)=(1+p)σ(a/p)
Ou bien p² divise a et alors σ(a)=(1+p)σ(a/p)-pσ(a/p²).
Dans le programme suivant t[a] contient successivement a, puis un diviseur premier de a, puis σ(a) puis σ'(a). Ce programme affiche tous les nombres parfaits et tous les couples de nombres amis inférieurs à n en un temps Θ(n ln ln n). Pour n=100000 il met 0,07 seconde. Pour n=1000000 il met 0,87 seconde.

const n=100000;
type nombre=longint;
var t:array[1..n] of nombre;
    p,a,b:nombre;
begin
  for p:=1 to n do t[p]:=p;
  for p:=2 to n do if t[p]=p then for b:=p to n div p do t[p*b]:=p;
  for a:=2 to n do
  begin
    p:=t[a]; (* p est un diviseur premier de a *)
    b:=a div p;
    if b mod p<>0 then t[a]:=t[b]*(p+1)
                  else t[a]:=t[b]*(p+1)-t[b div p]*p
  end;
  for a:=1 to n do t[a]:=t[a]-a;
  for a:=2 to n do
  begin
    b:=t[a];
    if b=a then writeln(a,' est parfait.');
    if b<a then if t[b]=a then writeln(a,' et ',b,' sont amis.')
  end
end.

Pour n=1000000 il affiche

6 est parfait.
28 est parfait.
284 et 220 sont amis.
496 est parfait.
1210 et 1184 sont amis.
2924 et 2620 sont amis.
5564 et 5020 sont amis.
6368 et 6232 sont amis.
8128 est parfait.
10856 et 10744 sont amis.
14595 et 12285 sont amis.
18416 et 17296 sont amis.
66992 et 66928 sont amis.
71145 et 67095 sont amis.
76084 et 63020 sont amis.
87633 et 69615 sont amis.
88730 et 79750 sont amis.
123152 et 122368 sont amis.
124155 et 100485 sont amis.
139815 et 122265 sont amis.
153176 et 141664 sont amis.
168730 et 142310 sont amis.
176336 et 171856 sont amis.
180848 et 176272 sont amis.
202444 et 196724 sont amis.
203432 et 185368 sont amis.
365084 et 280540 sont amis.
389924 et 308620 sont amis.
399592 et 356408 sont amis.
430402 et 319550 sont amis.
455344 et 437456 sont amis.
486178 et 469028 sont amis.
514736 et 503056 sont amis.
525915 et 522405 sont amis.
652664 et 643336 sont amis.
669688 et 600392 sont amis.
686072 et 609928 sont amis.
691256 et 624184 sont amis.
712216 et 635624 sont amis.
783556 et 667964 sont amis.
796696 et 726104 sont amis.
863835 et 802725 sont amis.
901424 et 879712 sont amis.
980984 et 898216 sont amis.

suivant précédent sommaire

lundi 29 novembre 2004 : pointeurs et listes chaînées

La mémoire vive de l'ordinateur, est un grand tableau. Les pointeurs sont des indices dans ce tableau. Les deux programmes suivants sont équivalents.

var a,b:integer;             var m:array[1..1000] of integer;
    p:^integer;                  p:integer;
begin                        begin
  p:=@a;                       p:=43;
  a:=3;                        m[43]:=3;
  p^:=p^+3;                    m[p]:=m[p]+3;
  writeln(a);                  writeln(m[43]);
  p:=@b;                       p:=47;
  p^:=4                        m[p]:=4
end.                         end.

La variable a correspond à l'élément de tableau m[43], La variable b correspond à l'élément de tableau m[47], L'adresse de a, notée @a, correspond à l'indice 43. L'adresse de b, notée @b, correspond à l'indice 47. La variable pointée par p, notée p^, correspond à l'élément de tableau m[p],
La variable p est de type pointeur sur un entier, noté ^integer. Sa valeur peut être l'adresse d'une autre variable de type entier. Quand la valeur de p est @a, on dit alors que p pointe sur a, et la variable pointée par p, c'est-à-dire p^ est a. Autrement dit, quand p vaut @a, alors p^ représente a.

var a,b,c:integer;
    p,q,r:^integer;
begin
  a:=1;b:=2;c:=3;
  new(p);
  q:=p;
  q^:=a+b;
  new(r);
  p^:=p^+1;
  r^:=q^;
  c:=r^;
  writeln(a:3,b:3,c:3,p^:3,q^:3,r^:3);
  p:=r;
  p^:=p^+r^;
  p^:=p^+r^;
  p^:=p^+r^;
  writeln(p^:3,q^:3,r^:3);
  p:=@a;
  q:=@b;
  p^:=a+b+c;
  q^:=a+b+c;
  writeln(a:3,b:3,c:3);
  for a:=1 to 2 do
  begin
    q^:=p^+1;
    q:=r
  end;
  writeln(a:3,b:3,c:3,p^:3,q^:3,r^:3);
  p:=@b;
  for c:=1 to 3 do
  begin
    p^:=r^+q^-c;
    r:=p;p:=q;q:=r
  end;
  writeln(p^:3,q^:3,r^:3)
end.

Le programme précédent écrit :

  1  2  4  4  4  4
 32  4 32
  7 13  4
  2  2  4  2  3  3
  8 13 13

Dans le programme suivant, le type p représente un pointeur sur une variable de type m. Une variable de type m est une structure formée de trois champs i, x et y. Puisque dans m les deux champs x et y sont de type p, il faut déclarer le type p avant le type m. Par contre dans la déclaration de p on utilise le type pointeur ^m, qui est formé de ^ suivi obligatoirement d'un nom. Ce nom correspond à un type qui peut être déclaré plus loin : Le type m est déclaré après le type p, mais on a quand même le droit de déclarer p comme un pointeur sur un m.
L'instruction new(a) crée une nouvelle variable de type m et range l'adresse de cette variable dans a. Autrement dit, elle change la valeur de a de telle façon que a^ représente une nouvelle variable.


type p=^m;
     m=record
         i:integer;
         x,y:p
       end;
var a,b:p;
begin
  new(a);
  new(b);
  a^.i:=1;
  b^.i:=2;
  a^.x:=a;
  a^.y:=b;
  b^.y:=a;
  new(b^.x);
  b^.x^.i:=3;
  b^.x^.x:=a;
  b^.x^.y:=b;
  writeln(a^.x^.x^.y^.x^.x^.y^.i)
end.

Le programme précédent écrit 2. Si on appelle m1, m2 et m3 les variables créées par les trois appels à new, le tableau suivant donne les valeurs de toutes les variables à la fin de l'exécution du programme.

variable	valeur
a	@m1
b	@m2
m1	(1,@m1,@m2)
m2	(2,@m3,@m1)
m3	(3,@m1,@m2)

listes chaînées

On peut ranger une suite de nombres de longueur quelconque dans une ``liste chaînée''. Chacun des nombres est mis dans un chainon, qui contient aussi un pointeur sur le chaînon suivant. Le pointeur du dernier chaînon aura la valeur spéciale nil pour indiquer qu'il n'a pas de successeur. La liste complète est représentée par l'adresse du premier chaînon (ou nil si elle est vide). Par exemple la liste 1, 5, 3, 6 sera réprésentée par @m1, si on appelle m1, m5, m3 et m6 les quatre chaînons.

variable	valeur
m1	(1,@m5)
m5	(5,@m3)
m3	(3,@m6)
m6	(6,nil)

Le programme suivant crée cette liste puis l'affiche.

type liste=^chainon;
     chainon=record val:integer; suite:liste end;
var l,p:liste;
begin
  new(l);                                  // l:=@m1
      l^.val:=1;                           // m1.val:=1
  new(l^.suite);                           // m1.suite=@m5
      l^.suite^.val:=5;                    // m5.val:=5
  new(l^.suite^.suite);                    // m5.suite=@m3
      l^.suite^.suite^.val:=3;             // m3.val:=3
  new(l^.suite^.suite^.suite);             // m3.suite=@m6
      l^.suite^.suite^.suite^.val:=6;      // m6.val:=6
      l^.suite^.suite^.suite^.suite:=nil;  // m6.suite=nil
  p:=l;
  while p<>nil do
  begin
    write(p^.val,' ');
    p:=p^.suite
  end
end.

Avec des with le programme précédent devient :

type liste=^chainon;
     chainon=record val:integer; suite:liste end;
var l,p:liste;
begin
  new(l);                 // l:=@m1
  with l^do               // with m1 do
  begin
    val:=1;               // m1.val:=1
    new(suite);           // m1.suite=@m5
    with suite^ do        // with m5 do
    begin
      val:=5;             // m5.val:=5
      new(suite);         // m5.suite=@m3
      with suite^ do      // with m3 do
      begin
        val:=3;           // m3.val:=3
        new(suite);       // m3.suite=@m6
        with suite^ do    // with m6 do
        begin
          val:=6;         // m6.val:=6
          suite:=nil      // m6.suite=nil
        end
      end
    end
  end;
  p:=l;
  while p<>nil do with p^ do
  begin
    write(val,' ');
    p:=suite
  end
end.

Avec des procédures il devient :

type liste=^chainon;
     chainon=record val:integer; suite:liste end;
function nouv(v:integer;s:liste):liste;
begin
  new(nouv);
  nouv^.val:=v;
  nouv^.suite:=s
end;
procedure aff(p:liste);
begin
  while p<>nil do with p^ do
  begin
    write(val,' ');
    p:=suite
  end;
  writeln
end;
  
var l:liste;
begin
  l:=nouv(1,nouv(5,nouv(3,nouv(6,nil))));
  aff(l)
end.

suivant précédent sommaire

lundi 6 décembre 2004 : listes chaînées

Compléter les procédures et fonctions suivantes :

procedure affre(p:liste):
procedure ffare(p:liste);
function longueurit(p:liste):integer;
function longueurre(p:liste):integer;
function sommeit   (p:liste):integer;
function sommere   (p:liste):integer;
procedure add1(p:liste);
function copie (p:liste):liste;    //  récursive
function miroir(p:liste):liste;    //  itérative
function eipoc (p:liste):liste;    //  itérative
function fusionre(a,b:liste):liste;
function fusionit(a,b:liste):liste;
function trifusion(a:liste):liste;

Les procédures dont le nom se termine par it sont itératives, Celles dont le nom se termine par re sont récursives. Si par exemple a est la liste (1,3,6,9) et b est la liste (2,4,5) et c est la liste (3,14,5,9,7), alors affre(a) écrit 1 3 6 9.
ffare(a) écrit 9 6 3 1.
longueurit(a) et longueurre(a) valent 4.
sommeit(a) et sommere(a) valent 19.
add1(a) ajoute 1 à chacun des éléments de la liste a qui devient (2,4,7,10).
copie(a) est une nouvelle liste constituée de quatre nouveaux chaînons contenant (1,3,6,9).
eipoc(a) est une nouvelle liste constituée de quatre nouveaux chaînons contenant (9,6,3,1).
a:=miroir(a) change l'ordre des chaînons de a qui devient (9,6,3,1).
funsionre(a,b) et funsionit(a,b) fabriquent la liste (1,2,3,4,5,6,9) en réutilisant les chaînons des deux listes a et b.
c:=trifusion(c) réordonne les chaînons de la liste c qui devient (3,5,7,9,14).
Les fonctions miroir et eipoc fonctionnent à peu près de la même façon : elles parcourent la liste p (comme dans aff) et rajoutent un par un les éléments parcourus en tête d'une liste initialement vide. La différence entre les deux fonctions est que eipoc crée un nouveau chaînon (en appelant nouv) alors que miroir détache le chainon de tête de p avant de le rajouter en tête de la nouvelle liste.
La première partie de la function trifusion ressemble beaucoup à la fonction miroir si on utilise l'algorithme suivant :

function trifusion(a:liste):liste;
var b,c:liste;
begin
  b:=nil;
  c:=nil;
  while a≠nil do
  begin
    on enlève un chainon en tête de a et on le met en tête de b;
    on échange b et c
  end;
  if b=nil then trifusion:=c
           else trifusion:= la liste obtenue en fusionnant les deux listes b et c après les avoir triées
end;

La boucle while répartit les éléments de a alternativement dans b et c, en mettant le dernier dans c. Donc à la fin, c a la même longueur que b ou a un élément de plus. Donc b est vide si et seulement si au début, a n'avait pas plus d'un élément qui se trouve donc dans c.

type liste=^chainon;
     chainon=record val:integer; suite:liste end;
function nouv(v:integer;s:liste):liste;
begin
  new(nouv);
  nouv^.val:=v;
  nouv^.suite:=s
end;
procedure aff(p:liste);
begin
  while p<>nil do with p^ do
  begin
    write(val,' ');
    p:=suite
  end;
  writeln
end;
procedure affre(p:liste);
begin
  if p<>nil then with p^ do
  begin
    write(val,' ');
    affre(suite)
  end
end;
procedure ffare(p:liste);
begin
  if p<>nil then with p^ do
  begin
    ffare(suite);
    write(val,' ')
  end
end;
function longueurit(p:liste):integer;
var j:integer;
begin
  j:=0;
  while p<>nil do
  begin
    j:=j+1;
    p:=p^.suite
  end;
  longueurit:=j
end;
function longueurre(p:liste):integer;
begin
  if p=nil then longueurre:=0
           else longueurre:=1+longueurre(p^.suite)
end;
function sommeit  (p:liste):integer;
var s:integer;
begin
  s:=0;
  while p<>nil do
  begin
    s:=s+p^.val;
    p:=p^.suite
  end;
  sommeit:=s
end;
function sommere  (p:liste):integer;
begin
  if p=nil then sommere:=0
           else sommere:=p^.val+sommere(p^.suite)
end;
procedure add1(p:liste);
begin
  while p<>nil do with p^ do
  begin
    val:=val+1;
    p:=suite
  end;
end;
function copie (p:liste):liste;    //  récursive
begin
  if p=nil then copie:=nil
           else copie:=nouv(p^.val,copie(p^.suite))
end;
function miroir(p:liste):liste;    //  itérative
var q,r:liste;
begin
  q:=nil;
  while p<>nil do
  begin
    r:=p; p:=r^.suite;  //  on enlève le premier élément r de p
    r^.suite:=q; q:=r   //  on l'ajoute en tête de q
  end;
  miroir:=q
end;
function eipoc (p:liste):liste;    //  itérative
var q:liste;
begin
  q:=nil;
  while p<>nil do
  begin
    q:=nouv(p^.val,q);
    p:=p^.suite
  end;
  eipoc:=q
end;
function copie2(p:liste):liste;  // itérative
begin copie2:=miroir(eipoc(p)) end;
function fusionre(a,b:liste):liste;
begin
end;
function fusionit(a,b:liste):liste;
begin
end;
function trifusion(a:liste):liste;
begin
end;
  
var l,a,b,c:liste;
begin
  l:=nouv(1,nouv(5,nouv(3,nouv(6,nil))));
  affre(l); ffare(l); aff(l);
  writeln(longueurit(l),'=',longueurre(l),'  ',sommeit(l),'=',sommere(l));
  a:=copie(l);
  add1(a);
  aff(a);
  l:=miroir(l);
  aff(l);
  b:=eipoc(a);
  aff(b);
  c:=copie2(b);
  aff(c)
end.

Le programme précédent écrit :

1 5 3 6 6 3 5 1 1 5 3 6
4=4  15=15
2 6 4 7
6 3 5 1
7 4 6 2
7 4 6 2

suivant précédent sommaire

lundi 13 décembre 2004 : tri fusion de listes chaînées

Si on remplace la fin du programme précédent par :

function fusionre(a,b:liste):liste;
begin
  if a=nil then fusionre:=b else
  if b=nil then fusionre:=a else
  if a^.val<b^.val then begin a^.suite:=fusionre(a^.suite,b); fusionre:=a end
                   else begin b^.suite:=fusionre(b^.suite,a); fusionre:=b end
end;
function fusionit1(a,b:liste):liste;
var c,p:liste;
begin
  c:=nil;
  while (a<>nil) or (b<>nil) do
  if (b=nil) or (a<>nil) and (a^.val<b^.val) then
  begin
    p:=a; a:=p^.suite;  // on détache le chainon p en tete de a
    p^.suite:=c; c:=p   // on le met en tete de c
  end                                        else
  begin
    p:=b; b:=p^.suite;  // on détache le chainon p en tete de b
    p^.suite:=c; c:=p   // on le met en tete de c
  end;
  fusionit1:=miroir(c)
end;
function fusionit2(a,b:liste):liste;
var d:liste;
begin
  if a=nil then fusionit2:=b else
  if b=nil then fusionit2:=a else
  begin
    if a^.val>b^.val then begin d:=b; b:=a end
                     else       d:=a;
    a:=d^.suite;
    fusionit2:=d;
    while (a<>nil) and (b<>nil) do
    if a^.val<b^.val then begin d^.suite:=a; d:=a; a:=d^.suite end
                     else begin d^.suite:=b; d:=b; b:=d^.suite end;
    if a=nil then d^.suite:=b
             else d^.suite:=a
  end
end;
function trifusion(a:liste):liste;
var p,b:liste;
    j:integer;
begin
  j:=longueurit(a) div 2;
  if j>0 then
  begin
    p:=a;
    for j:=j downto 2 do p:=p^.suite;
    b:=p^.suite;
    p^.suite:=nil;
    a:=fusionit2(trifusion(a),trifusion(b))
  end;
  trifusion:=a 
end;
  
var l,a,b,c:liste;
begin
  l:=nouv(1,nouv(5,nouv(3,nouv(6,nil))));
  affre(l); ffare(l); aff(l);
  writeln(longueurit(l),'=',longueurre(l),'  ',sommeit(l),'=',sommere(l));
  a:=copie(l);
  add1(a);
  aff(a);
  l:=miroir(l);
  aff(l);
  b:=eipoc(a);
  aff(b);
  c:=copie2(b);
  aff(c);
  c:=trifusion(c);
  aff(c)
end.

Il écrit une ligne de plus :

1 5 3 6 6 3 5 1 1 5 3 6
4=4  15=15
2 6 4 7
6 3 5 1
7 4 6 2
7 4 6 2
2 4 6 7

suivant précédent sommaire

lundi 3 janvier 2005 : pile et file d'attente

tableaux

type element=integer;
const nmax=100;
type pile=record
            t:array[0..nmax-1] of element;
	    n:integer
	  end;
     queue=record
             t:array[0..nmax-1] of element;
	     d,f:integer
	   end;
procedure empile(var p:pile;x:element);
begin
  if p.n=nmax then begin writeln('La pile déborde.'); halt end;
  p.t[p.n]:=x;
  inc(p.n)
end;
function depile(var p:pile;var x:element):boolean;
begin
  if p.n=0 then depile:=false else
  begin
    dec(p.n);
    x:=p.t[p.n];
    depile:=true
  end
end;
procedure initpile(var p:pile);
begin
  p.n:=0
end;
function pilevide(var p:pile):boolean;
begin
  pilevide:=p.n=0
end;
procedure enfile(var p:queue;x:element);
begin
  p.t[p.f]:=x;
  inc(p.f);
  if p.f=nmax then p.d:=0;
  if p.f=p.d then begin writeln('La file déborde.'); halt end
end;
function defile(var p:queue;var x:element):boolean;
begin
  if p.d=p.f then defile:=false else
  begin
    x:=p.t[p.d];
    inc(p.d);
    if p.d=nmax then p.d:=0;
    defile:=true
  end
end;
procedure initfile(var p:queue);
begin
  p.d:=0; p.f:=0
end;
function filevide(var p:queue):boolean;
begin
  filevide:=p.d=p.f
end;
var a:pile;
    b:queue;
    i,j:integer;
begin
  initpile(a);
  for i:=1 to 10 do empile(a,i);
  while depile(a,i) and depile(a,j) do
  begin
    writeln(i,'+',j,'=',i+j);
    empile(a,i+j)
  end;
  initfile(b);
  for i:=1 to 10 do enfile(b,i);
  while defile(b,i) and defile(b,j) do
  begin
    writeln(i,'+',j,'=',i+j);
    enfile(b,i+j)
  end
end.

Le programme précédent écrit :

10+9=19
19+8=27
27+7=34
34+6=40
40+5=45
45+4=49
49+3=52
52+2=54
54+1=55
1+2=3
3+4=7
5+6=11
7+8=15
9+10=19
3+7=10
11+15=26
19+10=29
26+29=55

listes chaînées

type element=integer;
type pile=^chainon;
     chainon=record x:element; s:pile end;
     queue=record p,q:pile end;
procedure empile(var p:pile;x:element);
var q:pile;
begin
  new(q);
  q^.x:=x;
  q^.s:=p;
  p:=q
end;
function depile(var p:pile;var x:element):boolean;
var q:pile;
begin
  if p=nil then depile:=false else
  begin
    q:=p;
    p:=q^.s;
    x:=q^.x;
    dispose(q);
    depile:=true
  end
end;
procedure initpile(var p:pile);
begin
  p:=nil
end;
function pilevide(var p:pile):boolean;
begin
  pilevide:=p=nil
end;
procedure enfile(var p:queue;x:element);
begin
  if p.p=nil then begin empile(p.p   ,x); p.q:=p.p    end
             else begin empile(p.q^.s,x); p.q:=p.q^.s end
end;
function defile(var p:queue;var x:element):boolean;
begin
  defile:=depile(p.p,x)
end;
procedure initfile(var p:queue);
begin
  p.p:=nil
end;
function filevide(var p:queue):boolean;
begin
  filevide:=p.p=nil
end;
var a:pile;
    b:queue;
    i,j:integer;
begin
  initpile(a);
  for i:=1 to 10 do empile(a,i);
  while depile(a,i) and depile(a,j) do
  begin
    writeln(i,'+',j,'=',i+j);
    empile(a,i+j)
  end;
  initfile(b);
  for i:=1 to 10 do enfile(b,i);
  while defile(b,i) and defile(b,j) do
  begin
    writeln(i,'+',j,'=',i+j);
    enfile(b,i+j)
  end
end.

précédent sommaire

lundi 10 janvier 2005 : fonction d'Ackermann

function f(n,i:longint):longint;
begin
  if n=0 then f:=i+1 else
  if i=0 then f:=1
         else f:=f(n-1,f(n,i-1))
end;
var i,n:integer;
begin
  for n:=0 to 5 do
  begin
    for i:=0 to 5 do write(f(n,i):10);
    writeln
  end
end.

Le programme précédent écrit :

         1         2         3         4         5         6
         1         2         3         4         5         6
         1         2         3         4         5         6
         1         2         3         4         5         6
         1         2         3         4         5         6
         1         2         3         4         5         6

On aurait pu le remplacer par

var i,n:integer;
begin
  for n:=0 to 5 do
  begin
    for i:=0 to 5 do write(i+1:10);
    writeln
  end
end.

On change légèrement la fonction.

function f(n,i:longint):longint;
begin
  if n=0 then f:=i+1 else
  if i=0 then f:=2
         else f:=f(n-1,f(n,i-1))
end;
var i,n:integer;
begin
  for n:=0 to 5 do
  begin
    for i:=0 to 5 do write(f(n,i):10);
    writeln
  end
end.

Le programme précédent écrit :

         1         2         3         4         5         6
         2         3         4         5         6         7
         2         4         6         8        10        12
         2         6        14        30        62       126
         2        14     65534

Il met plusieurs minute pour écrire 65534, puis il semble rentrer dans une boucle infinie. En fait f(0,i)=i+1, f(1,i)=i+2, f(2,i)=2+2i=2(i+2)-2, f(3,i)=2ⁱ⁺²-2, f(4,i)=2^2^2...^2-2 avec i+2 fois 2 dans 2^2^2..^2. Le terme suivant est donc f(4,3)=2⁶⁵⁵³⁶-2. Il est beaucoup trop grand pour être calculé. On peut aussi considérer une autre variante :

function f(n,i:longint):longint;
begin
  if n=0 then f:=i+1 else
  if i=0 then f:=f(n-1,1)
         else f:=f(n-1,f(n,i-1))
end;
var i,n:integer;
begin
  for n:=0 to 5 do
  begin
    for i:=0 to 5 do write(f(n,i):10);
    writeln
  end
end.

Le programme précédent écrit :

         1         2         3         4         5         6
         2         3         4         5         6         7
         3         5         7         9        11        13
         5        13        29        61       125       253
         13    65533

Il met plusieurs minute pour écrire 65533, puis il semble rentrer dans une boucle infinie. En fait f(0,i)=i+1, f(1,i)=i+2, f(2,i)=3+2i=3(i+2)-3, f(3,i)=2ⁱ⁺³-3, f(4,i)=2^2^2...^2-3 avec i+3 fois 2 dans 2^2^2..^2. Le terme suivant est donc f(4,2)=2⁶⁵⁵³⁶-3. Il est beaucoup trop grand pour être calculé.