Previous Up Next

Chapitre 19  Les programmes récursifs

Certains programmes se trouvent dans examples/recur.

19.1  Avec des chaines de caractères

19.1.1  Une liste de mots

On veut énumérer les éléments d’une liste. Pour cela on écrit le premier élément et on énumère la liste privée de son premier élément. On s’arrête quand la liste est vide.
On écrit :

enumere(l):={
if (l==[]) return 0;
print(l[0]);
enumere(tail(l));
}

On tape :
enumere(["jean","paul","pierre"])
On obtient, en écriture bleue, dans la zone des résultats intermédiaires :
"jean"
"paul"
"pierre"

19.1.2  Les mots

Étant donné un mot de n lettres, on veut écrire n lignes :
la première ligne sera constituée par la première lettre du mot,
la deuxième ligne sera constituée par les deux premières lettres...,
la dernière ligne sera constituée par le mot tout entier.
On écrira : mots(m) de façon récursive. On peut se servir de la fonction size(m) de Xcas qui renvoie le nombre de lettres du mot m, et de la fonction suppress(m,k) de Xcas qui renvoie le mot m privé de sa k-ième lettre (k=0.. size(m)-1).
On tape :

saufdernier(m):={
return suppress(m,size(m)-1);
}

puis

mots(m):={
if (size(m)==0) return 0;
mots(saufdernier(m));
print(m);
}

Exercice
Comment modifier le programme précédent pour avoir :
Étant donné un mot de n lettres, on veut écrire n lignes :
la première ligne sera constituée par le mot tout entier,
la deuxième ligne sera constituée par le mot privé de sa première lettre...,
la dernière ligne sera constituée par la première lettre du mot.
Réponse
On peut se servir de la fonction tail(m) de Xcas qui renvoie l le mot m privé de sa première lettre.

motex(m):={
if (size(m)==0) return 0;
print(m);
motex(tail(m));
}

19.2  Les palindromes

19.2.1  Les phrases palindromes

Étant donné une phrase, on veut écrire cette phrase en l’écrivant de droite à gauche. On écrira :
palindrome(s) de façon récursive :
il faut rajouter la première lettre de la phrase à la fin du palindrome de la phrase privée de sa première lettre.
On tape :

palindrome(ph):={
local s;
if (s==0) return ph;
s:=size(ph)-1;
return concat(palindrome(tail(ph)),ph[0]);
}

ou encore :
il faut rajouter la dernière lettre de la phrase devant le palindrome de la phrase privée de sa dernière lettre.
On tape :

saufdernier(m):={
return suppress(m,size(m)-1);
}
palindrome(ph):={
local s;
if (s==0) return ph;
s:=size(ph)-1;
return concat(ph[s],palindrome(saufdernier(ph)));
}

19.2.2  Nombre et valeur palindromique d’un entier

Un entier n est un palindrome s’il est identique à son palindrome qui est le nombre obtenu en écrivant n de droite à gauche.
Par exemple 12321 est un palindrome.
Pour tout entier n , on considère l’algorithme suivant :

  1. si l’entier n est un palindrome on s’arrête,
  2. sinon on ajoute à l’entier son palindrome (l’entier écrit à l’envers) et on retourne à l’étape 1.

Par exemple : 687,687+786=1473,1473+3741=5214,5214+4125=9339.
On appelle nombre palindromique d’un entier n le nombre Npal(n) d’étapes nécessaire pour obtenir unpalindrome.
Par exemple : Npal(12321)=0, Npal(687)=3.
On appelle valeur palindromique d’un entier n la valeur Vpal(n) du palindrome final.
Par exemple : Vpal(12321)=12321, Vpal(687)=9339.

  1. Étant donné un entier n, écrire une fonction palind qui renvoie le palindrome de n.
  2. Étant donné un entier n, écrire une fonction vnpalind qui renvoie la liste constituée de n, de sa valeur palindromique et de son nombre palindromique.
    Attention
    L’arrêt du processus est une conjecture. Prévoir un contrôle stoppant la boucle au delà de p étapes et renvoyant alors la liste .
  3. Explorer pour p=300 le cas des 100 premiers entiers (non nuls).
  4. Quels sont les entiers qui n’ont pas obtenu de nombre palindrome parmi les 1000 premiers entiers ?

19.3  Les dessins récursifs

