Somme des n premiers entiers

1. Ecrire une fonction itérative sommeI(n:int)->int (cette écriture signifie que le paramètre n est un entier et que la fonction renvoie un entier) renvoyant \(\displaystyle\sum_{i=0}^{n} i \).
2. Tester avec n = 200 (le résultat peut facilement être vérifié de tête).
3. On pose \(S_n = \displaystyle\sum_{i=0}^{n} i \). Ecrire la relation de récurrence entre \(S_n\) et \(S_{n-1}\).
4. En déduire une fonction récursive sommeR(n:int)->int renvoyant \(\displaystyle\sum_{i=0}^{n} i \).
5. Tester avec n = 200.
6. Tester avec n = 2000 ; pour quelle raison obtient-on un message d'erreur ?

L'écriture def f(paramètre:type)->type s'appelle une annotation, elle permet de préciser le type des paramètres et le type de la grandeur renvoyée afin de faciliter la compréhension deu code (sans effet sur l'exécution : aucune vérification n'est effectuée).

Présence d'un élément dans une liste

Rappels - Slicing : L[i:] renvoie la sous-liste composée des éléments de L à partir de l'index i ; L[-1] renvoie le dernier élément de L.
En déduire ce que renvoie L[:-1] puis vérifier sur un exemple.

1. Ecrire une fonction itérative presentI(L:list,e)->bool renvoyant un booléen (True ou False) suivant que l'élément e est présent ou non dans la liste L.
2. Effectuer au moins deux tests (élement présent / élément absent).
3. Quelle relation de récurrence peut-on imaginer ?
4. En déduire une fonction récursive presentR(L:list,e)->bool effectuant le même travail. Plusieurs solutions sont envisageables suivant que l'élément enlevé de la liste est le premier ou le dernier.
5. Tester la fonction.

Fonction mystere

Tester les commandes suivantes : False + 5 ; True + 5. Conclusion ?

Que fait la fonction suivante ? Expliquer son fonctionnement.

Remarque les parenthèses autour de L[0]==e sont indispensables pour forcer l'évaluation. On pourrait aussi écrire int((L[0]==e)).

pgcd par la méthode d’Euclide

Algorithme : pgcd(a, 0) = a et pgcd(a, b) = pgcd(b, a%b)
« Pour calculer le pgcd de a et de b, on remplace a par b et b par a%b tant que b n'est pas nul »
Rq : au cours de cet algorithme a et b sont modfiés.

Rappel : a%b est le reste dans la division Euclidienne de a par b.

1. Ecrire une fonction itérative pgcdI(a,b:int)->int.
2. Effectuer des tests.
3. Déduire de la relation de récurrence ci-dessus une fonction récursive pgcdR(a,b:int)->int.
4. Tester la fonction.

Récursivité - Ordre de l'évaluation des appels

Rappel : 'a'*4 renvoie aaaa.

Ecrire une fonction récursive f(n) renvoyant, avec n = 5 :
*****
****
***
**
*

Ecrire une fonction récursive g(n) renvoyant, avec n = 5 :
*
**
***
****
*****

Factorielle

1. Ecrire une fonction itérative factorielleI(n:int)->int renvoyant \(n !\).
2. Tester avec n = 10 (vérifier le résultat avec l'une des fonctions de python, numpy et scipy : math.factorial, numpy.math.factorial et scipy.math.factorial).
3. Ecrire la relation de récurrence entre \(n!\) et \((n-1) !\).
4. En déduire une fonction récursive factorielleR(n:int)->int.
5. Tester avec n = 10.

Exponentiation rapide (calcul de xⁿ)

Rappel : \(\left\lfloor a \right\rfloor\) désigne la partie entière de a. En python, \(\left\lfloor \frac{a}{2} \right\rfloor\) est obtenu par a//2.
Pour tester la parité d'un entier n, il suffit de calculer le reste dans la division Euclidienne de n par 2 : n % 2 en python.

1. Ecrire une fonction itérative puissanceI(x:float,n:int)->float renvoyant \(x^n\) sans utiliser l'opérateur ** ou une fonction python prédéfinie.
2. Tester la fonction.
3. Ecrire la relation de récurrence entre \(x^n\) et \(x^{n-1}\).
4. En déduire une fonction récursive puissanceR(x:float,n:int)->float.
5. Tester.
6. L'algorithme d'exponentiation rapide est le suivant :
   - si n est pair \(x^n = x^{\left\lfloor \frac{n}{2} \right\rfloor} \times x^{\left\lfloor \frac{n}{2} \right\rfloor}\) ;
   - si n est impair \(x^n = x^{\left\lfloor \frac{n}{2} \right\rfloor} \times x^{\left\lfloor \frac{n}{2} \right\rfloor} \times x\).
   Illustrer l’intérêt de cette méthode, en déroulant l’algorithme « à la main » et en comptant le nombre de multiplications à effectuer pour calculer x³⁷ avec cette méthode et comparer avec la fonction itérative puissanceI.
7. Ecrire une fonction récursive puissance2(x:float,n:int)->float en utilisant l'algorithme d'exponentiation rapide.
8. Tester la fonction.
9. En utilisant l’écriture de n en base 2 : \((n)_{10} = \displaystyle\sum\limits_{i = 0}^p {a_i 2^i} \) (où a_i est égal à 0 ou 1), montrer que la complexité de cette fonction est en \(O(log(n))\).

Suite de Fibonacci

Rappels - Matrices

La suite de Fibonacci est définie par : \(\left\{ \begin{array}{l}{F_0} = 1\\{F_1} = 1\\{F_n} = {F_{n - 1}} + {F_{n - 2}}\,\,\,\,\,n \ge 2\end{array} \right.\).

1. Ecrire une fonction itérative fibonacciI(n:int)->int.
2. Tester la fonction.
3. Déduire de la relation de récurrence ci-dessus une fonction récursive fibonacciR(n:int)->int.
4. Tester.
5. Expliquer pour quelle raison cette fonction est terriblement inefficace (en temps de calcul).
6. La relation de récurrence ci-dessus peut s’écrire sous forme matricielle : \(\left[ \begin{array}{l}{F_n}\\{F_{n - 1}}\end{array} \right] = \left[ {\begin{array}{*{20}{c}}1&1\\1&0\end{array}} \right]\left[ \begin{array}{l}{F_{n - 1}}\\{F_{n - 2}}\end{array} \right]\)
   En déduire une relation entre \(\left[ \begin{array}{l}{F_n}\\{F_{n - 1}}\end{array} \right] \) et \(\left[ \begin{array}{l}{F_1}\\{F_0}\end{array} \right]\).
7. Écrire une fonction puissanceM(M,n) (de complexité optimum) qui renvoie \(M^n\) où M> est une matrice carrée et n> un entier.
8. En déduire une fonction fibonacciM(n:int)->int plus efficace.
9. Tester la fonction.