Tarefa:
Seu programa recebe uma fração simples positiva e adequada no formato .<numerator>/<denominator>
Para esta entrada, ele deve encontrar duas frações.
- Uma fração que é menor que a entrada.
- Uma fração que é maior que a entrada.
Ambas as frações devem ter um denominador menor que a entrada. De todas as frações possíveis, elas devem ter a menor diferença para a entrada.
Saída:
A saída do seu programa deve ser:
- Uma fração menor que a entrada, no formato
<numerator>/<denominator>
. - Seguido por um caractere de espaço (código ASCII 32).
- Seguido por uma fração que é maior que a entrada, no formato
<numerator>/<denominator>
.
Do seguinte modo:
«fraction that is < input» «fraction that is > input»
Regras:
- Todas as frações produzidas devem estar nos termos mais baixos .
- Todas as frações produzidas devem ser frações apropriadas.
- Se não houver frações apropriadas possíveis permitidas pelas regras, você deverá gerar
0
uma saída em vez de uma fração <entrada e em1
vez de uma fração> entrada. - Você pode escolher se deseja receber a fração como argumento da linha de comando (por exemplo
yourprogram.exe 2/5
) ou solicitar a entrada do usuário. - Você pode assumir que seu programa não receberá entrada inválida.
- O código mais curto (em bytes, em qualquer idioma) vence.
Quaisquer argumentos de linha de comando não padrão (argumentos que normalmente não são necessários para executar um script) contam para a contagem total de caracteres.
O que seu programa não deve fazer:
- Depende de quaisquer recursos externos.
- Depende de ter um nome de arquivo específico.
- Saída qualquer coisa que não seja a saída necessária.
- Demore excepcionalmente para executar. Se o seu programa executar mais de um minuto para frações com um numerador e denominador de 6 dígitos (por exemplo
179565/987657
) no computador de um usuário doméstico comum, é inválido. - Frações de saída com
0
o denominador. Você não pode dividir por zero. - Frações de saída com
0
o numerador. Seu programa deve produzir em0
vez de uma fração. - Reduza uma fração inserida. Se a fração dada como entrada for redutível, você deve usar a fração conforme é inserida.
- Seu programa não deve ser escrito em uma linguagem de programação para a qual não existia um compilador / intérprete publicamente disponível antes que esse desafio fosse lançado.
Exemplos:
Entrada: 2/5
Saída: 1/3 1/2
Entrada: 1/2
Saída: 0 1
Entrada: 5/9
Saída: 1/2 4/7
Entrada: 1/3
Saída: 0 1/2
Entrada: 2/4
Saída: 1/3 2/3
Entrada: 179565/987657
Saída: 170496/937775 128779/708320
1/3 1/2
.Respostas:
Sábio -
119117Sage é necessário apenas na última linha, que cuida da saída. Tudo o resto também funciona em Python.
Substitua
raw_input()
porsys.argv[1]
para que a entrada seja lida a partir de um argumento da linha de comandos, em vez de um prompt. Isso não altera a contagem de caracteres. (Não funciona no Python sem importarsys
primeiro.)Isso essencialmente recursivamente constrói a respectiva sequência do Farey usando medianas dos elementos existentes, mas se restringe aos elementos mais próximos da entrada. De outro ponto de vista, ele executa uma pesquisa por intervalo aninhado nas respectivas seqüências do Farey.
Ele processa corretamente todos os exemplos em menos de um segundo na minha máquina.
Aqui está uma versão não destruída:
fonte
exec
!Python 2.7 - 138
Comecei com a solução óbvia de força bruta, mas percebi que, como o OP queria resolver instâncias com numeradores e denominadores de seis dígitos em menos de um minuto, preciso de uma solução melhor do que tentar um trilhão de possibilidades. Encontrei uma fórmula útil na página da Wikipedia para a sequência do Farey: se a / b, c / d são vizinhos em uma das seqüências do Farey, com
a/b<c/d
, entãob*c-a*b=1
. O loop while dentro de f no meu programa estende esse fato a números não reduzidos, usando o gcd, que o outro loop while calcula.Eu já joguei isso muito duro, mas eu adoraria ouvir alguma sugestão.
Edições:
166-> 162: Removido
a
eb
do programa externo. Eles eram desnecessários.162-> 155:
str()
-> ``155-> 154: Adicionado
k
.154-> 152: Removido
x
de dentro da função, passou como um argumento.152-> 150: Deu
a
um valor padrão em vez de passá-lo como argumento.150-> 146: Alterada a inicialização de
x
ey
.146-> 145: Removido
k
.145-> 144: Alterado ... e ... ou ... para (..., ...) [...], economizando espaço.
144-> 138: Alterado (..., ...) [...] para ... + ... * (...). Graças a @ mbomb007.
Casos de teste:
O penúltimo teste levou menos de um segundo no meu computador, enquanto o último demorou cerca de 5 a 10 segundos.
fonte
k=1
é pura maldade.print`(a*n+p)/d`+('/'+`a`)*(a>1),
Mathematica, 163 bytes
Isso é severamente limitado pelo requisito de entrada / saída, como entrada e seqüências de caracteres do usuário. Lidar com cordas é realmente complicado no Mathematica (pelo menos quando você quer jogar golfe). Fazendo isso da maneira natural no Mathematica, (usando apenas números inteiros e racionais), eu provavelmente reduziria isso para 50% do tamanho.
Pode fazer números de 6 dígitos em alguns segundos na minha máquina.
Um pouco mais legível (apesar de não ser realmente destruído):
Por uma questão de diversão, fazer isso "da maneira natural", ou seja, como uma função que leva numerador e denominador e retorna dois racionais, isso tem apenas 84 caracteres (portanto, minha estimativa de 50% foi bem próxima):
fonte
Julia -
127125 bytesAbordei isso de uma perspectiva matemática para evitar a necessidade de loops; portanto, esse código funciona muito rápido para entradas grandes (nota: se a / b é a entrada, a * b deve caber no Int64 (Int32 em sistemas de 32 bits) , caso contrário, serão geradas respostas sem sentido - se aeb forem expressáveis no Int32 (Int16 em sistemas de 32 bits), nenhum problema ocorrerá.
UPDATE: Não é mais necessário sobrecarregar a barra invertida para div, usando ÷, uma rede que economiza 2 bytes.
Ungolfed:
Ideia básica: encontre o maior def menor que b que satisfaça ad-bc = gcd (a, b) (próximo menor) e be-af = gcd (a, b) (próximo maior), depois calcule c e e de há. A saída resultante é c / de / f, a menos que d ou f seja 1; nesse caso, / d ou / f é omitido.
Curiosamente, isso significa que o código também funciona para frações impróprias positivas, desde que a entrada não seja um número inteiro (ou seja, gcd (a, b) = a).
No meu sistema, a entrada
194857602/34512958303
não leva tempo perceptível para a saída171085289/30302433084 23772313/4210525219
fonte
55552/999999
me dá-396/920632 486/936509
.int32(55552*999999)
dá-282630400
. Para mim, com esse teste, percebo51143/920632 52025/936509
que os denominadores são os mesmos e que 52025-51143 = 486 - (- 396). Vou adicionar uma nota para mencionar esse problema.1234567891234567/2145768375829475878
resulta em869253326028691/1510825213275018197 365314565205876/634943162554457681
. Essa alteração adiciona apenas 3 caracteres extras.JavaScript, 131
Com notação de seta gorda e
eval
chamadas:O
179565/987657
teste de estresse é executado em aproximadamente 35 segundos no Firefox, muito mais no Chrome (~ 6 minutos)Método mais rápido e sem
eval
e notação de seta gordaO
179565/987657
teste de estresse é executado em aproximadamente 5 segundos.Não jogou golfe:
fonte
eval
. EEK2/6
dá1/3 2/5
, no entanto,1/3
não é menor que, mas igual a2/6
.perl, 142 bytes (155 sem CPAN)
Ou se os módulos CPAN não forem permitidos / for necessário código 3-4 vezes mais rápido:
A versão anterior leva 9,55 segundos na minha máquina, a última versão 2,44 segundos.
Menos ilegível:
fonte