Licence Informatique
Algorithmique Avancée
TD 3: 11-12/10/05

    1. Combien de multiplications sont utilisées par l'algorithme donné en cours pour calculer xn quand n=32? Peut-on calculer x32 avec moins de multiplications?
    2. Mêmes questions pour n=30.
    (La version en exalgo:)
    fonction puissance(val x:reel; val i: entier): reel;
    var p:reel;
    debut
    si i=0 alors retourne 1
    sinon
    p:=puissance(x,i/2);
    si i%2=0 alors retourne p*p
    sinon retourne p*p*x
    finsi
    finsi
    fin
    finfonction;

  1. Ecrire une fonction récursive pgcd(m,n) qui calcule le plus grand diviseur commun des deux entiers (non-négatifs) m et n.
  2. Une procédure P(n,T) a pour paramètre un entier et un tableau unidimensionnel et n'utilise que les éléments T[1],...,T[n]. Je veux appeler P(n,T) une fois avec chaque combinaison possible de valeurs des éléments T[1],...,T[n] avec les contraintes que T[i] prend une valeur entre 1 et B[i] (1 £ i £ n) et la somme de tous les T[i] est au maximum K. Il est à noter que n est une variable.

    1. Ecrire une procédure récursive en exalgo qui effectue tous ces appels.
    2. Et une procédure non-récursive.



File translated from TEX by TTH, version 3.05.
On 10 Oct 2005, 17:43.