Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 30-04-2019 19:44:50

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Fraction continuue

Bonsoir @ tous.

Chacun connait l'écriture d'une fraction A/B en "fraction continue" :

A/B = (a1, a2, a3, ...an ) <===> a1 + 1 / ( a2 + 1 / ( a3 + 1 / ...an))))

Si on a l'écriture (a1, a2, a3,....an) on sait recalculer A/B en partant de "an" et en remontant jusqu'à "a1".

Cependant, on peut aussi retrouver A/B en calculant à partir de "a1" pour finir à "an".

Mais comment ça marche donc ce calcul en rétro ????

Bonne recherche

  • |
  • Répondre

#0 Pub

 #2 - 30-04-2019 23:19:40

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Fraction contiune

Notons [latex]c_k = a_k + \cfrac{1}{a_{k+1} + \cfrac{1}{  ... a_n}}[/latex]

On peut montrer par récurrence que la fraction peut s'écrire
[TeX]\dfrac{a\times  c_k + b}{c\times c_k + d}[/TeX]
(a,b,c,d dépendant de k)

En effet, [latex]c_k= a_k + \dfrac{1}{c_{k+1}} [/latex]
On peut alors remplacer et simplifier pour se ramener à cette forme.
Cette récurrence fournit le programme de calcul.

 #3 - 01-05-2019 09:01:23

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

fraction conyinue

Oui Caduk.

Mais de manière pratique ?

Calculer par exemple de gauche à droite : ( 1,2,1,1,2,2,1,3)

A la main bien entendu.

 #4 - 01-05-2019 12:18:14

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

Fraction ocntinue

Si on note An/Bn la fraction égale à (a1, a2, a3,....an), on a les relations :

A(n+1) = An*a(n+1) + A(n-1) et B(n+1) = Bn*a(n+1) + B(n-1) qui permettent de calculer les An et Bn de proche en proche.

Par exemple, pour (1,2,1,1,2,2,1,3) :
A1 = 1 et B1 = 1
A2 = 3 et B2 = 2
A3 = 3*1+1 = 4 et B3 = 2*1+1 = 3
A4 = 4*1+3 = 7 et B4 = 3*1+2 = 5
A5 = 7*2+4 = 18 et B5 = 5*2+3 = 13 ...

 #5 - 01-05-2019 14:46:28

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Fration continue

En utilisant ma méthode de calcul:
c
1+1/c = (c+1)/c
((2+1/c)+1)/(2+1/c) = ((3c+1)/c)/((2c+1)/c = (3c+1)/(2c+1)
(3(1+1/c)+1)/(2(1+1/c)+1) = ((4c+3)/c)/((3c+2)/c) = (4c+3)/(3c+2)
(4(1+1/c)+3)/(3(1+1/c)+2) = (7c+4)/(5c+3)
...

On peut expliciter un peu le calcul des coefficients.
Renommons d'abord les coefficients pour éviter les confusions
[TeX]\frac{A}{B}=\dfrac{w_k  c_k + x_k}{y_kc_k + z_k}[/TeX]
On a:
[TeX]w_0 = z_0 = 1, x_0=y_0=0[/TeX]
[TeX]\frac{A}{B}=\cfrac{w_k \left(a_k+ \cfrac{1}{c_{k+1}}\right) + x_k}{y_k \left(a_k+ \cfrac{1}{c_{k+1}}\right) + z_k} = \cfrac{\cfrac{\left(w_ka_k+x_k\right)c_{k+1}+w_k}{c_{k+1}}}{\cfrac{\left(y_ka_k+z_k\right)c_{k+1}+y_k}{c_{k+1}}} = \dfrac{\left(w_ka_k+x_k\right)c_{k+1}+w_k}{\left(y_ka_k+z_k\right)c_{k+1}+y_k}[/TeX]
On obtient donc les relations de récurrence:
[TeX]w_{k+1} = w_ka_k+x_k[/TeX]
[TeX]x_{k+1} = w_k[/TeX]
[TeX]y_{k+1} = y_ka_k+z_k[/TeX]
[TeX]z_{k+1} = y_k[/TeX]
On peut donc dresser le tableau du calcul de cette suite:

Code:

  k    0  1  2  3  4  5   6   7
  a_k  1  2  1  1  2  2   1   3 
  w_k  1  1  3  4  7  18  43  61  226
  x_k  0  1  1  3  4  7   18  43  
  y_k  0  1  2  3  5  13  31  44  163
  z_k  1  0  1  2  3  5   13  31

La fraction recherchée est donc 226/163

A noter que l'on peut simplifier un peu la récurrence en:
[TeX]w_{k+2} = w_{k+1}a_{k+1}+w_k[/TeX]
[TeX]y_{k+2} = y_{k+1}a_{k+1}+y_k[/TeX]

 #6 - 01-05-2019 17:40:41

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Fration continue

@ Ebichu: c'est OK, bravo !

Il manque peut être la généralisation des valeurs A0/B0 et A1/B1 pour toute fraction, peux tu la donner ?

@ Caduk : C'est bien détaillé, parfait !

Peut être maintenant un algo simple avec moins de variables pour mise en œuvre pratique ? (sans tableau).

 #7 - 02-05-2019 21:59:50

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

FFraction continue

Oui, bien sûr. On peut initialiser avec A0=1, B0=0, A1=a1, B1=1.

 #8 - 03-05-2019 11:19:07

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Fraction conntinue

@ Ebichu : il y a une autre possiblité ?

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete