NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 28/01/2014

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Type de nombres

 

Débutants

Général

FRACTIONS

 

Glossaire

Fraction

 

 

INDEX

Calcul

Débutant

Unitaire

Continues

Égyptiennes

Comparaison

Règle de trois

Somme 1

Glouton

Construction

Illicites

Inverse

Identités

Puissances

 

Sommaire de cette page

>>> Algorithme glouton

>>> Programmation

>>> Valeurs des fractions usuelles

>>> Constantes et leurs fractions égyptiennes

 

 


 

 

FRACTIONS ÉGYPTIENNES

 

Algorithme glouton pour le calcul des fractions égyptiennes.

Anglais: Greedy algorithm

 

Algorithme glouton

 

*      En 1201, Fibonacci trouve un algorithme pour effectuer une décomposition en fractions égyptiennes. La méthode a été redécouverte en 1880 par James Sylvester. Par contre, la méthode utilisée par les Égyptiens n'est pas connue.

*      Voyons sur des exemples comment faire fonctionner cet algorithme.

 

 

Première approche

 

*      Une fraction de départ, inférieure à 1, sinon retirez la partie entière.

*      Trouvez une fraction unitaire inférieure à 4/5 ou 8/10; 5/10 = 1/2 remplit la condition.

*      Cherchez la différence.

*      La fraction différence n'est pas unitaire; poursuivons avec cette nouvelle fraction.

*      Une fraction unitaire inférieure à 3/10 serait 2/10 = 1/5.

*      Calculez la différence; la fraction obtenue est unitaire.

*      C'est fin de l'algorithme.

*      Les trois fractions obtenues forment le résultat attendu.

 

 

 

 

4/5

 

1/2 < 4/5

 

 

 

1/5 < 3/10

 

 

 

 

 

Choix de la fraction

 

*         Une fraction de départ.

*         L'inverse de la fraction et l'entier juste supérieur.

 

*         La fraction sera l'inverse de cet entier.

 

 

*         Inverse de la fraction et entier supérieur.

*         Nouvelle différence.

 

 

 

 

*         Résultat.

 

 

 

 

77 / 111

 

111/77 < 2

 

 

222/43 = 5,… < 6

 

 

 

 

Optimisation

*        Avec cet algorithme le premier résultat ci-dessus est optimisé.

*        Cependant, même avec cet algorithme, il n'est pas sûr d'obtenir la meilleure des optimisations.

 

 

À comparer au premier résultat ci-dessus

 

 

 

Représentation de nombres irrationnels

 

*        Cet algorithme s'applique à tout nombre, y compris les nombres irrationnels.

 

 

 

Pi = 3

+ 1/8

+ 1/61                => 3,1414

+ 1/5020            => 3,14159264

+ 1/128541455

+ …

 

 

 

 

 

Programmation

 

Rationnels

 

> # algorithme glouton

Num:=77: Den:= 111:

lprint(Num/Den):

 

for i from 1  while i <10 do   

   E:=trunc(Den/Num)+1:

   lprint(1/E):       

     
      Num:=Num*E-Den:

      Den:=Den*E:

      F:=Num/Den:

 

 

 

   if numer(F)=1 then i:=100:lprint(Num/Den);fi:

 

od:

 

 

>

77/111

1/2

1/6

1/37

 

 

 

 

 

 

Exemple: 77 / 111

Impression de cette fraction.

 

Boucle limitée à 10 itérations.

Calcul du dénominateur de la nouvelle fraction et impression de celle-ci.

Nouvelle fraction différence.

 

Mise sous forme de fraction F.

 

Si le numérateur de cette nouvelle fraction vaut 1, c'est la fin: imprimer cette fraction; donner une grande valeur au pointeur de boucle qui forcera l'arrêt.

 

 

Résultat de l'exécution de cet algorithme.

 

 

 

 

Irrationnels

 

> # algorithme glouton

Num:=Pi-3: Den:= 1:P:=30:

lprint(Num/Den):

 

