Licence Informatique Algorithmique Avancée TD 3: Octobre 2006

1. (a) Combien de multiplications sont utilisées par l’algorithme donné en cours pour calculer x^{n} quand n = 32? Peut-on calculer x^{32} avec moins de multiplications?

(b) 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=1 alors retourne x
   sinon
      p:=puissance(x,i/2);
      si i%2=0 alors retourne p*p
      sinon retourne p*p*x
      finsi
   finsi
fin
finfonction;

2. Ecrire une fonction récursive pgcd(m,n) qui calcule le plus grand diviseur commun des deux entiers (non-négatifs) m et n.

3. 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.

(a) Ecrire une procédure récursive en exalgo qui effectue tous ces appels.

(b) Et une procédure non-récursive.

4. (Question supplémentaire) Un dédale est représenté par un tableau à deux dimensions dont les éléments sont 0 (libre) ou -1 (bloqué) ou +1 (porte). Ecrire une fonction booléenne qui décide s’il existe un chemin d’une case donnée (i,j) à une porte.

Un chemin est composé de pas dans les quatres directions N, S, E et O; vous pouvez supposer que tout le perimètre du dédale est bloqué sauf les portes.