Função de contagem racional

11

Crie uma função que use um número natural (começando com 0 inclusive) e retorne um par de números inteiros positivos, que são o numerador e o denominador, respectivamente. Use o deslocamento diagonal. Os números contados anteriormente devem ser ignorados. (você pode memorizar o conjunto de valores ignorados)

Diagrama:

insira a descrição da imagem aqui

Vermelho são valores ignorados

Valores:

  • f (0) = 1, 1
  • f (1) = 2, 1
  • f (2) = 1, 2
  • f (3) = 1, 3
  • f (4) = 3, 1 (observe o pular)
  • f (5) = 4, 1
  • f (6) = 3, 2
  • f (7) = 2, 3
  • f (8) = 1, 4
  • f (9) = 1, 5
  • f (10) = 5, 1 (observe o pular)

Você pode usar a estrutura de dados do Rational e suas operações, se existirem. O menor código vence.

Ming-Tang
fonte
11
O número de números racionais contados em cada diagonal é a função totiente da soma comum dessa diagonal.
Leaky Nun
Sei que esse desafio é antigo, mas existe uma resposta mais curta que a aceita, portanto, você pode aceitar novamente.
Esolanging Fruit

Respostas:

4

J, 41 36 caracteres

Pega um número inteiro e retorna um vetor que compreende dois números inteiros. Minha primeira solução que não é totalmente tácita nem totalmente explícita.

{3 :'~.;<`(<@|.)/.(,%+.)"0/~1+i.1+y'

Aqui está a solução com espaços inseridos onde apropriado:

{ 3 : '~. ; <`(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'

Uma explicação:

  1. x (, % +.) y–Um vetor de comprimento 2 que representa a fração com numerador xe denominador yreduzido ao menor denominador
  2. 1 + i. 1 + y–Um vetor de números inteiros de 1ay + 1
  3. (, % +.)"0/~ 1 + i. 1 + y–Uma matriz de todas as frações reduzidas com denominador e numerador não reduzidos no intervalo de 1até y + 1.
  4. <`(<@|.)/. y–Uma matriz das diagonais oblíquas da matriz y, uma com a outra na diagonal
  5. ~. ; y–Um conjunto de diagonais colapsado em um vetor de elementos com duplicatas removidas
  6. x { y–O item na posição xemy
  7. (u v) y–O mesmo que y u v y. Nesse caso de uso específico, ué {e vé3 : '~. ; <`(<@|.)/. (, % +.)"0/~ 1 + i. 1 + y'
FUZxxl
fonte
11
30 bytes
FrownyFrog
8

Haskell, 78 caracteres

q(r,f)=[(r-b,b)|b<-f[1..r-1],r`gcd`b==1]
d=reverse:id:d
f=((zip[2..]d>>=q)!!)

Exemplo de execução:

> map f [0..10]
[(1,1),(2,1),(1,2),(1,3),(3,1),(4,1),(3,2),(2,3),(1,4),(1,5),(5,1)]
> f 100
(17,1)
> f 1000
(3,55)

  • Edit: (100 → 87) bobo me, basta testar o gcd é suficiente!
  • Editar: (87 → 85) truque inteligente com cyclee funções para alternar a ordem das linhas
  • Editar: (85 → 82) substitua cyclepela lista infinita criada à mãod
  • Edit: (82 → 78) gcdidentidade aplicada , conforme sugerido por Matías
MtnViewMark
fonte
Por definição, gcd (r-b) b == gcd r bvocê pode cortar mais quatro caracteres.
Matías Giovannini
3

Python, 144 caracteres

def F(i):
 r,d,z=[1],1,[]
 while z[:i]==z:z+=[(x,y)for x,y in zip(r[::d],r[::-d])if all(x%j+y%j for j in r[1:])];d=-d;r+=[r[-1]+1]
 return z[i]
Keith Randall
fonte
2

Ruby 1.9, 109 106

F=->n{x=y=d=1
e=0
n.times{(x+=d).gcd(y+=e)>1&&redo
x<2?d<0?d=0:(d,e=1,-1):y<2?e<0?e=0:(d,e=-1,1):0}
[x,y]}
Lowjacker
fonte
2

OCaml + baterias, 182 168 caracteres

Isto é o que seria natural em Haskell, mas apenas é possível no OCaml:

open LazyList
let rec r(i,j)=lazy(let a,b=if(i+j)mod 2=0then i,j else j,i in
Cons((a,b),filter(fun(c,d)->a*d<>c*b)(r(if j=1 then 1,i+1else i+1,j-1))))
let f=nth(r(1,1))

Edit: A diagonal é desnecessária

Matías Giovannini
fonte
0

Perl 6 , 75 bytes

{(({|(1…($+=2)…1)}…*)Z/(1,{|(1…(($||=1)+=2)…1)}…*)).unique[$_]}

Teste-o

Isso basicamente gera toda a sequência de valores racionais, parando apenas quando o valor indexado é gerado.

(Com base no meu golfe para outro desafio.)

Expandido:

{  # bare block lambda with implicit parameter $_

  (
      ( # sequence of numerators

        {
          |( # slip into outer sequence (flatten)

            1      # start at one
            
            (
              $    # state variable
              += 2 # increment it by two each time this block is called
            )
            
            1      # finish at one
          )

        }
         * # never stop generating values
      )


    Z/   # zip using &infix:« /  » (generates Rats)


      ( # sequence of denominators

        1,  # start with an extra one

        {
          |( # slip into outer sequence (flatten)

            1
            
            (
              ( $ ||= 1 ) # state variable that starts with 1 (rather than 0)
              += 2        # increment it by two each time this is called
            )
            
            1
          )
        }
         * # never stop generating values
      )


  ).unique                # get only the unique values
  .[ $_ ]                 # index into the sequence
}

({1…($+=2)…1}…*)gera a sequência infinita de numeradores ( |(…)é usado acima para achatar)

(1 2 1)
(1 2 3 4 3 2 1)
(1 2 3 4 5 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 9 8 7 6 5 4 3 2 1)

(1,{1…(($||=1)+=2)…1}…*) gera a sequência infinita de denominadores

1
(1 2 3 2 1)
(1 2 3 4 5 4 3 2 1)
(1 2 3 4 5 6 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1)
(1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1)

Brad Gilbert b2gills
fonte