for i from 1  while i <7 do   

   EE:= evalf(Den/Num,30):

   E:=trunc(EE)+1:

   lprint(1/E):       

      Num:=evalf(Num*E-Den,30):

      Den:=evalf(Den*E,30):

      F:=Num/Den:

od:

 

 

 

Note: cet algorithme devra être adapté pour calculer des valeurs irrationnelles: introduire l'instruction evalf.

Inutile de tester si le numérateur vaut 1; les fractions se suivent sans fin …

 

Voir Programmation Mapple

 

 

Quelques valeurs usuelles

 

         Décimal     1/a        = 1/b   + 1/c  + 1/d

          0,1          1/10        1/11    1/110  

          0,111        1/9         1/10    1/90   

          0,125        1/8         1/9     1/72   

          0,142        1/7         1/8     1/56   

          0,1666       1/6         1/7     1/42   

          0,2          1/5         1/6     1/30   

          0,222        2/9         1/5     1/45   

          0,25         1/4         1/5     1/20   

          0,285        2/7         1/4     1/28   

          0,3          3/10        1/4     1/20   

          0,333        1/3         1/4     1/12   

          0,375        3/8         1/3     1/24   

          0,4          2/5         1/3     1/15   

          0,428        3/7         1/3     1/11    1/231

          0,444        4/9         1/3     1/9    

          0,5          1/2         1/3     1/6    

          0,555        5/9         1/2     1/18   

          0,571        4/7         1/2     1/14   

          0,6          3/5         1/2     1/10   

          0,625        5/8         1/2     1/8    

          0,666        2/3         1/2     1/6    

          0,7          7/10        1/2     1/5    

          0,714        5/7         1/2     1/5     1/70

          0,75         3/4         1/2     1/4    

          0,777        7/9         1/2     1/4     1/36

          0,8          4/5         1/2     1/4     1/20

          0,833        5/6         1/2     1/3    

          0,857        6/7         1/2     1/3     1/42

          0,875        7/8         1/2     1/3     1/24

          0,888        8/9         1/2     1/3     1/18

          0,9          9/10        1/2     1/3     1/15

 

Voir Comparaisons entre fractions usuelles / Table des fractions égyptiennes

 

 

 

Constantes et leurs fractions égyptiennes

Constante

Valeur

Fractions pour la partie décimale

0,3183098861

 

1/4                   Ces fractions s'ajoutent  

1/15                 pour plus ou moins de précision.

1/609

1/845029

1/1010073215739

1/1300459934891669100860858

Log 2

0,6931471806

 

1/2

1/6

1/38

1/6071

1/144715221

1/58600453312398682

0,7071067810

 

1/2

1/5

1/141

1/68575

1/32089377154

1/1644444236993982746479

1,236067977

 

1/5

1/28

1/2828

1/11765225

1/244616741135816

1/95913226236687016170827960389

1,414213562

 

1/3

1/13

1/253

1/218201

1/61323543802

1/5704059162715143504206

1,618033988

 

1/2

1/9

1/145

1/37986

1/2345721887

1/26943815937518486733

1,645751311

 

1/2

1/7

1/346

1/250326

1/159992246122

1/43126924985547822379813

1,732050808

 

1/2

1/5

1/32

1/1249

1/5986000

1/438522193400489

e

2,718281828

 

1/2

1/5

1/55

1/9999

1/3620211523

1/25838201787744990449

3,141592654

 

1/8

1/61

1/5020

1/128541455

1/162924332716725506

1/31542549081136766821160233132100001

Voir Constantes

 

 

 

 


 

Suite

*    Comparaison des fractions usuelles

*    Fractions dont la somme est égale à 1

*    Sommes d'inverses

*    FractionsGlossaire et index

Voir

*    Tables des fractions égyptiennes 

*    Fraction avec 0,65

Aussi

*    HistoireIndex

*    GéométrieIndex

*    Récurrence

*    Théorie des nombresIndex

DicoNombre

*    Nombre 1/4

*    Nombre 1/3

*    Nombre 1/2

*    Nombre 2/3

*    Nombre 3/4

Cette page

http://villemin.gerard.free.fr/Calcul/Fraction/Glouton.htm