Lundi 14 février 2022
Un palidrome est un mot, ou une phrase, qui se lit indentiquement dans les deux sens. Par exemple, les mots "radar", "kayak" ou "naan" sont des palindromes.
Question 1 : Écrire une fonction est_palindrome(mot) qui teste si la chaîne de caractère mot est (ou non) un palindrome. Pour cela, on pourra utiliser le mot-clef all.
Question 2 : Écrire une version récursive est_palindrome_rec(mot) de la fonction précédente.
L'algorithme d'Euclide permet de calculer le plus grand commun diviseur (pgcd) de deux entiers $a$ et $b$.
Question 1 : Implanter une fonction pgcd(a, b) qui calcule le pgcd de deux entiers a et b grâce à l'algorithme d'Euclide.
Vérifiez la validité de votre fonction en comparant le résultat avec la fonction gcd de SageMath (décommentez le code suivant).
On rappelle que pour utiliser des fonctions spécifiques de SageMath, il faut que ce logiciel soit bien lancé (vérifiez que, sur la barre de menu en haut à droite, SageMath est bien indiqué, en non Python3). Si ce n'est pas le cas, allez dans le menu Noyau (Kernel en anglais), puis changez de noyau en SageMath.
# a, b = randint(2, 1000), randint(2, 1000)
# print(pgcd(a, b) == gcd(a, b))
Question 2 : Implanter une fonction récursive pgcd_rec(a, b) qui calcule de manière récursive le pgcd de deux entiers a et b.
Vérifiez la validité de votre fonction en comparant le résultat avec la fonction gcd de SageMath.
# a, b = randint(2, 1000), randint(2, 1000)
# print(pgcd_rec(a, b) == gcd(a, b))
Question 3 : Implanter une fonction bezout(a, b) qui calcule les coefficients de Bezout de deux entiers a et b. On rappelle que ce sont les entiers $u$ et $v$ tels que $ua +vb = \mathrm{pgcd}(a, b)$, et qu'on peut les obtenir grâce à l'algorithme d'Euclide étendu.
Validez votre fonction en la comparant à la fonction xgcd de SageMath. Attention, la fonction xgcd retourne trois valeurs : le pgcd suivi des deux coefficients de Bezout.
# a, b = randint(2, 1000), randint(2, 1000)
# coeffs = bezout(a, b)
# coeffs_sage = xgcd(a, b)
# print(coeffs_sage)
# print(coeffs == coeffs[1:])
Question 4 : Écrire une fonction ppcm(a, b) qui calcule le ppcm de deux entiers $a$ et $b$.
Validez votre fonction en la comparant avec la fonction lcm de SageMath.
# a, b = randint(2, 1000), randint(2, 1000)
# print(ppcm(a, b) == lcm(a, b))
Question 1 : Écrire une fonction diviseurs(n) qui retourne la liste des diviseurs de n.
Question 2 : En déduire une fonction est_premier(n) qui teste si un entier naturel non-nul n est premier.
Question 3 : Écrire une fonction est_parfait(n) qui teste si un entier naturel non-nul n est parfait. On pourra utiliser la fonction sum() de python.
Question 4 (plus difficile) : Écrire une fonction factorise(n) qui retourne la factorisation d'un entier sous la forme d'une liste de listes L, telle que si $n = p_0^{e_0} p_1^{e_1} \dots p_k^{e_k}$, alors L[i] = [pi, ei].
Par exemple, pour $n = 84 = 2^2 \times 3 \times 7$, la fonction doit retourner la liste
L = [ [2, 2], [3, 1], [7, 1] ]
Question 1 : Écrire une fonction decomposition(n) qui calcule la décomposition en base $2$ d'un entier n. La fonction retournera la liste $[n_0, n_1, \dots, n_k]$ telle que $n = \sum_{i=0}^k n_i 2^k$. Si $n = 0$, la fonction retournera $[0]$.
Question 2 : Écrire une version récursive de la fonction précédente, qu'on appellera decomposition_rec(n).