19.3.1  Les segments

  1. Une spirale
    L’utilisateur choisit un réel a ∈ ]0;1[. Soit un point M0 d’affixe un réel z0>0 et les points Mk d’affixe zk=rkexp(ikπ/3) avec rk=a*rk−1.
    Écrire un programme qui réalise le dessin du point M0 et des p segments MkMk−1 pour k=1..p.

    On a donc zk==a*rk−1exp(i(k−1)π/3)exp(iπ/3)==aexp(iπ/3)zk−1 On peut faire soit un programme itératif, soit un programme récursif.
    On tape pour le programme itératif :

    segmenti(a,z0,p):={
    local L,k;
    point(z0);
    L:=NULL;
    pour k de 1 jusque p faire 
    L:=L,segment(z0,a*z0*exp(i*pi/3));
    z0:=a*z0*exp(i*pi/3);
    fpour;
    retourne L;
    }
    :;
    

    Pour le programme récursif : On peut décider d’avoir le dessin récursif seulement dans l’écran DispG : le programme est plus simple car toutes les instructions graphiques sont exécutées dans cet écran. On renvoie 1 pour que l’on puisse vérifier que la procédure s’est bien exécutée.
    On tape :

    segmentg(a,z0,p):={
      point(z0);
      si p>0 alors 
        segment(z0,a*z0*exp(i*pi/3));
        segmentg(a,a*z0*exp(i*pi/3),p-1);
      fsi;
      retourne 1;
    }
    :;
    

    Ou bien on met les différentes instructions graphiques à réaliser dans une liste L.
    On tape :

    segmentr(a,z0,p):={
      local L;
      si p==0 alors retourne point(z0); fsi;
      L:=segment(z0,a*z0*exp(i*pi/3)),segmentr(a,a*z0*exp(i*pi/3),p-1);
      retourne L;
    }
    :;
    

    Puis on tape :
    segmenti(0.8, 20, 30) ou
    segmentg(0.8, 20, 30) ou
    segmentr(0.8, 20, 30)

  2. Une autre spirale
    À partir d’un point M0 de coordonnées (x0,0) et d’un réel 0<k<1, on définit les points : M1 de coordonnées (0,kx0)
    M2 de coordonnées (−k2x0,0)
    M3 de coordonnées (0,−k3x0)
    M4 de coordonnées (k4x0,0)
    etc
    Écrire un programme qui dessine n segments MkMk+1
    On peut remarquer que l’affixe de Mk+1 se déduit de celui de Mk par une multiplication par i*k.
    On tape un programme itératif :
    spirali(x0,k,n):={
    local k,L;
    pour k de 1 jusque n faire 
     L:=L,segment(x0,i*k*x0);
     x0:=i*k*x0;
    }
    retourne L;
    }:;
    
    On tape un programme récursif :
    spiralr(x0,k,n):={
     si n<=0 alors retourne point(x0); fsi;
     retourne segment(x0,i*k*x0),spiralr(i*k*x0,k,n-1);
    }:;
    
  3. Une maison Soient A=(0,0) et B=(1,0). À partir du vecteur AB, on construit une maison c’est à dire les murs sont un carré direct ABEC et le toit est un triangle isocèle CED.
    On trace les segments AC et BE et on recommence la même opération avec les vecteurs CD et DE etc...On s’arrête en tracant le segment correspondant à AB
    Écrire un programme qui réalise ce dessin au bout de n fois.
    On tape un programme récursif (pour éviter des calculs trop long, on travaille en mode approché en mettant A:=evalf(A); B:=evalf(B);) :
    maison(A,B,n):={
     local C,D,E,L;
     A:=evalf(A); B:=evalf(B);
     si n<=0 alors retourne segment(A,B); fsi;
     C:=rotation(A,pi/2,B);
     E:=rotation(B,-pi/2,A);
     D:=similitude(C,sqrt(2)/2,pi/4,E);
     L:=segment(A,C),segment(B,E);
     L:=L,maison(C,D,n-1),maison(D,E,n-1);
     retourne L;
    }:;
    
    On peut transformer cet exercice en un exercice sur les complexes en demandant de calculer les affixes de C,D,E en fonction des affixes de A et B. On tape un programme récursif :
    maisonee(A,B,n):={
     local C,D,E,L,za,zb,zc,zd,ze;
     si n<=0 alors retourne segment(A,B); fsi;
     za:=affixe(A);
     zb:=affixe(B);
     zc:=normal(za+i*(zb-za));
     ze:=normal(zb+i*(zb-za));
     zd:=normal(3*i*(zb-za)/2+(za+zb)/2);
     C:=point(zc);
     E:=point(ze);
     D:=point(zd);
     L:=segment(A,C),segment(B,E);
     L:=L,maisonee(C,D,n-1),maisonee(D,E,n-1);
     retourne L;
    }:;
    

19.3.2  Les carrés

On veut réaliser le dessin récursif dont on a mis ci-dessous les premières étapes (profondeur 0,1 et 2):

On peut décider d’avoir le dessin récursif seulement dans l’écran DispG : le programme est plus simple car toutes les instructions graphiques sont exécutées dans cet écran.
On appelle cette procédure carresg(a,d,f)a est l’affixe du sommet en bas à gauche du grand carré, d est la longueur de son côté et f donne la longueur du côté du plus petit carré. carresg(a,d,f) renvoie 1 pour que l’on puisse vérifier que la procédure s’est bien exécutée.
On tape :

carresg(a,d,f):={
  si d>=f alors 
    carre(a,a+d);
    carresg(a-d/2,d/2,f);
    carresg(a+i*d,d/2,f);
    carresg(a+d/2-i*d/2,d/2,f);
    carresg(a+d+i*d/2,d/2,f);
  fsi;
  retourne 1;
}:;

On tape : carresg(0,40,2)
L’écran DispG s’ouvre et l’on voit le dessin se faire....

