Corrigé des Exercices (pc3)

Exercice 1 La solution consiste à écrire une fonction I(s, k) dans laquelle on cherche à atteindre la somme s en utilisant w[k], …, w[n]. On a la relation de récurrence :

I(s, k) = I(s, k + 1) ∨ I(s − w[k], k + 1)

d’où le programme :

int chiffres(int s, int k) {
  if (s == 0)
   chiffres = 1;
  else if (s < 0 || k > n)
   chiffres = 0;
  else
  if chiffres(s-w[k],k+1) {
     printf("%d",w[k]);
     chiffres = 1;
   }
   else
    chiffres = chiffres(s, k+1);
}

Exercice 2

1. On obtient

h_{4} = bacbāc̄bacb̄ācbac

2. On a |h_{n}| = 2^{n} − 1

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

h_{n+1} = ϕ(h_{n})aψ(h_{n})

4. On obtient en ne tenant pas compte des barres

h_{n} = \{ \begin{matrix}(abc)^{i}a & si n impair \\ (bac)^{j} & sinon \end{matrix}

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.