def bissextiles(annee : int) -> bool :
"""
Entrées : un nombre entier positif représentant une année
Sortie : Vrai ou Faux selon qui l'année est bissextile
"""
bissextile = False
if annee % 4 == 0 and annee % 100 != 0 or annee % 400 == 0 :
bissextile = True
return bissextile
bissextiles(0), bissextiles(2022), bissextiles(1992), bissextiles(2000), bissextiles(2100)
(True, False, True, True, False)
def bissextiles(annee : int) -> bool :
"""
Entrées : un nombre entier positif représentant une année
Sortie : Vrai ou Faux selon qui l'année est bissextile
"""
return annee % 4 == 0 and annee % 100 != 0 or annee % 400 == 0
bissextiles(0), bissextiles(2022), bissextiles(1992), bissextiles(2000), bissextiles(2100)
(True, False, True, True, False)
def u(q : float, u_0 : float, n : int) -> float :
"""
Entrées : q la raison de u, u_0 le premier terme de u et n un entier positif
Sortie : u_n
"""
rang = 0
u = u_0
while rang != n :
u = q * u
rang = rang + 1
return u
def su(q : float, u_0 : float, n : int) -> float :
"""
Entrées : q la raison de u, u_0 le premier terme de u et n un entier positif
Sortie : u_n
"""
rang = 0
u = u_0
s = u_0
while rang < n :
u = q * u
s = s + u
rang = rang + 1
return s
Plusieurs visions sont possible.
Solution 1: Partir de $0$ et essayer tous les entiers $l$ jusqu'à trouver le premier tel que $b^l > n$.
Solution 2: Transformer l'inégalité comme ceci
$$ 1 \leq \frac n {b^l} < b $$et diviser $n$ jusqu'à obtenir un nombre entre 1 et b. $l$ est le nombre de division effectuée
def log_b(n : int, b : int) -> int :
"""
Entrées :
- ( n : entier ) un nombre entier
- ( b : entier ) la base du logarithme à utiliser
Sortie : le logarithme entier en base b de n
"""
l = 0
while not (1 <= n < b) :
n = n // b
l = l + 1
return l
Pour le calcul des suites récurrente d'ordre 1 la technique consiste à associer à une variable, $u$, la valeur courrante de la suite, utiliser cette valeur pour calculer le rang suivant et mettre à jour la variable $u$.
def halley(n : int) -> float :
"""
Entrées : n le rang de la suite H à calculer
Sortie : Hn
"""
# Rang 0
h = 1
rang = 0
# Calcul du rang n en calculant chaque rang i successivement
while rang != n :
h = h * (h * h + 6) / ( 3 * h * h + 2)
rang = rang + 1
return h
Ici la suite est récurrente d'ordre 2, il nous faut donc deux variable, $u$ et $v$ pour conserver les deux termes précédents lors du calcul du terme suivant.
def fibonacci(n : int) -> int :
"""
Entrées : n le rang de la suite F à calculer
Sortie : Fn
"""
f = 0
if n > 0 : # Si n = 0, il n'y a aucun calcul à faire
# Rang 1
f = 1
f_prev = 0
rang = 1
# Calcul du rang n en calculant chaque rang i successivement
while rang != n :
f_suivant = f + f_prev
f_prev = f
f = f_suivant
rang = rang + 1
return f
Pour verifier si un nombre est parfait, on réalise la somme de ses diviseurs stricts.
On va parcourir tous les diviseurs stricts potentiels et accumuler leur somme dans une variable intermédiaire.
Une fois tous les diviseurs testés et accumulés dans une variable, on testera l'égalité de cette variable avec l'entrée.
def parfait(n : int) -> int :
"""
Entrées : n un entier positif
Sortie : un booléen. Vrai ssi n est parfait
"""
est_parfait = False # Cas n = 0 et n = 1
if n > 1 : # Cas n > 1
somme_diviseurs = 1 # 1 est diviseur de n, on l'ajoute directement à la somme
diviseur = 2
while diviseur < n :
if n % diviseur == 0 :
somme_diviseurs = somme_diviseurs + diviseur
diviseur = diviseur + 1
if somme_diviseurs == n :
est_parfait = True
return est_parfait
On peut diminuer le nombre de diviseurs potentiels à vérifier en remarquant que si d
divise n
alors n // d
divise n
et que les diviseurs vont donc par pairs avec un diviseur plus petit que $\sqrt n$ et un autre strictement plus grand. Il faut exclure les cas de $1$ allant de pair avec $n$ et de $\sqrt n$ si il est entier qui va de pair avec lui même et ne doit pas être ajouté deux fois.
def parfait_opt(n : int) -> int :
"""
Entrées : n un entier positif
Sortie : un booléen. Vrai ssi n est parfait
"""
est_parfait = False # Cas n = 0 et n = 1
if n > 1 : # Cas n > 1
somme_diviseurs = 1 # 1 est diviseur de n, on l'ajoute directement à la somme
diviseur = 2
while diviseur * diviseur < n :
if n % diviseur == 0 :
somme_diviseurs = somme_diviseurs + diviseur + ( n // diviseur)
diviseur = diviseur + 1
# À la sortie, diviseur^2 >= n. On traite le cas où n est un carré parfait.
if diviseur * diviseur == n :
somme_diviseurs = somme_diviseurs + diviseur
if somme_diviseurs == n :
est_parfait = True
return est_parfait
Teaser : ... Une fois le langage et les structures de données maitrisées on peut écrire cette fonction en une ligne ...
def parfait_pour_se_la_peter(n : int) -> int :
return n > 1 and sum(d for d in range(1,n) if n % d == 0) == n
def syracuse(s0 : int) -> int :
"""
Entrées : s0 > 0 terme initial de la suite
Sortie : un entier n. Le premier range tel que la Sn = 1
"""
# Rang 0
s = s0
rang = 0
# Calcul du rang suivant dans s, jusqu'à ce que s == 1
while s != 1 :
rang = rang + 1
if s % 2 == 0 :
s = s // 2
else :
s = 3 * s + 1
# Arrivé ici, s == 1. On renvoie le rang.
return rang
Just for fun : Evolution du nombre d'itération avec l'entrée
def adjacentes(epsilon : float) -> int :
"""
Entrées : epsilon un nombre réel
Sortie : le rang n, entier, à partir du quel |a_n - b_n| < epsilon
"""
a = 1
b = 2
n = 0
while not (-epsilon < a - b < epsilon) :
a = 2 / b
b = (a + b) / 2
n = n + 1
return n
def premier(n : int) -> bool :
"""
Entrées : n un entier >= 2
Sortie : Vrai ou Faux selon si n est premier
"""
diviseur = 2
while diviseur * diviseur <= n :
if n % diviseur == 0 :
return False
return True
def chanceux_euler(n : int) -> bool :
"""
Entrées : n > 1 un entier
Sortie : un booléen, vrai si n est chanceux
"""
chanceux = True
nombre = 0
while nombre <= n - 2 :
if not premier(nombre * nombre + nombre + n) :
chanceux = False
nombre = nombre + 1
return chanceux
Cette fonction fait parti d'un groupe de fonction qui ont peu d'intérêt en soit, mais qui sont utilisées pour tester la performance des compilateurs.
La fonction est naturellement recursive... Mais on ne sait pas encore ce que ça veut dire...
Pour la coder de manière itérative, il faut se tordre un peu l'esprit...
On peut voir la fonction sous cet angle : $$ \forall k \in \mathbb{N^*}, f^k(n) = \begin{cases} f^{k-1}(n-10) & {\rm {\ si\ }} n>100 \\ f^{k+2}(n+11) & {\rm {\ sinon.}} \end{cases} $$
Gardons un compteur profondeur
qui compte le nombre de fois que la fonction doit être appliquée sur n.
Initialement le compteur vaut $1$.
On applique la fonction tant que le compteur n'est pas nul, par definition.
def mccarthy91(n : int) -> int :
profondeur = 1
entrée = n
while profondeur != 0 :
if entrée > 100 :
entrée = entrée - 10
profondeur = profondeur - 1
else :
entrée = entrée + 11
profondeur = profondeur + 1
return entrée