On met les différentes instructions graphiques à réaliser dans une liste L. On appelle cette procédure carres(a,d,f)a est l’affixe du sommet en bas à gauche du grand carré, d est la longueur de son côté et f donne la longueur du côté du plus petit carré. carresg(a,d,f) renvoie la liste L.
On tape :

carres(a,d,f):={
  local L;
  si d<f alors retourne NULL fsi;
  L:=carre(a,a+d),carres(a-d/2,d/2,f),carres(a+i*d,d/2,f),
   carres(a+d/2-i*d/2,d/2,f),carres(a+d+i*d/2,d/2,f);
  retourne L;
}
:;

On tape : carres(0,40,2)

On peut aussi choisir comme paramètre la profondeur n du dessin récursif au lieu de f. On tape :

carren(a,d,n):={
local L;
si n=<0 alors retourne NULL fsi;
L:=carre(a,a+d),carren(a-d/2,d/2,n-1),carren(a+i*d,d/2,n-1),
   carren(a+d/2-i*d/2,d/2,n-1),carren(a+d+i*d/2,d/2,n-1);
retourne L;
}
:;

On tape : carren(0,40,4)

19.3.3  Les triangles

On veut réaliser le dessin récursif dont on a mis ci-dessous les premières étapes (profondeur 0,1,2 et 3) :

On peut décider d’avoir le dessin récursif seulement dans l’écran DispG : le programme est plus simple car toutes les instructions graphiques sont exécutées dans cet écran.
On appelle cette procédure triang(a,d,f)a est l’affixe du sommet en bas à gauche du grand triangle, d est la longueur de son côté et f donne la longueur du côté du plus petit triangle. triang(a,d,f) renvoie 1 pour que l’on puisse vérifier que la procédure s’est bien exécutée.
On tape :

triang(a,d,f):={
  si d>=f alors 
    triangle_equilateral(a,a+d);
    triang(a,d/2,f);
    triang(a+d/4+i*d*sqrt(3.)/4,d/2,f);
    triang(a+d/2,d/2,f);
  fsi;
  retourne 1;
}:;

On tape : triang(0,40,2)
L’écran DispG s’ouvre et l’on voit le dessin se faire....On met les différentes instructions graphiques à réaliser dans une liste. On appelle cette procédure triangles(a,d,f)a est l’affixe du sommet en bas à gauche du grand triangle, d est la longueur de son côté et f donne la longueur du côté du plus petit triangle.
On tape :

triangles(a,d,f):={
  local L;
  si d<f alors retourne NULL fsi;
  L:=triangle_equilateral(a,a+d),triangles(a,d/2,f),
     triangles(a+d/4+i*d*sqrt(3.)/4,d/2,f),triangles(a+d/2,d/2,f);
  retourne L;
}
:;

On tape : triangles(0,40,2)

On peut aussi choisir comme paramètre la profondeur n du dessin récursif au lieu de f. On tape :

trianglen(a,d,n):={
local L;
si n<0 alors retourne NULL fsi;
L:=triangle_equilateral(a,a+d),trianglen(a,d/2,n-1),
trianglen(a+d/4+i*d*sqrt(3.)/4,d/2,n-1),trianglen(a+d/2,d/2,n-1);
retourne L;
}
:;

On tape : trianglen(0,40,4)

19.3.4  Exercice

Écrire un programme qui réalise le dessin récursif dont on a mis ci-dessous les premières étapes (profondeur 0, 1 et 2) :

On tape :

triequi(A,B,n):={
local C,L,A1,B1,C1;
L:=triangle_equilateral(A,B,C);
si n>0 alors 
A1:=homothetie(C,-0.5,A);
B1:=homothetie(A,-0.5,B);
C1:=homothetie(B,-0.5,C);
L:=L,triequi(A1,C,n-1);
L:=L,triequi(B1,A,n-1);
L:=L,triequi(C1,B,n-1);
fsi;
retourne L;
}:;

On tape : triequi(0,1,5)
On obtient :

On tape : triequi(0,1+0.35*i,5)
On obtient :

19.3.5  Des triangles équilatéraux emboiés

À partir d’un triangle équilatèral direct ABC on construit les points A1,B1,C1 vérifiant :
AA1=4/3AB
BB1=4/3BC
CC1=4/3CA
Interprétez A1 comme le barycentre de A,a et B,b. Montrer que le triangle A1B1C1 estéquilatèral.
On recommence la même construction à partir de A1B1C1.
Écrire la procédure récursive qui réalise le dessin des n triangles obtenus par cette construction (en tout n+1 triangles ABC + les autres).
On a :
AA1=4/3AB−1/3AA
Donc A1 est le barycentre de A,−1 et B,4.
Donc B1 est le barycentre de B,−1 et C,4
Donc C1 est le barycentre de C,−1 et A,4.
La rotation r de centre O, le centre de ABC, et d’angle 2π/3 transforme A en B, B en C et C en A donc r transforme le barycentre de A,−1 et B,4 en le barycentre de B,−1 et C,4 c’est à dire transforme A1 en B1 et r transforme le barycentre de B,−1 et C,4 en le barycentre de C,−1 et A,4 c’est à dire transforme B1 en C1.
Donc le triangle A1B1C1 estéquilatèral.
On tape dans l’éditeur de programmes :

