Simplifiez une fraction continue

21

Les fractions continues sont des expressions qui décrivent les fractions de manière itérative. Ils peuvent être représentés graphiquement:

entrez la description de l'image ici

Ou ils peuvent être représentés comme une liste de valeurs: [a0; a1, a2, a3, ... an]

Le défi:

prendre un nombre de base: et une liste de valeurs de dénominateur: et simplifier la fraction continue en une fraction rationnelle simplifiée: retourner ou imprimer numérateur et dénominateur séparément.a0[a1, a2, a3, ... an]

Exemples:

  • √19 : [4;2,1,3,1,2]: 170/39
  • ℯ: [1;0,1,1,2,1,1]: 19/7
  • π: [3;7,15,1,292,1]: 104348/33215
  • ϕ: [1;1,1,1,1,1]: 13/8

Exemple d'implémentation: (python)

def foo(base, sequence):
    numerator = 1
    denominator = sequence[-1]
    for d in sequence[-2::-1]:
        temp = denominator
        denominator = d * denominator + numerator
        numerator = temp
    return numerator + base * denominator, denominator

Gagnant:

code le plus court en octets: - pas de code intégré qui résout tout le problème -

Aaron
la source
Vous devriez rendre cette phrase plus claire, "et simplifier la fraction continue en une seule fraction"; sauf si vous vouliez que le libellé signifie un résultat de 2.002peut être exprimé comme 2002/1000. C'est techniquement une "fraction unique", vous voudrez probablement dire, "une fraction unique, dans sa forme la plus simple."
Urne de poulpe magique
@carusocomputing point pris .. même si je ne me sentirais pas trop mal à propos des 2/4 (ou similaire) car cela a toujours simplifié la structure des fractions multiples en une seule fraction
Aaron
Hmm ... Je pense qu'il y a un moyen d'exploiter cela, mais avec la réponse golfscript de 13 octets, je devrais probablement utiliser MATL pour gagner.
Urne de poulpe magique du
@carusocomputing Je dirais allez-y ... Si vous pouvez battre la réponse de 13 octets, ce serait génial
Aaron
Vous pouvez arrêter le pi plus tôt - 355/113.
Thorbjørn Ravn Andersen

Réponses:

15

J, 8 5 octets

Identique à cela , mais utilise un build-in pour les justifications.

L'argument est {a0, a1, a2, a3, ...} comme une liste de J nombres rationnels à précision étendue. Le résultat est la fraction sous la forme d'un nombre rationnel J à précision étendue.

(+%)/

(+%) le plus-la-réciproque

/ réduction sur

Essayez-le en ligne!

-3 grâce aux miles .

Adam
la source
Si vous prenez l'entrée comme une liste d'entiers étendus, vous pourriez économiser 3 octets. Vous avez également utilisé la division APL dans l'explication.
miles
@miles Merci. Je ne peux pas me rapprocher de l'interdiction intégrée. Dommage que J n'ait pas de caractère de composition de crochet comme Dyalog APL .
Adám
Le lien en ligne de l'essai J est rompu
Chiel ten Brinke
@ChieltenBrinke Merci. Fixé.
Adám
12

Haskell, 37 36 18 octets

foldr1$(.(1/)).(+)

Cette fonction attend le Ratiotype de Haskell en entrée. Exemple d'utilisation:

Prelude Data.Ratio> ( foldr1$(.(1/)).(+) )  [4%1,2,1,3,1,2] 
170 % 39

Remarque: un explicite Ratiodans la liste d'entrée ( 4%1) suffit, le type systèmes comprend que les autres doivent aussi être Ratios.

Modifier: @Lynn a enregistré un octet. Merci!

Edit II: supprimé le import(voir cette discussion sur la méta ).

nimi
la source
1
Oooh, belle affaire de bord. La fonction elle-même est polymorphe, elle n'a donc pas besoin de la import. Cependant pour l'appeler, vous devez lui fournir des Ratios qui ont besoin de import. Dois-je ajouter le nombre importd'octets ou non?
nimi
1
Cela ressemble à une bonne question pour la méta.
Martin Ender
Je n'ai jamais utilisé Haskell, corrigez-moi si je me trompe, mais si l'équivalent python serait: from fractions import Fractionpour faire des opérations avec des Fractionobjets, l'instruction import est également comptée.
Aaron
.. nous avions ça avant .
nimi
@Aaron: le problème est: la définition de la fonction n'a pas besoin d'être importée, car elle est polymorphe. Lorsque vous voulez l'appeler, vous devez fournir des numéros de type Ratioqui ne peuvent être construits que via %, ce qui nécessite l'importation. Habituellement, nous ne comptons pas les octets pour appeler la surcharge, juste pour la fonction elle-même.
nimi
11

