ALGO EXO

Les égyptiens (2.000 AC) utilisant une technique particulière pour calculer le quotient de 2 nombres:
Exemple : 253 à diviser par 27
Ils établissaient certains multiples du dénominateur, en multipliant le nombre obtenu par 2, jusqu’à l’obtention d’un nombre supérieur au numérateur.
27	1	253
54	2	-216(=8*27)
108	4	----
216	8	37
512	16	-24(=1*27)
	   ----
	     10

On peut conclure que 253=10+(1*27)+(8*27) ou que 253/27=9+10/27 et 10/27 était exprimé sous la forme d’une somme de fractions a numérateur unitaire (seul exception 2/3 était aussi accepté) et à dénominateur différents. Donc 253*27=9+1/3+1/27
On a tout naturellement donné le nom de ‘fraction égyptienne’ à la représentation d’une fraction sous la forme d’une somme de fractions à numérateurs unitaires.
On ne sait pas très bien comment les égyptiens procédaient pour obtenir cette décomposition. Par contre, on sait que quand ils obtenaient une fraction du type 2/(pq), ils appliquaient la formule :
2/pq= 1/(p (p+q)/2)+1/(q (p+q)/2)

Remarque :
Notons que la représentation sous forme d’une somme de fraction à numérateurs unitaires n’est pas unique. C’est pourquoi, ils avaient décidé d’utiliser celle contenant le moins de termes.
1/n=1/(n+1)+1/(n(n+1))

En 1201, Fibonacci (Léonard de Pise) prouva que tout nombre relationnel N/D pouvait s’écrire sous la forme d’une somme de fractions à numérateur unitaire et décrivit une méthode pour l’obtention des dénominateurs :
-Si le nombre fractionnaire est supérieur à 1 (numérateur N supérieur au dénominateur D), on sépare la partie entière de la partie fractionnaire N’/D avec laquelle on travaillera ;
-Si N’=1, la décomposition est terminée sinon on recherche la plus grande fraction 1/a inférieure ou égale à N’/D (donc le plus petit dénominateur a tel que 1/a est inférieur ou égal) ;
-On recommence avec N’/D-1/a sauf si le nouveau numérateur est unitaire.

Application 3 :
Donner le code en pascal et en python qui permet d’obtenir la décomposition ci-dessus étudiée par Fibonacci, sans utiliser de fonction.