triangles(A,B,n):={
  local L,C;
  L:=triangle_equilateral(A,B,C);
  si n>0 alors 
    A:=barycentre([A,B],[-1,4]);
    B:=barycentre([B,C],[-1,4]);
    L:=L,triangles(A,B,n-1);
  fsi;
  return L;
}:;

puis on compile avec F9 et dans une ligne de commande, on tape :
triangles(point(0),point(1),5) On obtient :

19.3.6  Le problème des 3 insectes

Trois insectes partent, des sommets d’un triangle équilatéral A,B,C en direction de son voisin (C regarde B. B regarde C. A regarde C). À chaque étape de leur marche les 3 insectes forment un triangle équilatéral.
Dessiner les trajectoires des 3 insectes en résolvant une équation différentielle ou un système d’équations différentielles.
On peut faire une simulation de la situation en supposant que chaque insecte :
- regarde son voisin ce qui lui donne sa direction, puis,
- avance dans cette direction d’une longueur proprortionnelle au côté du triangle, puis , - regarde son voisin ce qui lui donne sa nouvelle direction etc...
Faire un programme qui dessine les triangles étapes de cete marche.
Refaire le même exercice en remplaçant le triangle équilatéral A,B,C par un triangle rectangle isocèle.
Résolution de 3 équations différentielles
Les trois insectes ont des trajectoires qui se déduisent l’une de l’autre par une rotation de centre G le centre de gravité du triangle et d’angle −2*π/3.
Si zA est l’affixe du point A et zB celle du point B..., on a :
zA′=zCzA
zB′=zAzB
zC′=zBzC
donc zA′+zB′+zC′=0 et donc
zA+zB+zC=cste=1+1/2+i3 /2=3*zG
On a :
zCzG=exp(−2*π/3)(zAzG)
(zAzG)′=zCzA=(zCzG)−(zAzG)=(exp(−2*π/3)−1)(zAzG).
zG=−(3+i3)/6
au temps t=0 on a : zA=0, zB=1, zC=1/2+i3/3
On tape (on suppose que l’on a coché complexe dans la configuration du CAS) :
triangle_equlateral(0,1)
zG:=(3+i*sqrt(3))/6
SA:=simplify(desolve([diff(z(t),t)=(exp(-2*i*pi/3)-1)*(z(t)-zG),
         z(0)=0],[t,z]))

SB:=simplify(desolve([diff(z(t),t)=(exp(-2*i*pi/3)-1)*(z(t)-zG),
         z(0)=1],[t,z]))

SC:=simplify(desolve([diff(z(t),t)=(exp(-2*i*pi/3)-1)*(z(t)-zG),
         z(0)=1/2+i*sqrt(3)/2],[t,z]))

On obtient :
plotparam(SA[0],t=0..4),plotparam(SB[0],t=0..4),
plotparam(SC[0],t=0..4)

On obtient :

Résolution d’un système d’équations différentielles
On peut aussi résoudre le système :
Z′=A*Z et au temps t=0, Z(0)=[0,1,1/2+i*√3 /2] avec

A:=


−11
0−1
10−1



On tape (on suppose que Complexe est coché dans la configuration du CAS ):
A:=[[-1,1,0],[0,-1,1],[1,0,-1]]
P,B:=jordan(A)
On obtient pour P :
[[1,(-i)*sqrt(3)-1,(i)*sqrt(3)-1],[1,2,2],[1,(i)*sqrt(3)-1, (-i)*sqrt(3)-1]]
On obtient pour B :
[[0,0,0],[0,((i)*sqrt(3)-3)/2,0],[0,0,((-i)*sqrt(3)-3)/2]]
On tape :
V0:=simplify(inv(P)*[0,1,1/2+i*sqrt(3)/2])
On obtient :
[((i)*sqrt(3)+3)/6,((-i)*sqrt(3)+3)/12,0]
On tape :
V:=V0*exp(B*t)
On obtient :
[1/6*((i)*sqrt(3)+3),1/12*exp(((i)*sqrt(3)*t-3*t)/2)*((-i)*sqrt(3)+3),0]
On tape :
Z:=P*V
ZA:=simplify(Z[0]);ZB:=simplify(Z[1]);ZC:=simplify(Z[2]);
plotparam(ZA,t=0..4),plotparam(ZB,t=0..4),plotparam(ZC,t=0..4), triangle_equilateral(0,1)
On obtient la figure précédente.

