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 à:

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 code-golf , 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

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…

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 /

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)]

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.

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.

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

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)`

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:

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.

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

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 "/"

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!

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.

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.

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}"}

> <> , 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!

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

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.

Python 2, 59 octets

s,t=1,1;exec"s,t=t,s+t-2*(s%t);"*input();print'%d/%d'%(s,t)

Utilise la formule de Peter et est également indexé sur 0.

Essayez-le en ligne

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

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]])&

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.