Exercices

1. Écrire la fonction qui à un entier associe son carré.

2. Écrire la fonction puissance.

3. En utilisant puissance, écrire la fonction exponentielle binaire (n \mapsto 2^n)

4. Écrire la fonction factorielle.

5. Écrire la fonction sommielle.

6. Écrire une fonction qui calcule le n-ième terme de la suite de Fibonacci.

   1. La tester sur l’entrée 30 (on devrait trouver 832040)
   2. La tester sur les valeurs suivantes. Mesurer le temps utilisé.
   3. Réfléchir à une version plus efficace.

7. Écrire des fonctions pair et impair qui testent si un nombre est pair ou impair.

8. Écrire une fonction combinaison qui calcule les combinaisons de k éléments parmi n en utilisant une identité connue du triangle de Pascal.

9. Écrire la fonction de Ackermann.

   \left\{ \begin{array}{l} A(0, n) = n+1\\ A(m, 0) = A(m-1, 1)\\ A(m,n) = A(m-1, A(m, n-1))\end{array}\right.