A sequência Stern-Brocot é uma sequência do tipo Fibonnaci que pode ser construída da seguinte maneira:
- Inicialize a sequência com
s(1) = s(2) = 1
- Definir contador
n = 1
- Anexar
s(n) + s(n+1)
à sequência - Anexar
s(n+1)
à sequência - Incremento
n
, volte para a etapa 3
Isso é equivalente a:
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/9
etc 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
, ondea
eb
são as entradas relevantes na sequência Stern-Brocot. Avaliar a fração antes da saída não é permitido. Por exemplo, para entrada12
, a saída deve ser2/5
, não0.4
. - As brechas padrão não são permitidas
Isso é código-golfe , 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
True
s em vez de1
s?True/2
não é uma fração válida (no que me diz respeito). Como um aparte,True
nem sempre é1
- alguns idiomas usam-1
para evitar possíveis erros ao aplicar operadores bit a bit. [citação necessário]True
é equivalente1
eTrue/2
seria1/2
.Respostas:
Gelatina , 14 bytes
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):
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):
De alguma forma, continuo escrevendo programas que levam quase tantos bytes para lidar com E / S quanto para resolver o problema real…
fonte
CJam (20 bytes)
Demonstração online . Observe que esse índice é 0. Para torná-lo indexado em 1, substitua a inicial
1_
porT1
.Dissecação
Isso usa a caracterização devido a Moshe Newman que
Se
x = s/t
então temosAgora, se assumirmos isso
s
et
somos coprimes, entãoEntão
a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))
funciona perfeitamente.fonte
Haskell,
78 77 6558 bytesRoubar descaradamente a abordagem otimizada nos dá:
Obrigado ao @nimi por jogar alguns bytes usando uma função infix!
(Ainda) usa indexação baseada em 0.
A abordagem antiga:
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:
fonte
s!!n
deve ser um byte mais curto:f n|x<-s!!n=x:x+x+1:f$n+1
s!!n+1
não é,(s!!n)+1
mass!!(n+1)
é por isso que não posso fazer isso: /s!!n
lá!++'/':(show.s$n+1)
emr
salvar um byte.(s#t)0=show...
,(s#t)n=t#(s+t-2*mod s t)$n-1
,r=1#1
. Você pode até omitirr
, ou seja, a última linha é justa1#1
.Gelatina , 16 bytes
Experimente online! ou verifique todos os casos de teste .
Como funciona
fonte
05AB1E ,
34332523 bytesExplicação
Experimente online
Economizou 2 bytes graças a Adnan.
fonte
XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý
.ý
pode formatar uma lista. Agradável.MATL , 20 bytes
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é
20
pelo menos.Experimente online!
Explicação
fonte
Python 2,
8581 bytesEste envio é indexado em 1.
Usando uma função recursiva, 85 bytes:
Se uma saída como
True/2
for aceitável, eis uma em 81 bytes:fonte
JavaScript (ES6), 43 bytes
Indexado 1; mude para
n=1
para 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:fonte
Python 2, 66 bytes
Usa a fórmula recursiva.
fonte
C (GCC), 79 bytes
Usa indexação baseada em 0.
Ideone
fonte
x?:y
é uma extensão do gcc.Na verdade, 18 bytes
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:
fonte
MATL ,
3230 bytesIsso usa uma abordagem direta: gera membros suficientes da sequência, escolhe os dois desejados e formata a saída.
Experimente online!
fonte
R, 93 bytes
Literalmente, a implementação mais simples. Trabalhando um pouco no golfe.
fonte
m4, 131 bytes
Define uma macro
r
que ér(n)
avaliada de acordo com as especificações. Não é realmente um jogo de golfe, apenas codifiquei a fórmula.fonte
Ruby, 49 bytes
Este é o índice 0 e usa a fórmula de Peter Taylor. Sugestões de golfe são bem-vindas.
fonte
> <> , 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).
Ele espera que a entrada esteja presente na pilha, portanto, +2 bytes para o
-v
sinalizador. Experimente online!fonte
Oitava, 90 bytes
fonte
C #,
9190 bytesTransmite para
Func<int, string>
. Esta é a implementação recursiva.Ungolfed:
Editar: -1 byte. Acontece que o C # não precisa de um espaço entre
return
e$
para seqüências de caracteres interpoladas.fonte
Python 2, 59 bytes
Usa a fórmula de Peter e é igualmente indexado a 0.
Experimente online
fonte
J, 29 bytes
Uso
Valores grandes de n requerem um sufixo,
x
que indica o uso de números inteiros estendidos.fonte
100
conta como um "grande valor"?Mathematica,
108106101 bytesfonte
R , 84 bytes
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.
fonte