Sortie du nième nombre rationnel selon la séquence de Stern-Brocot

30

La séquence Stern-Brocot est une séquence de type Fibonnaci qui peut être construite comme suit:

  1. Initialisez la séquence avec s(1) = s(2) = 1
  2. Régler le compteur n = 1
  3. Ajouter s(n) + s(n+1)à la séquence
  4. Ajouter s(n+1)à la séquence
  5. Incrémenter n, revenir à l'étape 3

Cela équivaut à:

s (n) = \ begin {cases} 1 & \ textrm {if} n = 1 \ s (\ frac n 2) & \ textrm {if} n \ textrm {est pair} \ s (\ frac {n-1 } 2) + s (\ frac {n + 1} 2) & \ textrm {sinon} \ end {cases}

Entre autres propriétés, la séquence de Stern-Brocot peut être utilisée pour générer chaque nombre rationnel positif possible. Chaque nombre rationnel sera généré une seule fois, et il apparaîtra toujours dans ses termes les plus simples; par exemple, 1/3est le 4e nombre rationnel de la séquence, mais les nombres équivalents 2/6, 3/9etc. n'apparaîtront pas du tout.

Nous pouvons définir le nième nombre rationnel comme r(n) = s(n) / s(n+1), où s(n)est le nième nombre de Stern-Brocot, comme décrit ci-dessus.

Votre défi consiste à écrire un programme ou une fonction qui produira le nième nombre rationnel généré à l'aide de la séquence Stern-Brocot.

  • Les algorithmes décrits ci-dessus sont indexés 1; si votre entrée est indexée 0, veuillez l'indiquer dans votre réponse
  • Les algorithmes décrits sont à titre illustratif uniquement, la sortie peut être dérivée de la manière que vous souhaitez (autre que le codage en dur)
  • L'entrée peut être via STDIN, les paramètres de fonction ou tout autre mécanisme d'entrée raisonnable
  • Ouptut peut être vers STDOUT, console, valeur de retour de fonction ou tout autre flux de sortie raisonnable
  • La sortie doit être sous forme de chaîne dans le formulaire a/b, où aet bsont les entrées pertinentes dans la séquence Stern-Brocot. L'évaluation de la fraction avant la sortie n'est pas autorisée. Par exemple, pour l'entrée 12, la sortie doit être 2/5non 0.4.
  • Les failles standard sont interdites

C'est le , donc la réponse la plus courte en octets gagnera.

Cas de test

Les cas de test ici sont indexés 1.

n    r(n)
--  ------
1    1/1
2    1/2
3    2/1
4    1/3
5    3/2
6    2/3
7    3/1
8    1/4
9    4/3
10   3/5
11   5/2
12   2/5
13   5/3
14   3/4
15   4/1
16   1/5
17   5/4
18   4/7
19   7/3
20   3/8
50   7/12
100  7/19
1000 11/39

Entrée OEIS: A002487
Excellente vidéo Numberphile discutant de la séquence: Infinite Fractions

Sok
la source
La sortie peut-elle utiliser Trues au lieu de 1s?
Loovjo
1
@ Loovjo Non, ce True/2n'est pas une fraction valide (en ce qui me concerne). En passant, ce Truen'est pas toujours le cas 1- certains langages utilisent à la -1place pour éviter les erreurs potentielles lors de l'application d'opérateurs au niveau du bit. [citation nécessaire]
Sok
connexes
flawr
2
@Sok citation
mbomb007
1
@Sok mais en Python, Trueest équivalent 1et le True/2serait 1/2.
Leaky Nun

Réponses:

3

Gelée , 14 octets

3ẋḶŒpḄċ
’Ç”/⁸Ç

Essayez-le en ligne!