GolfScript , 13 octets

~]-1%{\-1?+}*

Essayez-le en ligne!

Ouais pour les logiques cachées de GolfScript . :)

Explication

Le seul type de numéro "officiel" de GolfScript est des entiers. Mais l'opérateur d'exponentiation ne convertit pas son résultat en entier et, commodément, le résultat natif d'une exponentiation d'entier dans Ruby (le langage de l'interpréteur de GolfScript) est un nombre rationnel. Ainsi, nous pouvons facilement obtenir des fractions en élevant quelque chose à la puissance de -1. Idéalement, nous voulons quand même des réciproques ...

~]     # Evaluate input and wrap all a_i in a list.
-1%    # Reverse the list so that a_n is at the start and a_0 at the end.
{      # Fold... (apply this block to each element from a_n-1 down to a_0, with
       # the previous result on the stack)
  \    #   Swap previous result with current a_i.
  -1?  #   Raise previous result to the power of -1, computing its reciprocal
       #   as a rational number.
  +    #   Add a_i.
}*
Martin Ender
la source
11

Mathematica, 23 22 octets

Fold[#2+1/#&]@*Reverse

Essentiellement un portage de ma réponse GolfScript . Voici quelques alternatives:

Pour 24 octets, nous pouvons écrire une fonction variadique récursive:

f@n_=n
n_~f~m__:=n+1/f@m

Pour 21 octets, nous pouvons même définir un "opérateur variadique", mais sa convention d'appel serait tellement bizarre, que je suis réticent à compter celui-ci:

±n_=n
n_ ±m__:=n+1/±m

Vous devez l'appeler avec une séquence de valeurs d'entrée, par exemple ±Sequence[3, 7, 15, 1, 292, 1]ou ±##&[3, 7, 15, 1, 292, 1].

Et aussi pour 21 octets, il y aurait le intégré (interdit):

FromContinuedFraction
Martin Ender
la source
10

LabVIEW, 36 octets équivalents

Implémentation naïve assez simple à l'aide de l'algorithme OP. Existe-t-il une meilleure façon de procéder?

entrez la description de l'image ici

ijustlovemath
la source
5
Votre diplôme en génie électrique montre.
Urne de poulpe magique du
1
@ijustlovemath Props, mais ..... pertinent
Aaron
Oui, c'est un langage controversé pour être sûr. Je vois LabVIEW comme le "Je déteste les mathématiques" du monde des programmeurs. Le problème n'est pas les mathématiques en elles-mêmes, mais la façon dont elles sont enseignées (ou souvent le manque d'enseignement).
ijustlovemath
6

Dyalog APL , 10 octets

N'utilise même pas de build-in pour les justifications.

Prend {a 0 , a 1 , a 2 , a 3 , ...} comme argument, renvoie {dénominateur, numérateur}.

1(,÷∨)+∘÷/

1(,÷∨) 1-ajouté à divisé par le GCD de 1 et

+∘÷ plus-la-réciproque

/ réduction sur

TryAPL en ligne!

Adam
la source
6

Python 2, 62 octets

a=d=0
b=c=1
for n in input():a,b=b,n*b+a;c,d=d,n*d+c
print b,d

Ce n'est malheureusement pas aussi golfique (voir la réponse de @ xnor pour plus court), mais il calcule la fraction sans avoir besoin d'inverser l'entrée. Cela utilise l' approche "table magique" pour les convergents - étant donné les deux dernières fractions a/cet b/d, la fraction suivante est (n*b+a)/(n*c+d).

Par exemple, pour pi:

          3    7    15     1      292        1

  0   1   3   22   333   355   103993   104348
  1   0   1    7   106   113    33102    33215

Nous pouvons voir que 15*22 + 3 = 333, 15*7 + 1 = 106, 1*333 + 22 = 355, 1*106 + 7 = 113, etc.

Sp3000
la source
4

M, 5 octets

Ṛİ+¥/

L'entrée est une liste de valeurs [a0, a1, ..., aN]et elle sort un nombre rationnel.

Essayez-le en ligne! ou Vérifiez tous les cas de test.

Explication

Ṛİ+¥/  Input: list A
Ṛ      Reverse A
    /  Reduce A from left to right using
   ¥     A dyadic chain
 İ         Take the reciprocal of the left value
  +        Add the reciprocal to the right value
       Return and print implicitly
miles
la source
1
Qu'est-ce que c'est? Un nouveau dialecte de gelée?
Adám
@miles en fait 9 octets désolé :(
Aaron
@ Adám C'est une vieille fourchette de gelée destinée aux mathématiques et à la symbolique. Voici son repo Github .
miles du
1
@Aaron M utilise la même page de codes que Jelly, et elle peut être encodée en utilisant un octet pour chaque caractère.
miles
@miles OK, a ajouté .
Adám
4

Haskell, 30 octets

foldr(\h(n,d)->(h*n+d,n))(1,0)

Ajoute la mise à jour récursive chaque couche allant vers l' extérieur, n/dà h+(1/(n/d))qui est égal à h+d/nou (h*n+d)/n. La fraction est stockée sous la forme d'un tuple de (num,denom). La fraction initiale de (1,0)flips à 0/1laquelle est 0.

xnor
la source
3

Python, 50 octets

f=lambda l,n=1,d=0:l and f(l,l.pop()*n+d,n)or(n,d)

Construit la fraction continue à partir de la fin de la liste en remontant, en mettant à jour à plusieurs reprises la fraction n/dsur le dernier élément en xtant que n/d -> 1+1/(n/d) == (x*n+d)/n.

xnor
la source
3

 Lisp commun, 54

Un repli un peu bavard:

(lambda(s)(reduce(lambda(a r)(+(/ r)a))s :from-end t))

Les tests

PASS  NAME  ACTUAL               EXPECTED
===============================================
T     √19   170/39               170/39              
T     ℯ     19/7                 19/7                
T     π     104348/33215         104348/33215        
T     ϕ     13/8                 13/8                
coredump
la source
2

Julia (53 octets)

C'est la première fois que j'utilise Julia, si j'avais négligé un itérateur que j'aurais pu perdre plus d'octets, faites le moi savoir. Voici un indice pour quiconque ne sait pas quelle langue choisir pour ce défi spécifique: https://en.wikipedia.org/wiki/Rational_data_type

f(x,c)=(a=0;for b in x[end:-1:1];a=1//(b+a);end;a+c;)
  • Inversez le tableau d'entrée.
  • Itérer à travers elle avec division rationnelle.
  • Ajoutez c au résultat décimal.
Urne de poulpe magique
la source
vous pouvez enregistrer deux octets en définissant un opérateur (par exemple ) au lieu d'une fonction
Tasos Papastylianou
aussi, changez la boucle for pendant un moment et pop:x∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
Tasos Papastylianou
1
25: x->foldr((x,y)->x+1//y,x)(identique à la solution Haskell). utilisation:(x->foldr((x,y)->x+1//y,x))([4//1,2,1,3,1,2])
Fengyang Wang
Ooo ... Une fonction de pliage inversé? C'est beau! Je ne mérite pas de m'en attribuer le mérite, haha.
Urne de poulpe magique du
2

Javascript (ES6), 55 octets

s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

Cas de test

var f =
s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

console.log(f([4, 2, 1, 3, 1, 2]));
console.log(f([1, 0, 1, 1, 2, 1, 1]));
console.log(f([3, 7, 15, 1, 292, 1]));
console.log(f([1, 1, 1, 1, 1, 1]));

Arnauld
la source
2

CJam , 18 16 octets

XUq~W%{2$*+\}/]p

Interprète en ligne .

XU                  Push 1 and 0 to the stack
  q~W%              Push input, eval and reverse it
      {     }/      For each n in the reversed input...
       2$             Copy numerator
         *+           Calculate n*denominator + numerator
           \          Swap numerator and denominator
              ]p   Wrap in array and output
Sp3000
la source
2

05AB1E , 19 17 octets

R¬V¦vyY*X+YUV}YX)

Explication

Entrée prise comme une liste de nombres

                     # variable X is initialized as 1
R¬V¦                 # reverse the list, remove the first item and store it in variable Y
    v        }       # for each item N left in list
     yY*X+  V        # store N*Y+X in Y
          YU         # store Y in X
              YX)    # wrap X and Y in a list

