Exercice 2

1. On obtient

2. On a
3. La sustitution correspond à l'échange de 2 et 3. La substitution à l'échange de 1 et 2. On a donc

4. On obtient en ne tenant pas compte des barres

5. On utilise trois piles u,v,w correspondant aux piquets 1,2,3. Le déplacement d'une rondelle de a vers b ou l'inverse s'écrit:

    procedure transfert (var a, b: tableau);
    begin
     if a.tab[a.top] > b.tab[b.top] then begin
       b.top := b.top + 1;
       b.tab[b.top] := a.tab[a.top];
       a.top := a.top - 1
      end
     else  begin
       a.top := a.top + 1;
       a.tab[a.top] := b.tab[b.top];
       b.top := b.top - 1;
      end;
     writeln(u.top, v.top, w.top);
    end;

   Dans le cas d'un nombre impair de rondelles, on utilise la procédure

    procedure impair;
     var
      j: integer;
    begin
     for j := 1 to N do  i := 2 * i;
     for j := 1 to (i - 2) div 3 do begin
   {a} transfert(u, w);
   {b} transfert(u, v);
   {c} transfert(v, w);
      end;
   {a} transfert(u, w);
    end;

   et dans le cas d'un nombre pair :

    procedure pair;
     var
      j: integer;
    begin
     i := 1;
     for j := 1 to N do  i := 2 * i;
     for j := 1 to (i - 1) div 3 do  begin
   {b} transfert(u, v);
   {a} transfert(u, w);
   {c} transfert(v, w)
      end;
    end;

   Le programme principal s'écrit tout simplement

   begin
    write('donnez le nombre de jetons :  ');
    readln(N);
    init;
    if odd(N) then
     impair
    else
     pair;
   end.