Quelques exercices

Amusettes

Sommation

Exercice 14   Écrire une fonction qui, étant donné un entier $n$, renvoie $\sum_{i=1}^n \sum_{j=1}^i i+j$. Voir réponse 14.

Traduisez votre algorithme en langage C. Voir réponse 14.

Fibonacci

Exercice 15   Écrire une fonction qui calcule itérativement le $n$-ème nombre de Fibonnacci défini par $F_0=F_1=1$ et $F_n=F_{n-1}+F_{n-2}$ pour $n\leqslant 2$. Voir réponse 15.

Traduisez votre algorithme en langage C. Voir réponse 15.

Quelle est la complexité en temps et en espace de votre algorithme ?

Exercice 16   Écrire une fonction qui calcule itérativement le $n$-ème nombre de Fibonnacci mais avec une complexité en espace plus faible que la version précédente. Voir réponse 16.

Traduisez votre algorithme en langage C. Voir réponse 16.

Exercice 17   Écrire une fonction qui calcule récursivement le $n$-ème nombre de Fibonnacci. Voir réponse 17.

Traduisez votre algorithme en langage C. Voir réponse 17.

Catalan

Écrire une fonction qui calcule le $n$-ème nombre de Catalan, qui vaut $1$, si $n=1$ et $c_n=\sum_{k=1}^{n-1} c_k c_{n-k}$ sinon.