Philippe.Dumas@inria.fr


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

Retour en page principale Table des matières Index

Maple V.4 worksheet, bis Maple V.5 worksheet, bis

1 | 2

Nous commençons par définir une procédure qui réalise l'itération. Notez la dernière instruction qui crée une table de remember, ne comportant d'ailleurs que l'unique entrée 1.

> syracuse:=proc(u::posint)

    if (u mod 2)=0 then iquo(u,2)

    else 3*u+1

    fi

  end:

  syracuse(1):=1:

1. Il suffit maintenant d'itérer la procédure syracuse en comptant le nombre d'appels.

> stoppingtime:=proc(n::posint)

    local u,counter;

    u:=n;

    for counter from 0 while u<>1 do  

      u:=syracuse(u)

    od;

    counter

  end:

> stoppingtime(10);

Pour mieux comprendre ce qui se passe, on peut regarder de plus près l'exécution des calculs.

> trace(syracuse):

  stoppingtime(10);

{--> enter syracuse, args = 10

<-- exit syracuse (now in stoppingtime) = 5}

{--> enter syracuse, args = 5

<-- exit syracuse (now in stoppingtime) = 16}

{--> enter syracuse, args = 16

<-- exit syracuse (now in stoppingtime) = 8}

{--> enter syracuse, args = 8

<-- exit syracuse (now in stoppingtime) = 4}

{--> enter syracuse, args = 4

<-- exit syracuse (now in stoppingtime) = 2}

{--> enter syracuse, args = 2

<-- exit syracuse (now in stoppingtime) = 1}

> untrace(syracuse):

2. Pour traiter un ensemble, nous procédons essentiellement de la même manière.

> setstoppingtime:=proc(N::set(posint))

    local U,counter;

    U:=N;

    for counter from 0 while U<>{1} do  

      U:=map(syracuse,U)

    od;

    counter

  end:

> setstoppingtime({10});

> setstoppingtime({10,11,12});

> seq(stoppingtime(i),i=[10,11,12]);

> trace(setstoppingtime):

  setstoppingtime({10,11,12});

{--> enter setstoppingtime, args = {10, 11, 12}

<-- exit setstoppingtime (now at top level) = 14}

> untrace(setstoppingtime):

Pour une raison obscure, il était demandé de ne pas remployer la procédure de la première question. Voici donc une procédure qui satisfait cette spécification. On notera l'emploi de la table next qui permet de stocker les résultats intermédiaires.

> superstoppingtime:=proc(U::set(posint))

    local V,next,item,i;

    V:=U;

    for i while V<>{1} do

      for item in V do

        if item=1 then next[item]:=1

        elif irem(item,2)=0 then next[item]:=iquo(item,2)

        else next[item]:=3*item+1

        fi

      od;

    V:={seq(next[item],item=V)}

    od;

    i-1

  end:

> superstoppingtime({10,11,12});

Retour en page principale