Fração mais próxima

24

Tarefa:

Seu programa recebe uma fração simples positiva e adequada no formato .<numerator>/<denominator>

Para esta entrada, ele deve encontrar duas frações.

  1. Uma fração que é menor que a entrada.
  2. 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 0uma saída em vez de uma fração <entrada e em 1vez 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 0o denominador. Você não pode dividir por zero.
    • Frações de saída com 0o numerador. Seu programa deve produzir em 0vez 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

user2428118
fonte
11
Seu primeiro exemplo não corresponde à especificação: Ambas as frações devem ter um denominador menor que a entrada.
254 Howard
11
Primeiro exemplo, a saída deve ser 1/3 1/2.
precisa saber é o seguinte
@HeikoOberdiek Você está certo. Fixo.
usar o seguinte comando
11
Defina "computador médio do usuário doméstico". 90 segundos em uma máquina Intel Atom de 1,6 GHz são aceitáveis?
John Dvorak
2
Seu último exemplo está incorreto. A fração de entrada é igual à primeira das frações de saída.
DavidC

Respostas:

3

Sábio - 119 117

x,X=map(int,raw_input().split('/'))
a=0
A=c=C=1
while C<X:exec("ab,,AB"[c*X>C*x::2]+"=c,C");c=a+b;C=A+B
print a/A,b/B

Sage é necessário apenas na última linha, que cuida da saída. Tudo o resto também funciona em Python.

Substitua raw_input()por sys.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 importar sysprimeiro.)

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:

x,X = map(Integer,sys.argv[1].split('/'))
x = x/X
a = 0
c = b = 1
while c.denominator() < X:
    if c > x:
        b = c
    else:
        a = c
    c = ( a.numerator() + b.numerator() ) / ( a.denominator() + b.denominator() )
print a,b
Wrzlprmft
fonte
Eu já tinha medo de não receber novos envios para esta recompensa. Ótimo trabalho.
user2428118
Bom truque com o exec!
Xnor
Como a única resposta apresentada dentro do período de recompensa, concedo a você a recompensa. Parabéns.
user2428118
Eu apenas corrigi um erro em um dos exemplos. Você pode corrigir seu envio (mesmo que tenha passado meio ano desde que o enviou).
user2428118
12

Python 2.7 - 138

x,y=n,d=map(int,raw_input().split('/'))
while y:x,y=y,x%y
def f(p,a=d):
 while(a*n+p)%d:a-=1
 print`(a*n+p)/d`+('/'+`a`)*(a>1),
f(-x);f(x)

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ão b*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 ae bdo programa externo. Eles eram desnecessários.
162-> 155: str()-> ``
155-> 154: Adicionado k.
154-> 152: Removido xde dentro da função, passou como um argumento.
152-> 150: Deu aum valor padrão em vez de passá-lo como argumento.
150-> 146: Alterada a inicialização de xe y.
146-> 145: Removido k.
145-> 144: Alterado ... e ... ou ... para (..., ...) [...], economizando espaço.
144-> 138: Alterado (..., ...) [...] para ... + ... * (...). Graças a @ mbomb007.

Casos de teste:

2/5
1/3 1/2

1/2
0 1

2/4
1/3 2/3

179565/987657
170496/937775 128779/708320

12345678/87654321
12174209/86436891 11145405/79132382

O penúltimo teste levou menos de um segundo no meu computador, enquanto o último demorou cerca de 5 a 10 segundos.

isaacg
fonte
Isso k=1é pura maldade.
Evpok
11
@ Evpok: Eu estava tentando fazer o k = y = n funcionar, mas aparentemente se você modificar uma variável dentro de uma função, o python quer que seja local. Essa era a única maneira de obter uma variável local em 4 caracteres. Além disso, como a fração for positiva e adequada, o denominador não pode ser 1.
isaacg
Os argumentos da linha de comando são fáceis com o Python, portanto eles deveriam ter sido usados ​​para entrada, conforme as instruções aqui.
Alex Thornton
11
" Você pode escolher se deseja receber a fração como um argumento de linha de comando (por exemplo, yourprogram.exe 2/5) ou solicitar a entrada do usuário ."
Isaacg
Salve 6 caracteres:print`(a*n+p)/d`+('/'+`a`)*(a>1),
mbomb007
5

Mathematica, 163 bytes

{a,b}=FromDigits/@InputString[]~StringSplit~"/";r=Range[b-1];""<>Riffle[#~ToString~InputForm&/@(#@DeleteCases[#2[a/b*r]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}})," "]

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

{a, b} = FromDigits /@ InputString[]~StringSplit~"/";
r = Range[b - 1];
"" <> Riffle[#~ToString~
     InputForm & /@ (#[DeleteCases[#2[a/b*r]/r, a/b]] & @@@ {{Max, 
       Floor}, {Min, Ceiling}}), " "]

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

f[a_,b_]:=#@DeleteCases[#2[a/b*(r=Range[b-1])]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}}
Martin Ender
fonte
3

Julia - 127 125 bytes

Abordei 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.

a,b=int(split(readline(),"/"));k=gcd(a,b);f=b-invmod(a÷k,b÷k);d=2b-f-b÷k;print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1))

