Corrigé du partiel du 14 décembre 1996

Décomposition d’un entier

Saisie et affichage

1 Lecture d’une décomposition

PROGRAM Lecture;
VAR k, entier, somme : INTEGER;
BEGIN
Write('Nombre d'entiers à lire ? '); ReadLn(k);
somme := 0;
WHILE k > 0 DO
BEGIN
  Write('Un entier ? '); ReadLn(entier);
  somme := somme + entier;
  k := k - 1;   { il reste un entier de moins à lire }
END;
WriteLn('La somme est : ',somme);
END.

2 Vérification d’une décomposition

PROGRAM Vérification;
VAR n, k, indice, entier, somme : INTEGER;
BEGIN
Write('Entier à décomposer ? '); ReadLn(n);
Write('Longueur de la décomposition ? '); ReadLn(k);
somme := 0;
FOR indice := 1 TO k DO
BEGIN
  Write('Le ',indice,'-ième entier ? '); ReadLn(entier);
  somme := somme + entier;
END;
IF n = somme THEN WriteLn('C''est une décomposition de ',n)
ELSE       WriteLn('Ce n''est pas une décomposition de ',n);
END.

3 Lecture et stockage d’une décomposition

Remarque : si n < Nmax, alors la longueur de la décomposition est inférieure à Nmax.

PROGRAM Stockage;
CONST Nmax = 1000;
VAR LONG : INTEGER;

    TAB : ARRAY[1..Nmax] OF INTEGER;
    indice : INTEGER;
BEGIN
  Write('Longueur de la décomposition ? '); ReadLn(LONG);
  FOR indice := 1 TO LONG DO
  BEGIN
    Write('Le ',indice,'-ième entier ? '); ReadLn(TAB[indice]);
  END;
END.

4 Affichage d’une décomposition

PROGRAM Affichage; { sur plusieurs lignes }
CONST Nmax = 1000;
VAR LONG : INTEGER;
    TAB : ARRAY[1..Nmax] OF INTEGER;
    indice : INTEGER;
BEGIN
  { LONG et TAB sont donnés ici, avant le début du programme... }
  FOR indice := 1 TO LONG DO
    WriteLn('Le ',indice,'-ième entier est : ',TAB[indice]);
END.

ou bien

PROGRAM Affichage; { sur une seule ligne }
CONST Nmax = 1000;
VAR LONG : INTEGER;
    TAB : ARRAY[1..Nmax] OF INTEGER;
    indice : INTEGER;
BEGIN
  { LONG et TAB sont donnés ici, avant le début du programme... }
  FOR indice := 1 TO LONG-1 DO Write(TAB[indice],' ');
  WriteLn(TAB[LONG]);
END.

Calculs de décomposition antécédente

5 Calcul de la décomposition antécédente

Aide : On vérifie que si n = ∑_{i=1}^{k} u_{i}, alors n − 1 = ∑_{i=1}^{k−1} u_{i} + u_{k} − 1.

PROGRAM Antécédente;
CONST Nmax = 1000;
VAR LONG : INTEGER;
    TAB : ARRAY[1..Nmax] OF INTEGER;
    indice : INTEGER;
BEGIN

{ LONG et TAB sont donnés ici, avant le début du programme... }
IF TAB[LONG] = 1 THEN
  LONG := LONG - 1
ELSE
  TAB[LONG] := TAB[LONG] - 1;
END.

6 Affichage de la décomposition antécédente

PROGRAM AfficheAntécédente;
CONST Nmax = 1000;
VAR LONG : INTEGER;
  TAB : ARRAY[1..Nmax] OF INTEGER;
  indice : INTEGER;
BEGIN
{ Saisie de LONG et TAB }
Write('Longueur de la décomposition ? '); ReadLn(LONG);
FOR indice := 1 TO LONG DO
BEGIN
  Write('Le ',indice,'-ième entier ? '); ReadLn(TAB[indice]);
END;
{ Modification de LONG ou TAB }
IF TAB[LONG] = 1 THEN LONG := LONG - 1
ELSE TAB[LONG] := TAB[LONG] - 1;
{ Affichage de a(s) sur une seule ligne }
FOR indice := 1 TO LONG-1 DO Write(TAB[indice],' ');
WriteLn(TAB[LONG]);
END.

7 Énumération des antécédents

PROGRAM EnumèreAntécédents;
CONST Nmax = 1000;
VAR LONG : INTEGER;
  TAB : ARRAY[1..Nmax] OF INTEGER;
  indice : INTEGER;
BEGIN
{ Saisie de la suite s : LONG et TAB }
Write('Longueur de la décomposition ? '); ReadLn(LONG);
FOR indice := 1 TO LONG DO
BEGIN
  Write('Le ',indice,'-ième entier ? '); ReadLn(TAB[indice]);
END;
WHILE LONG > 0 DO
BEGIN
  { Affichage de s sur une seule ligne }
  FOR indice := 1 TO LONG-1 DO Write(TAB[indice],' ');
  WriteLn(TAB[LONG]);

    { Modification de LONG ou TAB pour remplacer s par a(s) }
    IF TAB[LONG] = 1 THEN LONG := LONG - 1
    ELSE TAB[LONG] := TAB[LONG] - 1;
  END;
END.

Énumération des décompositions

8 Descendants d’une suite

8.1 Nombre de descendants d’une suite s

On suppose que a(s′) = s, on a donc s′ descendant de s. Posons s = (u_{1}, ..., u_{k}) et s′ = (u′_{1}, ..., u′_{k′}). Il y a deux possibilités :

– a(s′) = (u′_{1}, ..., u′_{k′−1}). Ce qui signifie que k′ = k + 1 et que u′_{i} = u_{i} pour i ≤ k et u′_{k+1} = 1.

– a(s′) = (u′_{1}, ..., u′_{k′−1}, u′_{k′} − 1) Ce qui signifie que k′ = k et que u′_{i} = u_{i} pour i < k et u′_{k} = u_{k} + 1.

Ces deux cas correspondent à des suites différentes, il y a donc deux descendants possibles pour une suite donnée.

8.2 Énumération des décompositions

Si deux suites s′ et s′′ ont même descendant s, alors a(s) = s′ = s′′. Deux suites distinctes ne peuvent avoir de descendant commun.

Montrons par récurrence que n admet 2^{n−1} décompositions.

– Cas n = 1 : on sait que 0 < k ≤ n donc k = 1. On a alors ∑_{i=1}^{k} u_{i} = u_{1} = n = 1. Le nombre 1 admet une unique décomposition (1).

– Le nombre n + 1 admet K décompositions. Chacune est un descendant d’une décomposition de n. Il n’y a que 2 descendants possibles pour chaque, donc K ≤ 2.2^{n−1}. Chaque descendant d’une décomposition de n est une décomposition de n + 1, donc K ≥ 2.2^{n−1}. D’où K = 2^{n}.

9 Calcul des descendants

On va utiliser à tort des fonctions ayant un résultat de type Suite.

CONST Nmax = 1000;
TYPE Suite = RECORD
               LONG : INTEGER;
               TAB : ARRAY[1..Nmax] OF INTEGER;
             END;
FUNCTION D1(s : Suite) : Suite;
VAR indice : INTEGER;

BEGIN
  D1.LONG := s.LONG + 1;
  FOR indice := 1 TO s.LONG DO
    D1.TAB[indice] := s.TAB[indice];
  D1.TAB[D1.LONG] := 1;
END;
FUNCTION D2(s : Suite) : Suite;
VAR indice : INTEGER;
BEGIN
  D1.LONG := s.LONG;
  FOR indice := 1 TO s.LONG-1 DO
    D1.TAB[indice] := s.TAB[indice];
  D1.TAB[D1.LONG] := s.TAB[s.LONG] + 1;
END;

10 Énumération des décompositions de n

On va utiliser les fonctions D1 et D2. Attention : ENUM ne sonne pas de résultat, c’est donc une procédure...

L’analyse de l’énoncé nous permet de comprendre que la procédure ENUM doit afficher tous les k −1-ièmes descendants de la suite s. Pour ceci remarquons qu’appelée avec les paramètres (1) et 1, elle affiche (1).

PROCEDURE ENUM(s : Suite; k : INTEGER);
VAR indice : INTEGER;
BEGIN
  IF k = 1 THEN
  { Affichage de s }
  BEGIN
    FOR indice := 1 TO s.LONG-1 DO Write(s.TAB[indice],' ');
    WriteLn(s.TAB[s.LONG]);
  END
  { Appel récursif }
  ELSE
    ENUM(D1(s),k-1);
    ENUM(D2(s),k-1);
  END;
END;