Emita o enésimo número racional de acordo com a sequência Stern-Brocot

30

A sequência Stern-Brocot é uma sequência do tipo Fibonnaci que pode ser construída da seguinte maneira:

  1. Inicialize a sequência com s(1) = s(2) = 1
  2. Definir contador n = 1
  3. Anexar s(n) + s(n+1)à sequência
  4. Anexar s(n+1)à sequência
  5. Incremento n, volte para a etapa 3

Isso é equivalente a:

s (n) = \ begin {cases} 1 & \ textrm {if} n = 1 \ s (\ frac n 2) & \ textrm {if} n \ textrm {é par} \ s (\ frac {n-1 } 2) + s (\ frac {n + 1} 2) & \ textrm {caso contrário} \ end {cases}

Entre outras propriedades, a sequência Stern-Brocot pode ser usada para gerar todo número racional positivo possível. Todo número racional será gerado exatamente uma vez e sempre aparecerá nos seus termos mais simples; por exemplo, 1/3é o número 4 racional na sequência, mas os números equivalentes 2/6, 3/9etc não aparece de todo.

Podemos definir o enésimo número racional como r(n) = s(n) / s(n+1), onde s(n)é o enésimo número Stern-Brocot, conforme descrito acima.

Seu desafio é escrever um programa ou função que produza o enésimo número racional gerado usando a sequência Stern-Brocot.

  • Os algoritmos descritos acima são indexados em 1; se sua entrada for 0 indexada, indique na sua resposta
  • Os algoritmos descritos são apenas para fins ilustrativos, a saída pode ser derivada da maneira que você desejar (exceto a codificação)
  • A entrada pode ser via STDIN, parâmetros de função ou qualquer outro mecanismo de entrada razoável
  • Ouptut pode ser STDOUT, console, valor de retorno da função ou qualquer outro fluxo de saída razoável
  • A saída deve ser como uma sequência no formulário a/b, onde ae bsão as entradas relevantes na sequência Stern-Brocot. Avaliar a fração antes da saída não é permitido. Por exemplo, para entrada 12, a saída deve ser 2/5, não 0.4.
  • As brechas padrão não são permitidas

Isso é , então a resposta mais curta em bytes vencerá.

Casos de teste

Os casos de teste aqui são indexados 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

Entrada OEIS: A002487
Excelente vídeo Numberphile discutindo a sequência: Frações infinitas

Sok
fonte
A saída pode usar Trues em vez de 1s?
Loovjo 18/08/16
1
@ Loovjo Não, True/2não é uma fração válida (no que me diz respeito). Como um aparte, Truenem sempre é 1- alguns idiomas usam -1para evitar possíveis erros ao aplicar operadores bit a bit. [citação necessário]
Sok
relacionado
flawr 18/08/16
2
@Sok citation
mbomb007
1
@ Sok, mas em Python, Trueé equivalente 1e True/2seria 1/2.
Leaky Nun

Respostas:

3

Gelatina , 14 bytes

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

Experimente online!

Ooh, parece que posso vencer a resposta aceita por @Dennis, e no mesmo idioma. Isso funciona usando uma fórmula do OEIS: o número de maneiras de expressar (o número menos 1) em hiperbinário (ou seja, binário com 0, 1, 2 como dígitos). Ao contrário da maioria dos programas Jelly (que funcionam como um programa completo ou como uma função), este funciona apenas como um programa completo (porque envia parte da saída para o stdout e retorna o restante; quando usado como um programa completo, o valor de retorno é enviado para stdout implicitamente, para que toda a saída esteja no mesmo lugar, mas isso não funcionaria para o envio de uma função).

Esta versão do programa é muito ineficiente. Você pode criar um programa muito mais rápido que funcione para todas as entradas de até 2ⁿ, colocando n logo após o na primeira linha; o programa tem desempenho O ( n × 3ⁿ), portanto, manter n pequeno é bastante importante aqui. O programa, como gravado, define n igual à entrada, que é claramente grande o suficiente, mas também claramente grande demais em quase todos os casos (mas ei, ele salva bytes).