Ooh, on dirait que je peux battre la réponse acceptée par @Dennis, et dans la même langue. Cela fonctionne en utilisant une formule d'OEIS: le nombre de façons d'exprimer (le nombre moins 1) en hyperbinaire (c'est-à-dire binaire avec 0, 1, 2 comme chiffres). Contrairement à la plupart des programmes Jelly (qui fonctionnent soit comme un programme complet soit comme une fonction), celui-ci ne fonctionne que comme un programme complet (car il envoie une partie de la sortie à stdout et renvoie le reste; lorsqu'il est utilisé comme programme complet, la valeur de retour est envoyé à stdout implicitement, donc toute la sortie est au même endroit, mais cela ne fonctionnerait pas pour une soumission de fonction).

Cette version du programme est très inefficace. Vous pouvez créer un programme beaucoup plus rapide qui fonctionne pour toutes les entrées jusqu'à 2ⁿ en plaçant n juste après le sur la première ligne; le programme a des performances O ( n × 3ⁿ), donc garder n petit est assez important ici. Le programme tel qu'il est écrit définit n égal à l'entrée, ce qui est clairement assez grand, mais aussi clairement trop grand dans presque tous les cas (mais bon, il économise des octets).

Explication

Comme d'habitude dans mes explications Jelly, le texte entre accolades (par exemple {the input}) montre quelque chose qui est automatiquement rempli par Jelly en raison d'opérandes manquants dans le programme d'origine.

Fonction d'aide (calcule le n ème dénominateur, c'est-à-dire le n + 1 ème numérateur):

3ẋḶŒpḄċ
3ẋ       3, repeated a number of times equal to {the argument}
  Ḷ      Map 3 to [0, 1, 2]
   Œp    Take the cartesian product of that list
     Ḅ   Convert binary (or in this case hyperbinary) to a number
      ċ  Count number of occurrences of {the argument} in the resulting list

Les cinq premiers octets génèrent simplement tous les nombres hyperbinaires possibles jusqu'à une longueur donnée, par exemple avec l'entrée 3, la sortie de est [[0,1,2], [0,1,2], [0,1,2 ]] donc le produit cartésien est [[0,0,0], [0,0,1], [0,0,2], [0,1,0],…, [2,2,1], [2,2,2]]. multiplie simplement la dernière entrée par 1, l'avant-dernière entrée par 2, l'entrée antépénultième par 4, etc., puis ajoute; bien que cela soit normalement utilisé pour convertir le binaire en décimal, il peut très bien gérer le chiffre 2 et fonctionne donc également pour l'hyperbinaire. Ensuite, nous comptons le nombre de fois où l'entrée apparaît dans la liste résultante, afin d'obtenir une entrée appropriée dans la séquence. (Heureusement, le numérateur et le dénominateur suivent la même séquence).

Programme principal (demande le numérateur et le dénominateur et formate la sortie):

’Ç”/⁸Ç
’Ç      Helper function (Ç), run on {the input} minus 1 (‘)
  ”/    {Output that to stdout}; start again with the constant '/'
    ⁸Ç  {Output that to stdout}; then run the helper function (Ç) on the input (⁸)

D'une certaine manière, je continue d'écrire des programmes qui prennent presque autant d'octets pour gérer les E / S que pour résoudre le problème réel…


la source
Bon sang, vous ne plaisantiez pas sur le fait qu'il soit inefficace - sur TIO 12 prend 20 secondes pour terminer, et 13 fois complètement! Accepté, même si je ne peux pas vérifier tous les cas de test.
Sok
11

CJam (20 octets)

1_{_@_2$%2*-+}ri*'/\

Démo en ligne . Notez qu'il s'agit d'un index 0. Pour le rendre indexé 1, remplacez l'initiale 1_par T1.

Dissection

Cela utilise la caractérisation due à Moshe Newman qui

la fraction a(n+1)/a(n+2)peut être générée à partir de la fraction précédente a(n)/a(n+1) = xpar1/(2*floor(x) + 1 - x)

Si x = s/talors nous obtenons

  1 / (2 * floor(s/t) + 1 - s/t)
= t / (2 * t * floor(s/t) + t - s)
= t / (2 * (s - s%t) + t - s)
= t / (s + t - 2 * (s % t))

Maintenant, si nous supposons que set tsont coprime alors

  gcd(t, s + t - 2 * (s % t))