Dans le cas du triangle ABC avec
A:=point(0);B:=point(10);C:=point(i*10), le système à resoudre est le même c’est juste la condition initiale qui change (V0:=inv(P)*[0,1,i]) et les 3 insectes convergent vers le centre de gravité K du triangle ABC.
On tape (on suppose que Complexe est coché dans la configuration du CAS ):
A:=[[-1,1,0],[0,-1,1],[1,0,-1]]
P,B:=jordan(A)
V0:=simplify(inv(P)*[0,1,i])
On obtient :
[(1+i)/3,(sqrt(3)+2-i)/12,(-sqrt(3)+2-i)/12]
V:=V0*exp(B*t)
On obtient :
[(1+i)/3,1/12*exp(((i)*sqrt(3)*t-3*t)/2)*(sqrt(3)+2-i), 1/12*exp(((-i)*sqrt(3)*t-3*t)/2)*(-sqrt(3)+2-i)]
On tape :
Z:=P*V
ZA:=simplify(Z[0]);ZB:=simplify(Z[1]);ZC:=simplify(Z[2]);
plotparam(ZA,t=0..4),plotparam(ZB,t=0..4),plotparam(ZC,t=0..4), triangle(0,1,i)
On obtient la figure :

Le dessin des triangles
On dessine le triangle équilatéral ABC puis le triangle A1B1C1 avec :
A1=A+evalf((BA)/10),
B1=B+evalf((CB)/10) et
C1=C+evalf((AC)/10).
puis on recommence le même processus avec A1B1C1... On tape :

triop0(a,b):={
local L,C,c;
L:=triangle_equilateral(point(a),point(b),C);
c:=evalf(affixe(C));
si evalf(abs(b-a))<1 alors return L; fsi;
a:=a*0.9+b*0.1;
b:=b*0.9+c*0.1;
L:=L,triop0(a,b);
return L;
}:;

On tape :
triop0(0,10)
On obtient :

On peut tourner dans l’autre sens : on dessine le triangle équilatéral ABC puis le triangle A1B1C1 avec :
A1=A+evalf((CA)/10),
B1=B+evalf((AB)/10) et
C1=C+evalf((BC)/10).
puis on recommence le même processus avec A1B1C1... On tape :

triop(a,b):={
local L,C,c,a0;
L:=triangle_equilateral(point(a),point(b),C);
c:=evalf(affixe(C));
si evalf(abs(b-a))<1 alors return L; fsi;
a0:=a;
a:=a*0.9+c*0.1;
b:=b*0.9+a0*0.1;
L:=L,triop(a,b);
return L;
}:;

On tape :
triop(0,10)
On obtient :

On tape si on choisit un triangle ABC quelconque :

triopa(a,b,c):={
local L,a0,b0;
L:=triangle(point(a),point(b),point(c));
si (evalf(abs(b-a))<1) alors return L; fsi;
a0:=a;
b0:=b;
a:=a+evalf((c-a)/10);
b:=b+evalf((a0-b)/10);
c:=c+evalf((b0-c)/10);triopa(0,10,i*10);K:=point((10+10*i)/3)
L:=L,triopa(a,b,c);
return L;
}
:;

On tape :
triopa(0,10,i*10);K:=point((10+10*i)/3)
On obtient :

On fait faire des rotations à ces triangles
Dans triops on fait 6 rotations de triop alors que dans triops0 on fait 3 rotations du losange formé par triop0(a,b) et triop(b,a)
0n tape :

triops(A,B):={
local L,j,a,b;
a:=affixe(A);
b:=affixe(B);
L:=triop0(a,b);
pour j de 1 jusque 5 faire
B:=rotation(A,pi/3,B);
b:=affixe(B);
L:=L,triop(a,b);
fpour;
return L;
}:;
triops0(A,B):={
local L,j,a,b;
a:=affixe(A);
b:=affixe(B);
L:=NULL;
pour j de 1 jusque 3 faire
L:=L,triop0(a,b),triop(b,a);
B:=rotation(A,pi/3,B);
b:=affixe(B);
fpour;
return L;
}:;
triops1(A,B):={
local L,j,a,b,c,C;
a:=affixe(A);
b:=affixe(B);
L:=NULL;
pour j de 1 jusque 3 faire
triangle_equilateral(B,A,C);
c:=affixe(C);
L:=L,triop0(a,b),triop(b,a),,triop0(a,c);
B:=rotation(A,2*pi/3,B);
b:=affixe(B);
fpour;
return L;
}:;

On tape :
triops(point(0),point(10))
On obtient :
On tape :
triops0(point(0),point(10))
On obtient :

On tape :
triops1(point(0),point(10))
On obtient :

0n tape :

triopas(A,B,C):={
local L,j,F,a,b,c;
a:=affixe(A);
b:=affixe(B);
c:=affixe(C);
L:=triopa(a,b,c);
pour j de 1 jusque 7 faire
A:=rotation(B,pi/4,A);
C:=rotation(B,pi/4,C);
a:=affixe(A);
c:=affixe(C);
L:=L,triopa(a,b,c);
fpour;
return L;
}:;

On tape :
triopas(point(0),point(10),point(10*i))
On obtient :

Avec le triangle point(0),point(10),point(i*10*tan(2*pi/7)), on tape :

triopas7(A,B,C):={
local L,j,F,a,b,c;
a:=affixe(A);
b:=affixe(B);
c:=affixe(C);
L:=triopa(a,b,c);
pour j de 1 jusque 6 faire
A:=rotation(B,2*pi/7,A);
C:=rotation(B,2*pi/7,C);
a:=affixe(A);
c:=affixe(C);
L:=L,triopa(a,b,c);
fpour;
return L;
}:;