Explicação

Como de costume nas minhas explicações sobre o Jelly, o texto entre chaves (por exemplo {the input}) mostra algo que foi preenchido automaticamente pelo Jelly devido à falta de operandos no programa original.

Função auxiliar (calcula o n th denominador, ou seja, o n + numerador 1Te):

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

Os cinco primeiros bytes estão basicamente gerando todos os números hiperbinários possíveis até um determinado comprimento, por exemplo, com a entrada 3, a saída de é [[0,1,2], [0,1,2], [0,1,2 ]] para que o produto cartesiano seja [[0,0,0], [0,0,1], [0,0,2], [0,1,0],…, [2,2,1], [2,2,2]] basicamente apenas multiplica a última entrada por 1, a penúltima entrada por 2, a entrada antepenúltima por 4, etc. e depois adiciona; embora isso seja normalmente usado para converter binário em decimal, ele pode lidar com o dígito 2 muito bem e, portanto, funciona também com o hiperbinário. Depois, contamos o número de vezes que a entrada aparece na lista resultante, para obter uma entrada apropriada na sequência. (Felizmente, o numerador e o denominador seguem a mesma sequência).

Programa principal (solicita o numerador e o denominador e formata a saída):

’Ç”/⁸Ç
’Ç      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 (⁸)

De alguma forma, continuo escrevendo programas que levam quase tantos bytes para lidar com E / S quanto para resolver o problema real…


fonte
Que pena, você não estava brincando sobre isso ser ineficiente - no TIO 12 leva 20s para ser concluído e 13 vezes fora completamente! Aceito, embora não possa verificar todos os casos de teste.
Sok
11

CJam (20 bytes)

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

Demonstração online . Observe que esse índice é 0. Para torná-lo indexado em 1, substitua a inicial 1_por T1.

Dissecação

Isso usa a caracterização devido a Moshe Newman que

a fração a(n+1)/a(n+2)pode ser gerada a partir da fração anterior a(n)/a(n+1) = xpor1/(2*floor(x) + 1 - x)

Se x = s/tentão temos

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

Agora, se assumirmos isso se tsomos coprimes, então

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

Então a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))funciona perfeitamente.

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
fonte
Adoro a metodologia aqui, resposta incrível!
Sok
Se você rolar mais abaixo na entrada OEIS, verá que Mike Stay já enviou essa fórmula.
Neil
11

Haskell, 78 77 65 58 bytes

Roubar descaradamente a abordagem otimizada nos dá:

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

Obrigado ao @nimi por jogar alguns bytes usando uma função infix!

(Ainda) usa indexação baseada em 0.


A abordagem antiga:

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)

Maldito formato de saída ... E operadores de indexação. EDIT: E precedência.

Curiosidade: se as listas heterogêneas existissem, a última linha poderia ser:

