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

Comme nous l'avons déjà indiqué à l'exercice précédent, la procédure denumerants n'est guère satisfaisante et nous préférons travailler sur la procédure denum fournie dans la correction de cet exercice.

> 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(1000,[50,100,200,500]);

Pour borner le nombre d'occurrences de chaque sommant, nous ajoutons un paramètre et nous modifions légèment le code (lignes marquées d'un dièse).

> denum2:=proc(n::nonnegint,S::list(nonnegint),b::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 and q<=b then 1                            #

      else 0

      fi

    else

      ls:=S[nu];

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

      add(denum2(n-c*ls,head,b),c=0..min(b,iquo(n,ls))) #

    fi

  end:

> denum2(1000,[50,100,200,500],3);

Nous aimerions tester cette réponse. Nous reprenons donc la procédure denum1 de l'exercice 1 et nous la changeons pour qu'elle renvoie les décompositions qui satisfont le critère sur le nombre d'occurrences de chaque sommant. On notera que nous ne construisons pas la liste des décompositions possibles par des juxtapositions répétées mais en passant par l'intermédiaire d'une table T, ceci dans un souci d'efficacité. Il s'agit ici d'une question de style car la réponse est de taille faible, mais dans d'autres problèmes la différence d'occupation en mémoire peut être sensible. En effet la création d'une séquence de longueur l par des juxtapositions répétées produit d'abord un objet de taille 1, puis un objet de taille 2, etc, et enfin un objet de taille l. Au total, on peut ainsi prendre une place en mémoire qui est de l'ordre de l^2/2, alors que l'on ne cherche à construire qu'un objet de taille l.

> denum3:=proc(n::nonnegint,S::list(nonnegint),b::nonnegint)

    local depth,level,nn,flag,up,down,i,c,cpt,T;                 #

    depth:=nops(S);

    if depth=0 then RETURN(NULL) fi;

    level:=0:

    nn:=n;

    flag:=down;

    cpt:=0;                                                       #

    do

      if flag=down and nn=0 and max(seq(c[i],i=1..depth))<=b then #

        cpt:=cpt+1;                                               #

        T[cpt]:=[seq(c[i],i=1..depth)];                           #

        flag:=up 

      fi;

      if level<depth and flag=down then

          level:=level+1;

          c[level]:=0

      elif level>0 then

        if nn>=S[level] then

          flag:=down;

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

          nn:=nn-S[level];

        else 

          flag:=up;

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

          c[level]:=0;

          level:=level-1;

        fi

      else

        break

      fi;

    od;

    [seq(T[i],i=1..cpt)]

  end:

> denum3(1000,[50,100,200,500],3);

Nous laissons au lecteur le traitement d'une question connexe : écrire toutes les décompositions d'un entier donné dont le nombre total de sommants est borné par un entier donné. Par exemple si nous bornons le nombre de sommants par 3, il ne reste plus que la première décomposition parmi les six précédentes, car les nombres de sommants sont respectivement 2, 4, 5, 5, 6, 8.

Retour en page principale