Licence Info
Algorithmique Avancée
TD 3: 17-18/2/04

    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.
  1. 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) plusieurs fois avec toutes les valeurs possibles des éléments T[1],...,T[n] avec la contrainte que T[i] prend une valeur entre 1 et B[i] (1 <= i <= n) Il est à noter que n est une variable.

    1. Combien de fois devrai-je appeler P(n,T)?
    2. Ecrire une procédure récursive en exalgo qui effectue tous ces appels.
    3. Et une procédure non-récursive.
  2. Il faut calculer la somme des valeurs de tous les noeuds d'un arbre binaire.

    1. Ecrire une procédure récursive qui calcule la somme par un parcours de l'arbre avec incrémentation d'une variable globale à chaque noeud.
    2. Et une fonction qui n'utilise pas de variables globales.



File translated from TEX by TTH, version 3.05.
On 12 Feb 2004, 12:14.