Puis, on tape :
triopas7(point(0),point(10),point(i*10*tan(2*pi/7)));
On obtient :
On peut aussi faire la mêmes chose ave des losanges
On tape :

losop(a,b,c,d):={
local L;
L:=quadrilatere(point(a),point(b),point(c),point(d));
si evalf(abs(b-a))<1 alors return L; fsi;
a:=a*0.9+b*0.1;
b:=b*0.9+c*0.1;
c:=c*0.9+d*0.1;
d:=d*0.9+a*0.1;
L:=L,losop(a,b,c,d);
return L;
}:;

On tape :
losop(0,10,5+i*sqrt(3)*5,-5+i*sqrt(3)*5)
On obtient :

On tape :
losop(10,0,-5+i*sqrt(3)*5,5+i*sqrt(3)*5),
losop(10,0,-5-i*sqrt(3)*5,5-i*sqrt(3)*5),
losop(-5+i*sqrt(3)*5,0,-5-i*sqrt(3)*5,-10)

On obtient :

19.3.7  Les cercles

L’utilisateur choisit un entier n. Sur le cercle de de centre d’affixe a et de rayon r on dessine le cercle et les n points d’affixe ak:=r*exp(2.*i*k*pi/n) pour k=0..n-1. On recommence pour chaque k avec des cercles de de centre d’affixe ak et de rayon r/2. Et ainsi de suite à partir des points obtenus en divisant à chaque étape le rayon par 2. Écrire un programme qui réalise p étapes de ce processus. On tape :

cercles(a,r,n,p):={
local P,L,k,j;
P:=NULL;
si p<1 alors retourne NULL fsi;
pour k de 0 jusque n-1 faire
  P:=P,point(a+r*exp(2.*i*pi*k/n),affichage=p+epaisseur_point_2);
fpour;
L:=cercle(a,r),P;
pour j de 0 jusque n-1 faire
  L:=L,cercles(affixe(P[j]),r/2,n,p-1);
fpour;
retourne L;
}:;

On tape :
cercles(0,20,5,4)
On obtient :

19.4  Les tours de Hanoï

Une tour de Hanoï est composée de p disques de rayons différents que l’on numérote de 1 à p selon l’ordre croissant des rayons (le plus petit disque a le numéro 1 et le plus gros le numéro p). On dispose de 3 plots numérotés de 1 à 3.
Au départ les disques sont empilés selon l’ordre croissant sur le plot 1.
Le jeu consiste à reconstituer la tour sur le plot 2, en se servant du plot 3 comme plot intermédiaire, en déplacant les disques un à un, et en posant toujours un disque sur un disque plus petit que lui.
Par exemple, on peut mettre le dique 2 sur le disque 5, mais pas sur le disque 1.
On veut écrire un programme qui imprime ce qu’il faut faire comme manipulations : ce sera tour(a,b,c,p), où p représente le nombre de disques, où a représente le plot de départ, où b représente le plot d’arrivée, et où c représente le plot intermédiaire.
On tapera alors par exemple :
tour(1,2,3,4)
si on a une tour de 4 disques sur le plot 1, et qu’on veut la reconstituer sur le plot 2 par l’intermédiaire du plot 3.
Les manipulations à faire sont récursives, en voici les étapes :

On tape dans un niveau éditeur de programmes (que l’on ouvre avec Alt+p), puis on le teste et on le valide avec OK :

//tour(1,2,3,4) (tour de hanoi)
//depacement des p disques (de numero 1..p du plus petit au plus grand) 
//de a vers b en passant par c
tour(a,b,c,p) :={
  if (p==0) return 0;
  tour(a,c,b,p-1);
  print("deplacer le disque "+p+" de "+ a + " vers "+ b);
  tour(c,b,a,p-1);
  return 0;
}:;

On tape :
tour(1,2,3,4)
On obtient :

deplacer le disque 1 de 1 vers 3
deplacer le disque 2 de 1 vers 2
deplacer le disque 1 de 3 vers 2
deplacer le disque 3 de 1 vers 3
deplacer le disque 1 de 2 vers 1
deplacer le disque 2 de 2 vers 3
deplacer le disque 1 de 1 vers 3
deplacer le disque 4 de 1 vers 2
deplacer le disque 1 de 3 vers 2
deplacer le disque 2 de 3 vers 1
deplacer le disque 1 de 2 vers 1
deplacer le disque 3 de 3 vers 2
deplacer le disque 1 de 1 vers 3
deplacer le disque 2 de 1 vers 2
deplacer le disque 1 de 3 vers 2

19.5  Les permutations

19.5.1  Les permutations circulaires

La liste l est une liste de nombres tous différents.
On écrit la fonction circulaire(l) qui renvoie la liste obtenue à partir de l en renvoyant le début de la liste l à la fin de l.

//l:=[1,2,3]; circulaire(l) 
//renvoie la liste l ou la tete est mise a la fin. 
circulaire(l):={
return concat(tail(l),l[0]);
};

