La fraction continue d'un nombre nest une fraction de la forme suivante:


qui converge vers n.

La séquence adans une fraction continue s'écrit généralement: [a ₀ ; a ₁ , a ₂ , a ₃ , ... a _n ].
Nous écrirons le nôtre de la même manière, mais avec la partie répétée entre les points-virgules.

Votre objectif est de renvoyer la fraction continue de la racine carrée de n.
Entrée: un entier n. nne sera jamais un carré parfait.
Production: La fraction continue de sqrt(n).

Cas de test:
2 -> [1; 2;]
3 -> [1; 1, 2;]
19 -> [4; 2, 1, 3, 1, 2, 8;]

Le code le plus court gagne. Bonne chance!

GolfScript ( 66 60 caractères)

~:^,{.*^>}?(:?';'[1?{^1$.*-@/?@+.2$/@@1$%?\- 1$(}do;;]','*1$

Attention: la plupart des entrées ?sont la variable représentant floor(sqrt(input))plutôt que la fonction intégrée. Mais le premier est le intégré.

Prend l'entrée sur stdin et les sorties sur stdout.

Psuedocode de l'algorithme (preuve de justesse actuellement laissée en exercice au lecteur):

n := input()
m := floor(sqrt(n))
output(m)
x := 1
y := m
do
  x := (n - y * y) / x
  output((m + y) / x)
  y := m - (m + y) % x
while (x > 1)

Encore une fois, je me retrouve à vouloir un seul opérateur qui prend a bla pile et laisse a/b a%bsur la pile.

Python, 95 97 (mais correct ...)

Cela utilise uniquement l'arithmétique entière et la division du sol. Cela produira des résultats corrects pour toutes les entrées entières positives, bien que si l'on veut utiliser un long, ils devront ajouter un caractère; par exemple m=a=0L. Et bien sûr ... attendez un million d'années que le sol de mon pauvre homme se termine.

z=x=m=1
while n>m*m:m+=1
m=y=m-1
l=()
while-z<x:x=(n-y*y)/x;y+=m;l+=y/x,;y=m-y%x;z=-1
print c,l

Production:

n=139
11 (1, 3, 1, 3, 7, 1, 1, 2, 11, 2, 1, 1, 7, 3, 1, 3, 1, 22)

edit: utilise maintenant l'algorithme de Peter Taylor. C'était do...whileamusant.

Python, 87 82 80

x=r=input()**.5
while x<=r:print"%d"%x+",;"[x==r],;x=1/(x%1)
print`int(r)*2`+";"

Il prend un entier et donne une sortie comme:

4; 2, 1, 3, 1, 2, 8;

Mathematica 33 31

c[n_]:=ContinuedFraction@Sqrt@n

La sortie est au format liste, ce qui est plus approprié pour Mathematica. Exemples:

c[2]
c[3]
c[19]
c[139]
c[1999]

(* out *)
{1, {2}}
{1, {1, 2}}
{4, {2, 1, 3, 1, 2, 8}}
{11, {1, 3, 1, 3, 7, 1, 1, 2, 11, 2, 1, 1, 7, 3, 1, 3, 1, 22}}
{44, {1, 2, 2, 4, 1, 1, 5, 1, 5, 8, 1, 3, 2, 1, 2, 1, 1, 1, 1, 1, 1, 
  1, 14, 3, 1, 1, 29, 4, 4, 2, 5, 1, 1, 17, 2, 1, 12, 9, 1, 5, 1, 43, 
  1, 5, 1, 9, 12, 1, 2, 17, 1, 1, 5, 2, 4, 4, 29, 1, 1, 3, 14, 1, 1, 
  1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 8, 5, 1, 5, 1, 1, 4, 2, 2, 1, 88}}

Python ( 136133 96)

La méthode standard pour les fractions continues, extrêmement golfée.

a=input()**.5
D=c=int(a);b=[]
while c!=D*2:a=1/(a%1);c=int(a);b+=[c]
print D,";%s;"%str(b)[1:-1]

C, 137

Y compris la nouvelle ligne, en supposant que je n'ai pas à rouler ma propre racine carrée.

#include<math.h>
main(i,e){double d;scanf("%lf",&d);e=i=d=sqrt(d);while(i^e*2)printf("%d%c",i,e^i?44:59),i=d=1.0/(d-i);printf("%d;",i);}

Il casse pour sqrt (139) et contient le point-virgule supplémentaire occasionnel dans la sortie, mais je suis trop fatigué pour y travailler plus loin ce soir :)

5
2, 4;
19
4, 2,1,3,1,2,8;
111
10, 1,1,6,1,1,20;

Perl, 99 caractères

Ne se gâche pas sur 139, 151, etc. Testé avec un nombre compris entre 1 et 9 chiffres.

$"=",";$%=1;$==$-=($n=<>)**.5;
push@f,$==(($s=$=*$%-$s)+$-)/($%=($n-$s*$s)/$%)until$=>$-;
say"$-;@f;"

Remarque: $%, $=et $-sont toutes les variables de forçage entier.

APL (NARS), 111 caractères, 222 octets

r←f w;A;a;P;Q;m
m←⎕ct⋄Q←1⋄⎕ct←P←0⋄r←,a←A←⌊√w⋄→Z×⍳w=0
L: →Z×⍳0=Q←Q÷⍨w-P×P←P-⍨a×Q⋄r←r,a←⌊Q÷⍨A+P⋄→L×⍳Q>1
Z: ⎕ct←m

La fonction f est basée sur l'algo one find dans la page http://mathworld.wolfram.com/PellEquation.html pour résoudre l'équation de Pell. Cette fonction f a son entrée tout nombre non négatif (type de fraction aussi). Il y a peut-être quelque chose qui ne va pas, je me souviens que √ a, dans ma façon de voir, un problème pour les grands nombres de

  √13999999999999999999999999999999999999999999999x
1.183215957E23 

il y aurait donc une fonction sqrti (). Pour cette raison, l'entrée fraction (et l'entrée entière) doit être <10 ^ 15. tester:

 ⎕fmt (0..8),¨⊂¨f¨0..8