Ungolfed:

a,b=int(split(readline(),"/")) # Read in STDIN in form a/b, convert to int
k=gcd(a,b)           # Get the greatest common denominator
f=b-invmod(a÷k,b÷k)  # Calculate the denominator of the next biggest fraction
d=2b-f-b÷k           # Calculate the denominator of the next smallest fraction
print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1)) # Calculate numerators and print

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/34512958303não leva tempo perceptível para a saída171085289/30302433084 23772313/4210525219

Glen O
fonte
Testar com 55552/999999me dá -396/920632 486/936509.
User2428118
@ user2428118 - Você está em um sistema de 32 bits (ou está usando uma Julia de 32 bits)? Eu usei "int", o que significa que em um sistema de 32 bits, ele usará o Int32 em vez do Int64. int32(55552*999999)-282630400. Para mim, com esse teste, percebo 51143/920632 52025/936509que os denominadores são os mesmos e que 52025-51143 = 486 - (- 396). Vou adicionar uma nota para mencionar esse problema.
Glen O
Se você deseja garantir que o código funcione para todas as entradas de tamanho Int64, substitua "int" por "int128". Com essa mudança, a entrada 1234567891234567/2145768375829475878resulta em 869253326028691/1510825213275018197 365314565205876/634943162554457681. Essa alteração adiciona apenas 3 caracteres extras.
Glen O
Sim, estou usando um computador de 32 bits. Vou experimentá-lo em uma máquina de 64 bits em algum momento em que tiver tempo para isso.
precisa saber é o seguinte
Testar em um computador de 64 bits fornece o resultado correto, por isso estou aceitando esta resposta.
precisa saber é o seguinte
2

JavaScript, 131

Com notação de seta gorda e evalchamadas:

m=>{for(e=eval,n=e(m),i=p=0,q=1;++i</\d+$/.exec(m);)if(n*i>(f=n*i|0))g=f+1,p=f/i>e(p)?f+'/'+i:p,q=g/i<e(q)?g+'/'+i:q;return p+' '+q}

O 179565/987657teste de estresse é executado em aproximadamente 35 segundos no Firefox, muito mais no Chrome (~ 6 minutos)

Método mais rápido e sem evale notação de seta gorda

for(n=eval(m=prompt(a=i=p=0,b=c=d=q=1));++i<m.match(/\d+$/);)if(n*i>(f=n*i|0))g=f+1,p=f*c>i*a?(a=f)+'/'+(c=i):p,q=g*d<i*b?(b=g)+'/'+(d=i):q;alert(p+' '+q)

O 179565/987657teste de estresse é executado em aproximadamente 5 segundos.

Não jogou golfe:

m=prompt(); //get input
a=0; c=1; //first fraction
b=1; d=1; //second fraction
n=eval(m); //evaluate input
for (i=1; i<m.match(/\d+$/); i++) { //loop from 1 to input denominator
  f=Math.floor(n*i);
  if (n*i > f) { //if fraction not equal to simplification of input
    g=f+1; // f/i and g/i are fractions closer to input
    if (f/i>a/c) a=f, c=i;
    if (g/i<b/d) b=g; d=i; 
  }
}
alert(a+'/'+c+' '+b+'/'+d); //output values handling 0 and 1 correctly
Michael M.
fonte
também ... muito ... eval. EEK
John Dvorak
3
Testar com 2/61/3 2/5, no entanto, 1/3não é menor que, mas igual a 2/6 .
usar o seguinte comando
@ user2428118 corrigido
Michael M.
Por que essa resposta foi aceita tão cedo?
Evpok
11
@ user2428118: Você pode esperar alguns dias antes de aceitar soluções. Além disso, essa solução não é mais a mais curta.
Isaacg
2

perl, 142 bytes (155 sem CPAN)

use bare A..Z;$/="/";N=<>;D=<>;F=N/D;K=G=1;for$H(1..D){J<F&&J>E?(E,I):J>F&&J<G?(G,K):()=(J=$_/H,"$_/$H")for(Z=int F*H)..Z+1}print I||0," $K\n"

Ou se os módulos CPAN não forem permitidos / for necessário código 3-4 vezes mais rápido:

$/="/";$N=<>;$D=<>;$F=$N/$D;$g=$G=1;for$d(1..$D){$f<$F&&$f>$E?($E,$e):$f>$F&&$f<$G?($G,$g):()=($f=$_/$d,"$_/$d")for($z=int$F*$d)..$z+1}print$e||0," $g\n"

A versão anterior leva 9,55 segundos na minha máquina, a última versão 2,44 segundos.

Menos ilegível:

($N, $D) = split(m[/], <>);
$F = $N / $D;
$G = 1;
foreach $d (1 .. $D) {
    $z = int $F * $d;
    foreach $_ ($z .. $z + 1) {
        $f = $_ / $d;
        ($f < $F && $f > $E ? ($E, $e) :
        ($f > $F && $f < $G ? ($G, $g) : ())) = ($f, "$_/$d");
    }
}
print $e || 0, ' ', $g || 1, "\n";
skibrianski
fonte