On écrit la fonction permcir(l) qui renvoie la liste des permutations circulaires obtenues à partir de l. On écrit cette fonction récursivement en renplacant l par circulaire(l). Il faut un test d’arrêt pour ce parcours, pour cela on a besoin d’un paramètre supplementaire qui sera ld : c’est une liste de référence égale à l au départ et qui n’est pas modifiée. On s’arrête quand circulaire(l)==ld, c’est à dire quand on retrouve la liste de départ. On utilise une variable locale lr égale à la liste à renvoyer.

// utilise circulaire, l:=[1,2,3];permcir(l,l); 
//renvoie les permutations circulares de l
//variable locale lr la liste resultat
// ld liste reference de depart
permcir(l,ld):={
local lr;
if (circulaire(l)==ld) return [l];
lr:=[l];
lr:= append(lr,op(permcir(circulaire(l),ld)));
return lr;
};

On peut supprimer la variable locale lr et la fonction circulaire.
On écrit alors la fonction permcc(l) qui renvoie la liste des permutations circulaires obtenues à partir de l.
Ici, on utilise un autre test d’arrêt, on a toujours besoin d’un paramètre supplementaire qui sera ld : c’est une liste de référence égale à l au départ et qui est modifiée, sa taille diminue de 1 à chaque appel récursif. On s’arrête quand ld==[], c’est à dire quand on a fait autant d’appels que la taille de l.

//l:=[1,2,3];permcc(l,l); 
//renvoie les permutations circulares de l
//sans variable locale, ld liste reference de depart
permcc(l,ld):={
if (ld==[]) return [];
return [l,op(permcc(concat(tail(l),l[0]),tail(ld)))];
};

Comme il faut 2 paramètres pour écrire la fonction récursive permcc, on écrit la fonction finale permutation_circ qui utilise permcc :

//l:=[1,2,3];permutation_circ(l); 
//renvoie les permutations circulares de l
//utilise permcc
permutation_circ(l):={
return permcc(l,l);
};

On tape :
permutation_circ([1,2,3])
On obtient :
[[1,2,3],[2,3,1],[3,1,2]]

19.5.2  Programme donnant toutes les permutations d’une liste l

La liste l est une liste de nombres tous différents.
1/ En faisant n=size(l) appels récursifs.
Les fonctions que l’on va écrire vont utiliser la fonction echange.

//echange ds l les elements d'indices j et k
echange(l,j,k):={
local a;
a:=l[j];
l[j]:=l[k];
l[k]:=a;
return l;
}:;

On peut décrire l’arbre des permutations de la liste l :
à partir de la racine on a n=size(l) branches. Chaque branche commence respectivement par chacun des éléments de la liste l.
On va donc parcourir cet arbre de la racine (nœud de niveau 0) aux différentes extrémités, en renvoyant la liste des branches parcourues pour arriver à cette extrémité.
On va parcourir cet arbre en parcourant les n branches. On numérote ces n branches par p=1..n et le niveau des nœuds q=0..n−1.
On aura donc n appels récursifs.
Chaque branche p (p=1..n) peut être considérée à leur tour comme un arbre ayant n−1 branches. La branche p aboutit aux permutations qui laissent invariant le p-ième élément de l (l[p−1]). C’est cet élément que l’on va échanger avec l[0] pour que chaque branche p laisse invariant l’ élément l[0].
On sait que l’on est arrivé au bout de la branche, quand on se trouve au nœud de niveau n−1, dans ce cas la permutation chechée est l (c’est la permutation obtenue à partir de l en laissant ces n−1 premiers éléments invariants).
On utilise une variable locale lr, égale à la liste à renvoyer et un paramètre k, pour que permus(l,k) renvoie toutes les permutations de l qui laissent invariant les k premiers éléments de l. On tape :

//utilise echange et la variable locale lr (liste resultat)
//permus(l,k) laisse invariant les k premiers elements de l
//permus([1,2,3,4],0); renvoie toutes les permutations de l 
permus(l,k):={
local lr,j;
if (k==size(l)-1) return [l];
lr:=[];
for (j:=k;j<size(l);j++){
l:=echange(l,k,j);
lr:=[op(lr),op(permus(l,k+1))];
l:=echange(l,j,k);
}
return lr;
}:;

On n’est pas obligé de remettre la suite l à sa valeur de départ pour recommencer l’itération puisque le premier échange dans l’itération revient à transformer l en la liste où on a mis son j-ième élément en tête (j=0..n−1). La liste résultat ne sera alors pas dans le même ordre. Si on veut avoir la liste dans l’ordre lexicographique, il ne faut pas mettre la deuxième instruction echange. En effet :
sans la deuxième instruction echange, on échange 0 et 1 pour j=1 ([1,0,2..]) puis 0 et 2 pour j=2 ([2,0,1..]) etc sans la deuxième instruction echange, on échange 0 et 1 ([1,0,2..]) puis, 1 et 0 ([0,1,2..]) pour j=1, puis 0 et 2 ([2,1,0..]) puis, 2 et 0 ([0,1,2..]) pour j=2 etc