┌9───────────────────────────────────────────────────────────────────────────────────────────────────────┐
│┌2─────┐ ┌2─────┐ ┌2───────┐ ┌2─────────┐ ┌2─────┐ ┌2───────┐ ┌2─────────┐ ┌2─────────────┐ ┌2─────────┐│
││  ┌1─┐│ │  ┌1─┐│ │  ┌2───┐│ │  ┌3─────┐│ │  ┌1─┐│ │  ┌2───┐│ │  ┌3─────┐│ │  ┌5─────────┐│ │  ┌3─────┐││
││0 │ 0││ │1 │ 1││ │2 │ 1 2││ │3 │ 1 1 2││ │4 │ 2││ │5 │ 2 4││ │6 │ 2 2 4││ │7 │ 2 1 1 1 4││ │8 │ 2 1 4│││
││~ └~─┘2 │~ └~─┘2 │~ └~───┘2 │~ └~─────┘2 │~ └~─┘2 │~ └~───┘2 │~ └~─────┘2 │~ └~─────────┘2 │~ └~─────┘2│
│└∊─────┘ └∊─────┘ └∊───────┘ └∊─────────┘ └∊─────┘ └∊───────┘ └∊─────────┘ └∊─────────────┘ └∊─────────┘3
└∊───────────────────────────────────────────────────────────────────────────────────────────────────────┘
  f 19
4 2 1 3 1 2 8 
  f 54321x
233 14 1 1 3 2 1 2 1 1 1 1 3 4 6 6 1 1 2 7 1 13 4 11 8 11 4 13 1 7 2 1 1 6 6 4 3 1 1 1 1 2 1 2 3 1 1 14 466 
  f 139
11 1 3 1 3 7 1 1 2 11 2 1 1 7 3 1 3 1 22 
  +∘÷/f 139
11.78982612
  √139
11.78982612

si l'argument est un carré d'un nombre, il retournerait une liste de 1 seul élément, le carré de ce nombre

  f 4
2 

Si cela dépendait de moi, dans un exercice sans "codegolf" je préférerais l'édition précédente qui utilise la fonction sqrti () ...