Les fractions continues sont des expressions qui décrivent les fractions de manière itérative. Ils peuvent être représentés graphiquement:
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
2.002
peut être exprimé comme2002/1000
. C'est techniquement une "fraction unique", vous voudrez probablement dire, "une fraction unique, dans sa forme la plus simple."Réponses:
J,
85 octetsIdentique à 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 surEssayez-le en ligne!
-3 grâce aux miles .
la source
∘
.Haskell,
373618 octetsCette fonction attend le
Ratio
type de Haskell en entrée. Exemple d'utilisation:Remarque: un explicite
Ratio
dans la liste d'entrée (4%1
) suffit, le type systèmes comprend que les autres doivent aussi êtreRatio
s.Modifier: @Lynn a enregistré un octet. Merci!
Edit II: supprimé le
import
(voir cette discussion sur la méta ).la source
import
. Cependant pour l'appeler, vous devez lui fournir desRatio
s qui ont besoin deimport
. Dois-je ajouter le nombreimport
d'octets ou non?from fractions import Fraction
pour faire des opérations avec desFraction
objets, l'instruction import est également comptée.Ratio
qui 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.GolfScript , 13 octets
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 ...
la source
Mathematica,
2322 octetsEssentiellement un portage de ma réponse GolfScript . Voici quelques alternatives:
Pour 24 octets, nous pouvons écrire une fonction variadique récursive:
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:
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):
la source
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?
la source
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-ajouté à divisé par le GCD de 1 et+∘÷
plus-la-réciproque/
réduction surTryAPL en ligne!
la source
Python 2, 62 octets
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/c
etb/d
, la fraction suivante est(n*b+a)/(n*c+d)
.Par exemple, pour pi:
Nous pouvons voir que
15*22 + 3 = 333
,15*7 + 1 = 106
,1*333 + 22 = 355
,1*106 + 7 = 113
, etc.la source
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
la source
Haskell, 30 octets
Ajoute la mise à jour récursive chaque couche allant vers l' extérieur,
n/d
àh+(1/(n/d))
qui est égal àh+d/n
ou(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/1
laquelle est0
.la source
Python, 50 octets
Construit la fraction continue à partir de la fin de la liste en remontant, en mettant à jour à plusieurs reprises la fraction
n/d
sur le dernier élément enx
tant quen/d -> 1+1/(n/d) == (x*n+d)/n
.la source
Lisp commun, 54
Un repli un peu bavard:
Les tests
la source
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
la source
∘
) au lieu d'une fonctionx∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;)
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])
Javascript (ES6), 55 octets
Cas de test
la source
CJam ,
1816 octetsInterprète en ligne .
la source
05AB1E ,
1917 octetsExplication
Entrée prise comme une liste de nombres
Essayez-le en ligne!
la source
JavaScript (ES6), 44 octets
la source
Javascript (ES6), 50 octets
C'est grâce à la réponse d'Arnauld, avant de le voir j'étais coincé à 66 octets:
Exemple:
Appel:
f([1, 0, 1, 1, 2, 1, 1])
Sortie:
Array [ 19, 7 ]
la source
Perl 6 , 24 octets
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.… .nude
retourne le nu merator et de proposeur du Rat .{ … }
en faire un lambda de bloc nu avec un paramètre implicite@_
.Usage:
la source
Zephyr , 145 octets
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:
la source
Rubis, 34 octets
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
.la source
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+
.(a, b) => (a + 1/b)
.la source
APL (NARS), 15 + 1 caractères, 30 + 2 octets
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:
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 ...
la source