= gcd(t, s - 2 * (s % t))
= gcd(t, -(s % t))
= 1

Fonctionne donc a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))parfaitement.

1_           e# s=1, t=1
{            e# Loop...
  _@_2$%2*-+ e#   s, t = t, s + t - 2 * (s % t)
}
ri*          e# ...n times
'/\          e# Separate s and t with a /
Peter Taylor
la source
J'adore la méthodologie ici, réponse géniale!
Sok
Si vous faites défiler plus bas l'entrée OEIS, vous constaterez que Mike Stay a déjà soumis cette formule.
Neil
11

Haskell, 78 77 65 58 octets

Voler sans vergogne l'approche optimisée nous donne:

(s#t)0=show s++'/':show t
(s#t)n=t#(s+t-2*mod s t)$n-1
1#1

Merci à @nimi d'avoir joué quelques octets en utilisant une fonction infixe!

(Toujours) utilise une indexation basée sur 0.


L'ancienne approche:

s=(!!)(1:1:f 0)
f n=s n+s(n+1):s(n+1):(f$n+1)
r n=show(s n)++'/':(show.s$n+1)

Merde le format de sortie ... Et les opérateurs d'indexation. EDIT: Et la priorité.

Fait amusant: si les listes hétérogènes étaient une chose, la dernière ligne pourrait être:

r n=show>>=[s!!n,'/',s!!(n+1)]
ThreeFx
la source
Utiliser un garde pour lier s!!ndevrait être un octet plus court:f n|x<-s!!n=x:x+x+1:f$n+1
Laikoni
@Laikoni s!!n+1ne l'est pas (s!!n)+1mais s!!(n+1)c'est pourquoi je ne peux pas faire ça: /
ThreeFx
En fait, cela aurait dû être évident. C'est juste ... tellement s!!nlà-dedans!
Laikoni du
1
Vous pouvez utiliser ++'/':(show.s$n+1)in rpour enregistrer un octet.
nimi
1
Passer à une fonction infixe: (s#t)0=show..., (s#t)n=t#(s+t-2*mod s t)$n-1, r=1#1. Vous pouvez même omettre r, c'est-à-dire que la dernière ligne est juste 1#1.
nimi
6

Gelée , 16 octets

L‘Hị⁸Sṭ
1Ç¡ṫ-j”/

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

Comment ça marche

1Ç¡ṫ-j”/  Main link. Argument: n

1         Set the return value to 1.
 Ç¡       Apply the helper link n times.
   ṫ-     Tail -1; extract the last two items.
     j”/  Join, separating by a slash.


L‘Hị⁸Sṭ   Helper link. Argument: A (array)

L         Get the length of A.
 ‘        Add 1 to compute the next index.
  H       Halve.
   ị⁸     Retrieve the item(s) of A at those indices.
          If the index in non-integer, ị floors and ceils the index, then retrieves
          the items at both indices.
    S     Compute the sum of the retrieved item(s).
     ṭ    Tack; append the result to A.
Dennis
la source
5

05AB1E , 34 33 25 23 octets

XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý

Explication

XX‚                        # push [1,1]
   ¹G           }          # input-1 times do
     Â                     # bifurcate
      2£                   # take first 2 elements of reversed list
        DO¸                # duplicate and sum 1st copy, s(n)+s(n+1)
           s¦              # cut away the first element of 2nd copy, s(n)
             ìì            # prepend both to list
               ¨           # remove last item in list
                 R2£       # reverse and take the first 2 elements
                    '/ý    # format output
                           # implicitly print

Essayez-le en ligne

Enregistré 2 octets grâce à Adnan.

Emigna
la source
Est-ce que cela fonctionne aussi?: XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý.
Adnan
@Adnan En effet. J'ai oublié que l' ýon peut formater une liste. Agréable.
Emigna
4

MATL , 20 octets

FT+"@:qtPXnosV47]xhh

Celui-ci utilise la caractérisation en termes de coefficients binomiaux donnée dans la page OEIS .

L'algorithme fonctionne en théorie pour tous les nombres, mais en pratique, il est limité par la précision numérique de MATL, et donc il ne fonctionne pas pour les entrées de grande taille. Le résultat est précis pour des entrées jusqu'à 20au moins.

Essayez-le en ligne!

Explication

FT+      % Implicitly take input n. Add [0 1] element-wise. Gives [n n+1]
"        % For each k in [n n+1]
  @:q    %   Push range [0 1 ... k-1]
  tP     %   Duplicate and flip: push [k-1 ... 1 0]
  Xn     %   Binomial coefficient, element-wise. Gives an array
  os     %   Number of odd entries in that array
  V      %   Convert from number to string
  47     %   Push 47, which is ASCII for '\'
]        % End for each
x        % Remove second 47
hh       % Concatenate horizontally twice. Automatically transforms 47 into '\'
         % Implicitly display
Luis Mendo
la source
4

Python 2, 85 81 octets

x,s=input(),[1,1]
for i in range(x):s+=s[i]+s[i+1],s[i+1]
print`s[x-1]`+"/"+`s[x]`

Cette soumission est indexée 1.

En utilisant une fonction récursive, 85 octets:

s=lambda x:int(x<1)or x%2 and s(x/2)or s(-~x/2)+s(~-x/2)
lambda x:`s(x)`+"/"+`s(x+1)`

Si une sortie comme True/2est acceptable, en voici une à 81 octets:

s=lambda x:x<1 or x%2 and s(x/2)or s(-~x/2)+s(~-x/2)
lambda x:`s(x)`+"/"+`s(x+1)`
Loovjo
la source
3

JavaScript (ES6), 43 octets

f=(i,n=0,d=1)=>i?f(i-1,d,n+d-n%d*2):n+'/'+d

1 indexé; remplacer par n=1pour 0 indexé. La page OEIS liée a une relation de récurrence utile pour chaque terme par rapport aux deux termes précédents; Je l'ai simplement réinterprété comme une récurrence pour chaque fraction en termes de la fraction précédente. Malheureusement, nous n'avons pas de TeX en ligne, vous n'aurez donc qu'à le coller sur un autre site pour découvrir comment ces formats:

unebbune+b-2(unemodb)
Neil
la source
3

Python 2, 66 octets

f=lambda n:1/n or f(n/2)+n%2*f(-~n/2)
lambda n:`f(n)`+'/'+`f(n+1)`

Utilise la formule récursive.

xnor
la source
3

C (GCC), 79 octets

Utilise l'indexation basée sur 0.

s(n){return!n?:n%2?s(n/2):s(-~n/2)+s(~-n/2);}r(n){printf("%d/%d",s(n),s(n+1));}

Ideone

betseg
la source
1
x?:yest une extension gcc.
rici
3

En fait, 18 octets

11,`│;a%τ@-+`nk'/j

Essayez-le en ligne!

Cette solution utilise la formule de Peter et est également indexée sur 0. Merci à Leaky Nun pour un octet.

Explication:

11,`│;a%τ@-+`nk'/j
11                  push 1, 1
  ,`│;a%τ@-+`n      do the following n times (where n is the input):
                      stack: [t s]
    │                 duplicate the entire stack ([t s t s])
     ;                dupe t ([t t s t s])
      a               invert the stack ([s t s t t])
       %              s % t ([s%t s t t])
        τ             multiply by 2 ([2*(s%t) s t t])
         @-           subtract from s ([s-2*(s%t) s t])
           +          add to t ([t+s-2*(s%t) t])
                      in effect, this is s,t = t,s+t-2*(s%t)
              k'/j  push as a list, join with "/"
Mego
la source
@LeakyNun Je vais suspendre cette amélioration jusqu'à ce qu'il y ait des éclaircissements du PO.
Mego
2

MATL , 32 30 octets

1i:"tt@TF-)sw@)v]tGq)V47bG)Vhh

Cela utilise une approche directe: génère suffisamment de membres de la séquence, sélectionne les deux membres souhaités et formate la sortie.

Essayez-le en ligne!

Luis Mendo
la source
2

R, 93 octets

f=function(n)ifelse(n<3,1,ifelse(n%%2,f(n/2-1/2)+f(n/2+1/2),f(n/2)))
g=function(n)f(n)/f(n+1)

Littéralement la mise en œuvre la plus simple. Travailler un peu au golf.

user5957401
la source
2

m4, 131 octets

define(s,`ifelse($1,1,1,eval($1%2),0,`s(eval($1/2))',`eval(s(eval(($1-1)/2))+s(eval(($1+1)/2)))')')define(r,`s($1)/s(eval($1+1))')

