Philippe.Dumas@inria.fr


http://algo.inria.fr/dumas/Maple/

Retour en page principale Table des matières Index

Maple V.4 worksheet Maple V.5 worksheet

Nous reprenons la procédure fournie.

> denumerants:=proc(n::nonnegint)

    local n2,n5,n10,n20,nb,p,q,r;

    nb:=0;

    for n20 from 0 to iquo(n,20) do

      p:=n-20*n20;

      for n10 from 0 to iquo(p,10) do

        q:=p-10*n10;

        for n5 from 0 to iquo(q,5) do

          nb:=nb+iquo(q-5*n5,2)+1

        od

      od

    od;

    nb

  end:

> st:=time():

  denumerants(1000);

  time()-st;

Une légère modification (# 0) suffit pour obtenir le résultat demandé. On peut au choix (#1) renvoyer le dénumérants ou NULL.

> denumerantsview:=proc(n::nonnegint)

    local n2,n5,n10,n20,nb,p,q,r;

    nb:=0;

    for n20 from 0 to iquo(n,20) do

      p:=n-20*n20;

      for n10 from 0 to iquo(p,10) do

        q:=p-10*n10;

        for n5 from 0 to iquo(q,5) do

          r:=iquo(q-5*n5,2);                                 # 0

          for n2 from 0 to r do                              # 0

            nb:=nb+1;                             # 1        # 0

            print(n-(2*n2+5*n5+10*n10+20*n20),n2,n5,n10,n20) # 0

          od                                                 # 0

        od

      od

    od;

    nb                                            # 1

  # NULL                                          # 1

  end:

> denumerantsview(11);

Ces deux procédures ne sont guère satisfaisantes car une simple modification de la liste des sommants permis oblige à les récrire complètement. De plus le style est désagréable puisque le niveau d'imbrication des boucles dépend de la donnée. Il est plus agréable de disposer d'une procédure qui prend en argument la liste des sommants autorisés. Notons qu'un même sommant pourrait apparaître plusieurs fois ; on peut alors considérer que les sommants sont pourvus d'une couleur, ce qui permet de distinguer deux sommants de même valeur. Voici d'abord une version récursive assez naturelle. On soustrait le dernier sommant zéro fois, une fois, deux fois, autant que faire se peut et on cherche une décomposition de ce qui reste à l'aide des autres sommants. Le cas où il n'y a qu'un sommant est traité à part. L'emploi de l'option remember est indispensable pour que la procédure soit efficace. Cette version est essentiellement la procédure proposée à la page 110. Bien sûr en Maple V.3, nous employons convert/+ au lieu de add.

> denum:=proc(n::nonnegint,S::list(nonnegint))

    local nu,q,r,ls,head,i,c;

    option remember;

    nu:=nops(S);

    if nu=0 then 0

    elif nu=1 then 

      q:=iquo(n,S[1],r);

      if r=0 then 1

      else 0

      fi

    else

      ls:=S[nu];

      head:=[seq(S[i],i=1..nu-1)];

      add(denum(n-c*ls,head),c=0..iquo(n,ls))

    fi

  end:

    

> denum(10,[10,5,1,2]);

> st:=time():

  denum(1000,[1,2,5,10,20]);

  time()-st;

Voici maintenant une version itérative qui est vue comme un parcours d'arbre. La racine de l'arbre est au niveau 0 et elle est étiquetée par l'entier à décomposer. Le passage du niveau i au niveau i+1 concerne le sommant numéro i de la liste des sommants permis. Si l'arête qui fait passer du noeud étiqueté par l'entier nu au noeud étiqueté par l'entier nu' porte l'étiquette c, alors la relation nu=c+nu' est satisfaite. Nous recherchons les noeuds étiquetés par 0. Ici encore les sommants permis ne sont pas nécessairement distincts et ils ne sont pas forcément rangés dans l'ordre croissant.

L'instruction mise en commentaire (# 0) permet de voir le parcours effectué sur un exemple. Nous partons de la racine de l'arbre. Si nous sommes dans le sens de la descente (flag=down) et que le noeud est étiqueté par 0, alors nous avons trouvé une décomposition de l'entier et nous l'écrivons (# 1). Si nous ne sommes pas à la profondeur maximale, alors nous continuons à descendre (# 2) ; ainsi nous commençons par décrire la branche la plus à gauche de l'arbre et la descente est privilégiée. Il s'agit d'un parcours en profondeur d'abord. Ensuite nous nous déplaçons vers la droite (# 3) dans la mesure où cela est possible (# 31). Si cela n'est pas possible, nous remontons (# 32) d'un cran. Enfin si nous sommes revenus au niveau 0, il est temps de sortir de la boucle (# 4).

> denum1:=proc(n::nonnegint,S::list(nonnegint))

    local depth,level,nn,flag,up,down,i,c;

    depth:=nops(S);

    if depth=0 then RETURN(NULL) fi;

    level:=0:

    nn:=n;

    flag:=down;

    do

      if flag=down and nn=0 then                        # 1

        print(seq(c[i],i=1..depth));

        flag:=up 

      fi;

      if level<depth and flag=down then                 # 2

          level:=level+1;

          c[level]:=0

      elif level>0 then                                 # 3

        if nn>=S[level] then                            # 31

          flag:=down;

          c[level]:=c[level]+1;

          nn:=nn-S[level];

        else                                            # 32

          flag:=up;

          nn:=nn+c[level]*S[level];

          c[level]:=0;

          level:=level-1;

        fi

      else                                              # 4

        break

      fi;

  # print([seq(c[i],i=1..level)],nn,flag)               # 0

    od;

    NULL

  end:

> denum1(10,[2,5,1]);

Nous voyons apparaître les dix décompositions de l'entier 10 en les sommants 2, 5 et 1.

Pour ce qui concerne les dénumérants on peut consulter le livre de Louis Comtet [Comtet70, tome premier, chap. II, sect. 6, page 119 et suivantes].

Retour en page principale