Fractions Egyptiennes
I. Les fractions égyptiennes¶
Dans l'ancienne Egypte, les fractions étaient écrites d'une façon très particulière, comme une somme de fractions de l'unité. On rappelle qu'une "fraction" est un nombre inférieur à 1, comme le suggère le mot "fraction" en français.
Par exemple: \(\frac{6}{7}\) était écrit : \(\frac{1}{2}+\frac{1}{3}+\frac{1}{42}\)
Il n'est pas évident à première vue que l'on puisse écrire n'importe quelle fraction de cette façon, mais cela fut démontré par Leonardo de Pise (plus connu comme Leonardo de Fibonacci) en 1202.
Pour le montrer, Leonardo de Pise utilisa un algorithme qu'il nomma the greedy algorithm (algorithme glouton)
C'est sans doute la plus anciennne référence à un algorithme glouton, avec cette dénomination.
👉 Remarquons que nous appelerons "fraction unitaire" une fraction de l'unité, donc un fraction dont le numérateur est égal à 1.
\(\dfrac{1}{2},\dfrac{1}{3},\dfrac{1}{4}\) sont des fractions unitaires.
II. Sentir l'algorithme¶
Nous allons essayer d'écrire notre fraction comme une somme de fractions unitaires parmi les fractions suivantes : \(\dfrac{1}{2},\dfrac{1}{3},\dfrac{1}{4},\dfrac{1}{5},\dfrac{1}{6},\dfrac{1}{7}\) etc ...
Nous avons bien évidemment \(\dfrac{1}{2}>\dfrac{1}{3}>\dfrac{1}{4}>\dfrac{1}{5}>\dfrac{1}{6}>\dfrac{1}{7}\) etc ...
Premier exemple :¶
Nous allons ici montrer comment on trouve que \(\dfrac{6}{7}=\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{42}\).
L'idée de cet algorithme glouton, et d'utiliser toujours en premier les fractions les plus grandes possibles.
Regardons la première fraction unitaire possible : \(\dfrac{1}{2}\)
Nous pouvons donc écrire que \(\dfrac{5}{14}=\dfrac{1}{3}+\text{reste}\).
Nous allons utiliser le même procédé pour calculer ce nouveau reste :
\(\text{reste}=\dfrac{5}{14}-\dfrac{1}{3}=\dfrac{15-14}{42}=\dfrac{1}{42}\)
Nous avons donc \(\dfrac{5}{14}=\dfrac{1}{3}+\dfrac{1}{42}\)
Nous avons beaucoup de chance car \(\dfrac{1}{42}\) est une fraction unitaire. L'algorithme est donc terminé, et nous avons obtenu, en rassemblant tous les résultats : \(\boxed{\dfrac{6}{7}=\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{42}}\).
Deuxième exemple :¶
Nous allons décomposer \(\dfrac{10}{21}\).
\(\dfrac{10}{21}\) n'est pas supérieur à \(\dfrac{1}{2}\), donc il est impossible d'écrire \(\dfrac{10}{21}=\dfrac{1}{2}+\text{reste}\), avec
\(\text{reste}\) qui serait un nombre positif.
Nous utilisons le principe de l'algorithme glouton, et regardons la fraction unitaire suivante : \(\dfrac{1}{3}\).
\(\dfrac{10}{21}\) est supérieur à \(\dfrac{1}{3}\), donc il est possible d'écrire \(\dfrac{10}{21}=\dfrac{1}{3}+\text{reste}\), avec
\(\text{reste}\) qui serait un nombre positif.
Calculons ce reste :
Troisième exemple:¶
Nous allons décomposer \(\dfrac{3}{7}\).
- \(\dfrac{3}{7}\) n'est pas supérieur à \(\dfrac{1}{2}\), donc il est impossible d'écrire \(\dfrac{10}{21}=\dfrac{1}{2}+\text{reste}\), avec \(\text{reste}\) qui serait un nombre positif.
- Nous utilisons le principe de l'algorithme glouton, et regardons la fraction unitaire suivante : \(\dfrac{1}{3}\).
\(\dfrac{3}{7}\) est supérieur à \(\dfrac{1}{3}\), donc il est possible d'écrire \(\dfrac{3}{7}=\dfrac{1}{3}+\text{reste}\), avec \(\text{reste}\) qui serait un nombre positif.
Calculons ce reste : \(\text{reste} = \dfrac{3}{7}-\dfrac{1}{3}=\dfrac{2}{21}\).
Mais \(\dfrac{2}{21}\) ne peut pas être simplifié, et n'est pas une fraction unitaire. - Nous reprenons le procédé avec la fraction unitaire suivante \(\dfrac{1}{4}\).
\(\dfrac{2}{21}\) n'est pas supérieur à \(\dfrac{1}{4}\). - Nous reprenons le procédé avec la fraction unitaire suivante \(\dfrac{1}{5}\).
\(\dfrac{2}{21}\) n'est pas supérieur à \(\dfrac{1}{5}\). - Nous reprenons le procédé avec la fraction unitaire suivante \(\dfrac{1}{6}\).
\(\dfrac{2}{21}\) n'est pas supérieur à \(\dfrac{1}{6}\). - Ainsi de suite ...
- \(\dfrac{2}{21}\) est supérieur à \(\dfrac{1}{11}\) donc il est possible d'écrire \(\dfrac{2}{21}=\dfrac{1}{11}+\text{reste}\), avec
\(\text{reste}\) qui serait un nombre positif.
Calculons ce reste :\(\text{reste} = \dfrac{2}{21}-\dfrac{1}{11}=\dfrac{1}{231}\). \(\dfrac{1}{231}\) est une fraction unitaire. L'algorithme est donc terminé, et nous avons obtenu, en rassemblant tous les résultats :
\(\boxed{\dfrac{3}{7}=\dfrac{1}{3}+\dfrac{1}{11}+\dfrac{1}{231}}\).
II. L'algorithme simple¶
a) Sans affichage
- Il faut d'abord simplifier la fraction donnée.
- Il faut initialiser
resteavec cette fraction simplifiée. - Tant que
resten'est pas unitaire, il faut soustraire àrestela plus grande fraction unitaire possible parmi \(\dfrac{1}{2},\dfrac{1}{3},\dfrac{1}{4},\dfrac{1}{5},\dfrac{1}{6},\dfrac{1}{7}\) ... , simplifier le résultat qui est le nouveaureste.
b) Avec affichage
Nous pourrons utiser une chaîne de caractères qui se complète à chaque tour de boucle. Par exemple dans le premier exemple, nous obtenons successivement :
decomposition = "1 /" + "2" + "+"`
decomposition = "1 /" + "2" + "+" + "1" + "/" + "3" + "+"`
decomposition = "1 /" + "2" + "+" + "1 /" + "3" + "+" + "1 /" + "42"`
III. Créer une classe Fraction¶
PGCD
Le calcul du pgcd de a et b permet la simplification directe de la fraction \(\dfrac{a}{b}\).
La bibliothèque math de python contient la méthode gcd pour calculer ce pgcd.
from math import gcd # gcd est en fait ce qu'en France on appelle pgcd
print(gcd(12, 18))
Pour coder l'algorithme nous allons utiliser une classe Fraction.
- Les éléments de la classe ont deux attributs :
num(numérateur) etdenom(dénominateur). - Nous aurons aussi besoin des méthodes
simplifieretmoins. - La méthode
simplifiervous est donnée. Vous pourrez la démontrer en cours de mathématiques, elle utilise le PGCD du numérateur et du dénominateur. - Soit un objet
fraction1, et un objetfraction2,fraction1.moins(fraction2)renvoie un objetFractionégal à la soustractionfraction1 - fraction2
Rapellons que $$\frac{a}{b} -\frac{c}{d} = \frac{ad-bc}{bd} $$
Classe Fraction
Compléter la classe Fraction suivante:
from math import gcd
class Fraction :
def __init__(self, num, denom) :
self.num = num
self.denom = denom
def __str__(self) :
return str(self.num)+ "/" +str(self.denom)
def __eq__(self, f) :
return self.num * f.denom == self.denom * f.num
def simplifier(self):
"""
Methode d'Euclide pour déterminer le pgcd du numérateur et du
dénominateur.
Pour trouver la forme simplifiée, on divise le numérateur et
le dénominateur par le pgcd du numérateur et du dénominateur
"""
a = self.num
b = self.denom
pgcd = gcd(a, b)
self.num = int(self.num/pgcd)
self.denom = int(self.denom/pgcd)
def moins(self, f2):
return ...
IV. L'algorithme glouton¶
Décomposition en fraction unitaire
Compléter ci-dessous la fonction decompose(a, b)qui prend en argument 2 entiers (numérateur et dénominateur) et qui renvoie la chaine de caractères donnant la décomposition en fractions égyptiennes de \(\dfrac{a}{b}\)
def decompose(a: int, b: int) -> str :
"""
Cette fonction renvoie la chaine de caractères
donnant la décomposition de a/b en fractions egyptienne
Exemple :
decompose(10,21)
>>> "10/21 = 1/3 + 1/7"
"""
reste = Fraction(a, b)
reste.simplifier() # peut être utile si la fraction de départ n'est pas irreductible
n = 2 # dénominateur de la 1ere fraction unitaire 1/2 parmi 1/2, 1/3, 1/4 etc...
decomposition = str(a) + "/" + str(b) + " = "
...
assert decompose(3, 5) == '3/5 = 1/2 + 1/10'