r n=show>>=[s!!n,'/',s!!(n+1)]
ThreeFx
fonte
Usando um guarda para ligamento s!!ndeve ser um byte mais curto:f n|x<-s!!n=x:x+x+1:f$n+1
Laikoni
@Laikoni s!!n+1não é, (s!!n)+1mas s!!(n+1)é por isso que não posso fazer isso: /
ThreeFx 18/08
Na verdade, isso deveria ter sido óbvio. É só ... tantos s!!nlá!
Laikoni 18/08/16
1
Você pode usar ++'/':(show.s$n+1)em rsalvar um byte.
nimi
1
Mudar para um uma função infix: (s#t)0=show..., (s#t)n=t#(s+t-2*mod s t)$n-1, r=1#1. Você pode até omitir r, ou seja, a última linha é justa 1#1.
nimi
6

Gelatina , 16 bytes

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

Experimente online! ou verifique todos os casos de teste .

Como funciona

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
fonte
5

05AB1E , 34 33 25 23 bytes

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

Explicação

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

Experimente online

Economizou 2 bytes graças a Adnan.

Emigna
fonte
Isso também funciona ?: XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý.
Adnan
@Adnan De fato. Eu esqueci que ýpode formatar uma lista. Agradável.
Emigna
4

MATL , 20 bytes

FT+"@:qtPXnosV47]xhh

Isso usa a caracterização em termos de coeficientes binomiais fornecidos na página OEIS .

O algoritmo funciona na teoria para todos os números, mas na prática é limitado pela precisão numérica do MATL e, portanto, não funciona para entradas grandes. O resultado é preciso para entradas de até 20pelo menos.

Experimente online!

Explicação

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
fonte
4

Python 2, 85 81 bytes

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

Este envio é indexado em 1.

Usando uma função recursiva, 85 bytes:

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

Se uma saída como True/2for aceitável, eis uma em 81 bytes:

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
fonte
3

JavaScript (ES6), 43 bytes

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

Indexado 1; mude para n=1para 0-indexado. A página OEIS vinculada tem uma relação de recorrência útil para cada termo nos termos dos dois termos anteriores; Apenas o reinterpretei como uma recorrência para cada fração em termos da fração anterior. Infelizmente, não temos o TeX embutido, então basta colá-lo em outro site para descobrir como é o formato:

umabbuma+b-2(umamodb)
Neil
fonte
3

Python 2, 66 bytes

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

Usa a fórmula recursiva.

xnor
fonte
3

C (GCC), 79 bytes

Usa indexação baseada em 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
fonte
1
x?:yé uma extensão do gcc.
rici 20/08/16
3

Na verdade, 18 bytes

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

Experimente online!

Essa solução usa a fórmula de Peter e também é indexada em 0. Agradecimentos a Leaky Nun por um byte.

Explicação:

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
fonte
Um byte controverso fora
Freira Furada
@LeakyNun Vou adiar essa melhoria até que haja esclarecimentos do OP.
Mego
2

MATL , 32 30 bytes

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

Isso usa uma abordagem direta: gera membros suficientes da sequência, escolhe os dois desejados e formata a saída.

Experimente online!

Luis Mendo
fonte
2

R, 93 bytes

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)

Literalmente, a implementação mais simples. Trabalhando um pouco no golfe.

user5957401
fonte
2

m4, 131 bytes

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

Define uma macro rque é r(n)avaliada de acordo com as especificações. Não é realmente um jogo de golfe, apenas codifiquei a fórmula.

Homem do programa
fonte
2

Ruby, 49 bytes

Este é o índice 0 e usa a fórmula de Peter Taylor. Sugestões de golfe são bem-vindas.

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

> <> , 34 + 2 = 36 bytes

Depois de ver a excelente resposta de Peter Taylor, reescrevi minha resposta de teste (que era um embaraçoso 82 bytes, usando recursão muito desajeitada).

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

Ele espera que a entrada esteja presente na pilha, portanto, +2 bytes para o -vsinalizador. Experimente online!

Sok
fonte
1

Oitava, 90 bytes

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
fonte
1

C #, 91 90 bytes

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

Transmite para Func<int, string> . Esta é a implementação recursiva.

Ungolfed:

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

Editar: -1 byte. Acontece que o C # não precisa de um espaço entre returne $para seqüências de caracteres interpoladas.

leite
fonte
1

J, 29 bytes

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

Uso

Valores grandes de n requerem um sufixo, xque indica o uso de números inteiros estendidos.

   f =: ([,'/',])&":&([:+/2|]!&i.-)>:
   f 1
1/1
   f 10
3/5
   f 50
7/12
   f 100x
7/19
   f 1000x
11/39
milhas
fonte
100conta como um "grande valor"?
dcsohl
1
@dcsohl Nesse método, os coeficientes binomiais são calculados e, para n = 100, o maior deles é C (72, 28) = 75553695443676829680> 2 ^ 64 e exigirá números inteiros estendidos para evitar valores de ponto flutuante.
miles
1

Mathematica, 108 106 101 bytes

(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]])&
numbermaniac
fonte
1

R , 84 bytes

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

Experimente online!

A implementação R mais antiga não segue as especificações, retornando um ponto flutuante em vez de uma string, então aqui está uma que segue.

Giuseppe
fonte