//permuts([1,2,3,4],0) utilise echange 
//la 2ieme instruction echange est inutile
permuts(l,k):={
local lr,j;
if (k==size(l)-1) return [l];
lr:=[];
for (j:=k;j<size(l);j++){
l:=echange(l,k,j);
lr:=[op(lr),op(permuts(l,k+1))];
}
return lr;
}:;

Comme il faut 2 paramètres pour écrire la fonction récursive permuts, on écrit la fonction permutation qui utilise permuts:

//l:=[1,2,3];permutation(l); 
//renvoie toutes les permutations de l
//utilise permuts
permutation(l):={
return permuts(l,0);
};

On tape :
permutation([1,2,3])
On obtient :
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
On peut aussi écrire une autre fonction récursive ayant comme paramètre ld et lf. ld contient les premières valeurs de l qui seront inchangées dans la permutation et lf contient les valeurs restantes de l, celles qui restent à permuter. On remarquera que le résultat mis dans res est ici une séquence.

//au debut ld=[] et lf=l,
//groupe_s([],l) renvoie toutes les permutations de l
groupe_s(ld,lf):={
 local j,n,res;
 n:=size(lf);
 res:=NULL;
 if (n==1)
   return concat(ld,lf);
 for (j:=0;j<n;j++){
   res:=res,groupe_s(append(ld,lf[0]),tail(lf));
   // permutation circulaire
   lf:=append(tail(lf),lf[0]);
 }
 return res;
};

Et la fonction groupesym qui utilise la fonction récursive groupe_s :

//utilise groupe_s
//groupesym(l) renvoie toutes les permutations de l
groupesym(l):=return(groupe_s([],l));

2/ En faisant 2 appels récursifs.
Cet algorithme est surtout fait pour des langages qui n’ont pas de boucle for.
Les fonctions vont utiliser la fonction circulaire (pour plus de clareté), puis on remplacera circulaire(l) par concat(tail(l),l[0]).

//l:=[1,2,3]; circulaire(l) 
//renvoie la liste l ou la tete est mise a la fin. 
circulaire(l):={
return concat(tail(l),l[0]);
};

On peut décrire l’arbre des permutations de la liste l :
à partir de la racine on a n=size(l) branches. Chaque branche commence par chacun des éléments de la liste l.
On va parcourir cet arbre, en parcourant la premiére branche, puis en considérant qu’il reste à parcourir un arbre de n−1 branches.
On aura donc 2 appels récursifs.
Pour le parcours de la première branche, il faut connaitre la liste des éléments qui nous a permis d’arriver à un nœud donné, c’est cette liste que l’on met dans ldl, l contenant les éléments qu’il faut encore permuter. On s’arrête quand l=[], et le résultat est [ldl].
Pour le parcours des n−1 branches restantes, on change pour chaque branche la liste à permuter en circulaire(l).
Il faut un test d’arrêt pour ce parcours, pour cela on a besoin d’un paramètre supplementaire qui sera ld (liste de référence égale à l au départ) dans permss ou qui sera n (longueur de l au départ) dans permss1.
On écrit permss :

// utilise circulaire, l:=[1,2];permss([],l,l);
//ldl=debut de l, l=liste a permuter, 
//ld=liste de reference (=l au debut)
permss(ldl,l,ld):={
if (l==[]) return [ldl];
if (ld==[]) return ld;
return [op(permss(concat(ldl,l[0]),tail(l),tail(l))),
        op(permss(ldl,circulaire(l),tail(ld)))];
};

On écrit permss1 qui utilise comme paramètre n qui représente la longueur de la liste qui reste à permuter (n=size(l) au départ) :

//utilise circulaire, l:=[1,2,3,4];permss1([],l,size(l)); 
//ldl=debut de l, l=liste a permuter, n=size(l) au debut
permss1(ldl,l,n):={
if (l==[]) return [ldl];
if (n==0) return [];
return [op(permss1(concat(ldl,l[0]),tail(l),size(tail(l)))),
        op(permss1(ldl,circulaire(l),n-1))];
};

On a aussi écrit la fonction permss2 contenant une variable locale lr qui est la liste à renvoyer et qui donne un algorithme plus lisible.

//l:=[1,2];permss2([],l,l); 
//ldl=debut de l, l=liste a permuter,
//ld=liste de reference (=l au debut)
// lr liste a renvoyer en variable locale
permss2(ldl,l,ld):={
local lr;
if (l==[]) return [ldl];
if (ld==[]) return [];
lr:=permss2(concat(ldl,l[0]),tail(l),tail(l));
lr:=append(lr,op(permss2(ldl,concat(tail(l),l[0]),tail(ld))));
return lr
};

puis la fonction permute qui utilise permss2 :

//utilise permss2, 
//permute(l) renvoie toutes les permutations de l
permute(l):={
return permss2([],l,l);
};

On tape :
permute([1,2,3])
On obtient :
[[1,2,3],[1,3,2],[2,3,1],[2,1,3],[3,1,2],[3,2,1]]


Previous Up Next