Você pode criar uma lista de todos os racionais 0 <r ≤ 1 listando-os ordenados primeiro pelo denominador e depois pelo numerador:
1 1 1 2 1 3 1 2 3 4 1 5 1 2 3 4 5
- - - - - - - - - - - - - - - - -
1 2 3 3 4 4 5 5 5 5 6 6 7 7 7 7 7
Observe que pulamos qualquer número racional que já ocorreu antes. Por exemplo, 2/4 é ignorado porque já listamos 1/2.
Neste desafio, estamos interessados apenas nos numeradores. Observando a lista acima, escreva uma função ou programa usando um número inteiro positivo n que retorne o enésimo numerador da lista.
Casos de teste:
1 -> 1
2 -> 1
3 -> 1
4 -> 2
5 -> 1
6 -> 3
7 -> 1
8 -> 2
9 -> 3
50 -> 4
80 -> 15
(0,1]
Respostas:
MATL ,
1713 bytesExperimente online! Ou verifique todos os casos de teste .
O tamanho da entrada pode ser limitado pela precisão do ponto flutuante. Todos os casos de teste fornecem o resultado correto.
Explicação
Isso gera todas as frações
k/m
comk
,m
em[1 2 ...n]
, como uma matrizn
×n
. A linha indica o numerador e a coluna indica o denominador. Na verdade, a entrada da matriz contém a fração inversam/k
, em vez dek/m
, mas isso é irrelevante e pode ser ignorada no restante da explicação.As entradas da matriz são consideradas implicitamente classificadas na ordem principal da coluna. Nesse caso, isso corresponde à ordem necessária: denominador e numerador.
Três tipos de entradas precisam ser desconsiderados nessa matriz:
k/m
,k>m
que têm o mesmo valor como uma entrada anterior (por exemplo,2/4
não é considerado porque é a mesma que1/2
)k/k
,k>1
. Entradas que possuem um numerador que excede o denominadork/m
,k<m
(estes não são parte do problema).A desconsideração de entradas é feita com uma
unique
função, que remove de forma estável os valores duplicados e gera os índices das entradas sobreviventes. Com isso, as entradas do tipo 1 acima são removidas automaticamente. Para lidar com os tipos 2 e 3, as entradas da matriz na diagonal e abaixo são definidas como0
. Dessa forma, todas as zero entradas serão removidas, exceto a primeira (correspondente à fração válida1/1
).Considere a entrada
4
como um exemplo.fonte
Geléia ,
119 bytesExperimente online! ou verifique todos os casos de teste .
Como funciona
fonte
Mathematica, 53 bytes
fonte
Haskell, 40 bytes
Uma função anônima. Bem simples: usa uma compreensão de lista para gerar uma lista infinita, fazendo um loop sobre todos os numeradores
n
e denominadores relativamente primosd
. Para converter o índice zero em um indexado, adicionamos um a0
, que recebe4
bytes.fonte
n<-[0..d]
adiciona o zero de maneira mais curta e salva os 4 bytesPitão, 13 bytes
Experimente online. Suíte de teste.
fonte
Pitão, 11 bytes
Experimente online: Demonstração
Explicação:
fonte
Na verdade , 15 bytes
Esta resposta é baseada na resposta de Dennis 'Jelly . Uso
HN
no final para evitar problemas com a indexação 0 e a necessidade de diminuir e trocar no início ou no final.H
obtém os primeirosn
membros da lista de numeradores que resultam eN
obtém o último membro dessa seleção, ou seja, on
numerador, tudo sem mexer nas operações de pilha. Sugestões de golfe são bem-vindas. Experimente online!Ungolfing
fonte
Python,
111110 bytesA fração é representada por
x/y
. O argumenton
é decrementado quando uma nova fração de ajuste é encontrada (as verificaçõesgcd
fromfractions
podem ser reduzidas). Em cada iteração do loop,x
é incrementado; em seguida, sex>=y
uma nova série de fraçõesy+1
for iniciada,>
por causa do "caso especial"(x,y)=(2,1)
, será direcionado parax>y
.Estou certo de que isso pode ser mais praticado, mas estou perdendo onde eu poderia melhorá-lo.Encontrei.Link para código e casos de teste
fonte
JavaScript (ES6), 95 bytes
Funciona através da geração de todas as
n²
fracções com numerador e denominador de1
an
e filtrando aqueles maior do que1
ou previamente visto, em seguida, tendo on
th.fonte
Perl, 82 + 2 (
-pl
sinalizador) = 84 bytesUngolfed:
fonte
JavaScript (ES6), 76
Menos golfe
Teste
fonte
Clojure, 85 bytes
Usa a compreensão da lista para gerar uma lista de todos os racionais, depois o filtra para obter apenas os distintos. Pega o
nth
item da lista e retorna seu numerador. Também é necessária uma condição separada para o primeiro elemento, porque o Clojure não pode usar o numerador de um número inteiro. (por qualquer motivo, considerando que um número inteiro não seja Rational - https://goo.gl/XETLo2 )Veja on-line - https://ideone.com/8gNZEB
fonte