Essayez-le en ligne!

Emigna
la source
2

JavaScript (ES6), 44 octets

a=>a.reduceRight(([n,d],v)=>[v*n+d,n],[1,0])
Neil
la source
1

Javascript (ES6), 50 octets

f=(s,n=1,d=s.pop())=>s+""?f(s,d,s.pop()*d+n):[d,n]

C'est grâce à la réponse d'Arnauld, avant de le voir j'étais coincé à 66 octets:

f=(b,s,i=s.length-1,n=1,d=s[i])=>i?f(b,s,--i,d,s[i]*d+n):[n+b*d,d]

Exemple:
Appel: f([1, 0, 1, 1, 2, 1, 1])
Sortie:Array [ 19, 7 ]

Hedi
la source
1

Perl 6 , 24 octets

{[R[&(1/*+*)]](@_).nude}

Explication:

  • 1 / * + *est un lambda à deux paramètres ( *) qui prend l'inverse du premier et ajoute le second. (renvoie un rat )

  • R[&(…)]l'utilise comme s'il s'agissait d'un opérateur infixe et l'inverse.
    (y compris le rendre associatif)

  • […](@_) prend cela et l'utilise pour réduire l'entrée.

  • … .nuderetourne le nu merator et de proposeur du Rat .

  • { … }en faire un lambda de bloc nu avec un paramètre implicite @_.

Usage:

say {[R[&(1/*+*)]](@_).nude}(3,7,15,1,292,1) #*/# (104348 33215)

my &code = {[R[&(1/*+*)]](@_).nude}; # stupid highlighter */

say code 4,2,1,3,1,2;    # (170 39)
say code 1,0,1,1,2,1,1;  # (19 7)
say code 1,1,1,1,1,1;    # (13 8)
Brad Gilbert b2gills
la source
1

Zephyr , 145 octets

input n as Integer
set a to Array(n)
for i from 1to n
input a[i]as Integer
next
set r to a[n]
for i from 1to n-1
set r to(/r)+a[n-i]
next
print r

Zephyr est le premier langage de programmation que j'ai jamais créé. Il a été conçu pour être intuitif et avoir une syntaxe propre - plutôt au détriment de la brièveté. Pourquoi est-ce que je joue avec, demandez-vous? Parce que, contrairement à toutes les langues que j'ai écrites depuis, il a un type intégré Fraction. Vous pouvez même utiliser l'opérateur de division /comme opérateur unaire pour "inverse" (une fonctionnalité que j'ai empruntée pour Pip).

Maintenant, il y a des limitations importantes. Le plus gros problème pour ce défi est que les tableaux doivent être définis avec une taille fixe, ce qui signifie que le programme commence par lire la taille du tableau à l'utilisateur. (J'espère que cela est correct; l'alternative consiste à coder en dur la taille.) Il y a aussi le problème mineur que la priorité des opérateurs n'existe pas, ce qui signifie que les expressions multi-opérateurs doivent avoir des parenthèses.

Voici un exemple d'exécution:

C:\Zephyr> python zephyr.py contfrac.zeph
6
1
1
1
1
1
1
13/8
DLosc
la source
1

Rubis, 34 octets

->a{a.reverse.inject{|b,i|i+1r/b}}

Cela effectue un pliage à droite (en inversant puis en pliant à gauche), en ajoutant chaque élément à 1 sur le total cumulé (les éléments à droite). Ruby a le type Rational, ce qui est vraiment sympa. Et les justifications littérales sont un nombre suffixé avec r.

IMP1
la source
1

Stax , 4 octets

╣╩┼►

Exécuter et déboguer

Aussi petit soit-il, ce n'est pas un système intégré. Les logiques intégrées aident cependant un peu. Déballé en ascii, le programme est rksu+.

  1. Inversez le tableau.
  2. Pliez le tableau à l'aide de (a, b) => (a + 1/b).
récursif
la source
1

APL (NARS), 15 + 1 caractères, 30 + 2 octets

{1=≢⍵:↑⍵⋄+∘÷/⍵}

Traduction en Apl (Nars) de la solution d'Adam J ... l'entrée autorisée pour cette fonction sera toute liste de nombres entiers, où le premier élément sera de type rationnel. Tester:

  f←{1=≢⍵:↑⍵⋄+∘÷/⍵}      
  f 4x 2 1 3 1 2
170r39 
  f 1x 0 1 1 2 1 1
19r7 
  f 3x 7 15 1 292 1
104348r33215 
  f 1x 1 1 1 1 1
13r8 
  f 3x 89 888 999 11 222 373 7282 9272 3839 2828 
158824716824887954093160207727r52744031585005490644982548907 
  f ,0x
0 
  f ,9x
9 

ce serait donc 15 caractères comme longueur de fonction et 1 caractère pour "x" pour entrer le type d'entrée que je veux et quitter le type que je veux ...

RosLuP
la source