Définit une macro rtelle qu'elle r(n)évalue selon la spécification. Pas vraiment joué au golf, je viens de coder la formule.

Programme homme
la source
2

Rubis, 49 octets

Il est indexé sur 0 et utilise la formule de Peter Taylor. Suggestions de golf bienvenues.

->n{s=t=1;n.times{s,t=t,s+t-2*(s%t)};"#{s}/#{t}"}
Sherlock9
la source
1

> <> , 34 + 2 = 36 octets

Après avoir vu l'excellente réponse de Peter Taylor, j'ai réécrit ma réponse de test (qui était un embarrassant de 82 octets, utilisant une récursion très maladroite).

&01\$n"/"on;
&?!\:@}:{:@+@%2*-&1-:

Il s'attend à ce que l'entrée soit présente sur la pile, donc +2 octets pour l' -vindicateur. Essayez-le en ligne!

Sok
la source
1

Octave, 90 octets

function f(i)S=[1 1];for(j=1:i/2)S=[S S(j)+S(j+1) (j+1)];end;printf("%d/%d",S(i),S(i+1));end
dcsohl
la source
1

C #, 91 90 octets

n=>{Func<int,int>s=_=>_;s=m=>1==m?m:s(m/2)+(0==m%2?0:s(m/2+1));return$"{s(n)}/{s(n+1)}";};

S'exécute vers Func<int, string>. Il s'agit de l'implémentation récursive.

Non golfé:

n => 
{
    Func<int,int> s = _ => _; // s needs to be set to use recursively. _=>_ is the same byte count as null and looks cooler.
    s = m =>
        1 == m ? m               // s(1) = 1
        : s(m/2) + (0 == m%2 ? 0 // s(m) = s(m/2) for even
        : s(m/2+1));             // s(m) = s(m/2) + s(m/2+1) for odd
    return $"{s(n)}/{s(n+1)}";
};

Édition: -1 octet. Il s'avère que C # n'a pas besoin d'espace entre returnet $pour les chaînes interpolées.

Lait
la source
1

J, 29 octets

([,'/',])&":&([:+/2|]!&i.-)>:

Usage

Les grandes valeurs de n nécessitent un suffixe xqui indique l'utilisation d'entiers étendus.

   f =: ([,'/',])&":&([:+/2|]!&i.-)>:
   f 1
1/1
   f 10
3/5
   f 50
7/12
   f 100x
7/19
   f 1000x
11/39
miles
la source
100compte comme une «grande valeur»?
dcsohl
1
@dcsohl Dans cette méthode, les coefficients binomiaux sont calculés et pour n = 100, le plus grand calculé est C (72, 28) = 75553695443676829680> 2 ^ 64 et nécessitera des entiers étendus pour éviter les valeurs à virgule flottante.
miles
1

Mathematica, 108 106 101 octets

(s={1,1};n=1;a=AppendTo;t=ToString;Do[a[s,s[[n]]+s[[++n]]];a[s,s[[n]]],#];t@s[[n-1]]<>"/"<>t@s[[n]])&
engourdi
la source
1

R , 84 octets

function(n,K=c(1,1)){for(i in 1:n)K=c(K,K[i]+K[i+1],K[i+1])
paste0(K[i],"/",K[i+1])}

Essayez-le en ligne!

L' ancienne implémentation R ne suit pas les spécifications, renvoyant un point flottant plutôt qu'une chaîne, alors en voici une qui le fait.

Giuseppe
la source