Simplifique uma fração

8

Vencedor: resposta de Ian D. Scott , em um byte (48 bytes)! Soberbo!

Seu programa deve aceitar a entrada de uma fração que pode ser simplificada e, em seguida, simplificada.

Regras:

  • Se a fração já estiver em sua forma mais simplificada, você deverá informar o usuário
  • Não há funções internas para fazer isso
  • O usuário deve digitar o número em algum momento; no entanto, o método que o programa lê não importa. Pode ser com stdin, console.readline, etc. Desde que o usuário digite 9/18(por exemplo) em algum momento, é válido
  • A saída deve ser feita com stdout, console.writeline, etc ...
  • A fração será inserida como x/ye deve produzir comoa/b
  • A fração deve gerar a forma mais simplificada. Por exemplo, 8/12 -> 6/9 não é válido , a única solução válida é 2/3.

  • Este concurso termina em 9 de agosto de 2014 (7 dias após a publicação)
  • Esta é uma questão de , então o código mais curto vence
Jon
fonte
1
Como devemos informar o usuário?
bebe
Stdout, console.writeline, etc.
Jon
7
Este é realmente um problema bastante trivial. Tudo o que você faz é dividir pelo gcd (uma função que geralmente é incorporada, mas não seria difícil de escrever).
Hobbies de Calvin
1
@ Calvin'sHobbies Sim, o problema em si é trivial. Fazer isso na menor quantidade de código não é tão fácil.
Jon
3
O que você quer dizer com "Se a fração já está em sua forma mais simplificada, você deve informar o usuário"? Deve haver uma mensagem específica além de apenas retornar a entrada? Nesse caso, eu não a resposta aceita satisfaz isso.
Martin Ender

Respostas:

1

Python - 69 48

A primeira coisa a fazer é representá-lo no formato nativo do python para armazenar frações, a saber, a classe Fraction.

print(__import__("fractions").Fraction(input()))

Agora simplificamos ... mas veja! Já está simplificado.

Isso conta como usar uma função interna? Não se destina especificamente à simplificação, e Fraction é uma classe de qualquer maneira, não uma função.

Eu não chamei nenhuma função simplificadora, por isso não é minha culpa se o python decidir fazer isso sozinho.

Ian D. Scott
fonte
Mas o construtor dessa classe é uma função?
flawr
@flawr type(fractions.Fraction.__init__)retorna em wrapper_descriptorvez de function, então você poderia dizer que não é uma função. Na verdade, isso significa apenas que é implementado em c, mas qualquer coisa que não esteja na função de classe não é uma função, certo?
Ian D. Scott
2
-1: este é um built-in. Embora não diga "simplificar" no nome, simplifica frações.
Cyoce 21/05
5

> <> (92)

0v
+>>>>>>a*ic4*-:0(?v
v@:{:~^?=2l0  ,a~ <
>:?!v:@%
=1:~<;no-1*4c,n,@:/?
|oooo;!'simplest' /

Eu sei que posso diminuir isso, vou jogar um pouco mais de manhã.

Explicação básica: As duas primeiras linhas e a segunda metade da terceira são todas para leitura de números. Infelizmente,> <> não tem como fazer isso, então a análise ocupa metade do programa.

A quarta linha é um simples cálculo iterativo do gcd. Estou surpreso com o desempenho da contagem de bytes no algoritmo real. Se não fosse pelo terrível I / O, poderia ser realmente um idioma de golfe razoável.

As duas últimas linhas são apenas para imprimir o resultado e dividir os números originais pelo MDC.

Mike Precup
fonte
você realmente fez melhor que todos, exceto o do golfe. agradável!
haskeller orgulhoso
não é mais verdade :-(
proud haskeller
3

GolfScript, 49 caracteres

'/'/{~}%.~{.@\%.}do;:G({{G/}%'/'*}{;'simplest'}if

Execute os dois casos de teste aqui :

> 8/12
2/3

> 7/12
simplest
Howard
fonte
3

JavaScript 101

Pela primeira vez, uma solução que não usa o EcmaScript 6

v=prompt().split('/');for(a=v[0]|0,b=v[1]|0;a-b;)a>b?a-=b:b-=a;
alert(a>1?v[0]/a+'/'+v[1]/a:'Reduced')

Mas com E6 poderia ser 93

[n,d]=prompt().split('/');for(a=n|0,b=d|0;a-b;)a>b?a-=b:b-=a;
alert(a>1?n/a+'/'+d/a:'Reduced')
edc65
fonte
1
for([a,b]=[c,d]=prompt().split('/');b;[a,b]=[b,a%b]);alert(a-1?c/a+'/'+d/a:'Reduced'); 86 i espero que seja matematicamente correto ...
bebe
2

Python 2.7, 124

from fractions import gcd;x,y=map(int,raw_input().split('/'));g=gcd(x,y);print'%d/%d'%(x/g,y/g)if g!=1 else'Already reduced'

Solução muito simples, embora eu saiba que seria mais curto em muitos outros idiomas.

Eu usei um importado, gcdmas se ele conta como um redutor de fração interno, ele pode ser implementado diretamente.

Passatempos de Calvin
fonte
2

Python 2 (82)

A,B=a,b=map(int,raw_input().split("/"))
while b:a,b=b,a%b
print`A/a`+"/"+`B/a`,a<2

Imprime um booleano posteriormente para dizer se o original estava na forma mais simples. Apenas faz o algoritmo GCD usual. A maioria dos caracteres é gasta na entrada / saída.

xnor
fonte
Não seria mais curto usar o Python 3 input()?
mbomb007
@ mbomb007 Já faz um tempo, mas acho que os 4 caracteres salvos são mais do que perdidos pelo Python 3 que precisa ser analisado print, mapser descompactado e talvez inteiro, em vez da divisão float.
Xnor
Esqueceu a divisão. Só isso faria com que "não valesse a pena". O que você quer dizer com mapser desembalado?
mbomb007
@ mbomb007 Meu erro, a,b=map(int,...)não requer caracteres extras, pois é a,b=...descompactado automaticamente. O problema que você às vezes encontra com o Python 3 é que mapnão produz uma lista, mas um objeto de mapa que exige a transformação em uma lista antes que você possa fazer algo como cortá-la. Uma expressão como *l,=map(...)é necessária para atribuir lcomo uma lista.
Xnor
2

PHP> = 7.1, 76 bytes (não-concorrente)

for([$x,$y]=explode("/",$argn),$t=1+$x;$y%--$t||$x%$t;);echo$x/$t."/".$y/$t;

Versão Online

Jörg Hülsermann
fonte
1

C, 94

Apenas adivinhe a força bruta e verifique se o GCD começa em a | b até 1;

main(a,b,c){scanf("%d/%d",&a,&b);for(c=a|b;--c;)if(a%c+b%c<1)a/=c,b/=c;printf("%d/%d\n",a,b);}
technosaurus
fonte
83: c;d;f(a,b){b?f(b,a%b):printf("%d/%d",c/a,d/a);}main(){scanf("%d/%d",&c,&d);f(c,d);}
bebe
0

Rebmu (104 caracteres)

P"/"rSst[a b]paSp AtiA BtiB Ca DbFOiMNcD 1 -1[izADmdCiMDdI[CdvCi DdvDi]]QapAPtsCpTSdIa^e?aCe?bD[Q"Err"]Q

Não silencioso:

P"/"
rS
; extract numerator to a, denominator to b
st [a b] pa s p
; convert a,b to integers
AtiA
BtiB
; set c=a, d=b
Ca Db
; loop from min(c,d) to 1
fo i mn c d 1 -1[
    ; check if (c mod i) + (d mod i) is 0
    iz ad md c i md d i [
        ; divide c, d by i
        Cdv c i
        Ddv d i
    ]
]
; set Q to c/d
Qap ap ts c p ts d
; check if a==c and b==d
i a^ e? a c e? b d[
    ; set q to "err"
    Q"err"
]
; print q
Q
es1024
fonte
0

PHP 156

meh.

$f=$argv[1];$p=explode('/',$f);$m=max(array_map('abs',$p));for(;$m;$m--)if(!($p[0]%$m||$p[1]%$m)){$r=$p[0]/$m.'/'.$p[1]/$m;break;}echo $r===$f?'reduced':$r;

Corre:

php -r "$f=$argv[1];$p...[code here]...:$r;" 9/18;
1/2
  • imprime "reduzido" se a fração já estiver em sua forma mais simples
  • trabalha com frações negativas
  • trabalha com frações impróprias (por exemplo, 150/100 dá 3/2)
  • meio que funciona com decimais (por exemplo, 1,2 / 3,6 fornece 0,75 / 2,25)
  • 99/0 incorretamente dá 1/0 ?
  • não será reduzido a um número inteiro (por exemplo, 100/100 dá 1/1)

Aqui está uma versão não-gasta com alguns testes (modificados em forma de função):

<?php
$a = array(
    '9/18','8/12','50/100','82/100','100/100','150/100','99/100',
    '-5/10','-5/18','0.5/2.5','1.2/3.6','1/0','0/1','99/0'
);
print_r(array_map('r',array_combine(array_values($a),$a)));

function r($f) {
    $p = explode('/',$f);
    $m = max(array_map('abs',$p));
    for ( ; $m; $m-- )
        if ( !($p[0] % $m || $p[1] % $m) ) {
            $r = $p[0]/$m.'/'.$p[1]/$m;
            break;
        }
    return $r === $f ? 'reduced' : $r;
}
/*
Array(
    [9/18] => 1/2
    [8/12] => 2/3
    [50/100] => 1/2
    [82/100] => 41/50
    [100/100] => 1/1
    [150/100] => 3/2
    [99/100] => reduced
    [-5/10] => -1/2
    [-5/18] => reduced
    [0.5/2.5] => 0.2/1
    [1.2/3.6] => 0.75/2.25
    [1/0] => reduced
    [0/1] => reduced
    [99/0] => 1/0
)
*/
?>
zamnuts
fonte
0

Java, 361 349 329 (obrigado @Sieg pela intdica)

class P{public static void main(String[]a){String[]e=a[0].split("/");String f="";int g=new Integer(e[0]),h=new Integer(e[1]);if(g>h){for(int i=h;i>=1;i--){if(g%i==0&&h%i==0){f=g/i+"/"+h/i;break;}}}else if(g<h){for(int i=g;i>=1;i--){if(g%i==0&&h%i==0){f=g/i+"/"+h/i;break;}}}else if(g.equals(h)){f="1/1";}System.out.println(f);}}

Sei que não é curto, mas estou hipnotizado com o que fiz.

Para usá-lo, compile o código e execute-o passando os argumentos pela linha de comando.

  • Somente números inteiros (não gosto doublese a tarefa não exige).
  • Se a fração já estiver simplificada, ele retornará.
  • Não funciona com frações negativas.
  • Dividindo por zero? Nenhum cookie para você (retorna uma string vazia).

Ungolfed (se alguém quiser ver essa bagunça):

class P{
    public static void main(String[]a){
        String[]e=a[0].split("/");
        String f="";
        int g=new Integer(e[0]),h=new Integer(e[1]);
        if(g>h){
            for(int i=h;i>=1;i--){
                if(g%i==0&&h%i==0){
                    f=g/i+"/"+h/i;
                    break;
                }
            }
        }else if(g<h){
            for(int i=g;i>=1;i--){
                if(g%i==0&&h%i==0){
                    f=g/i+"/"+h/i;
                    break;
                }
            }
        }else if(g.equals(h)){
            f="1/1"; //no processing if the number is THAT obvious.
        }
        System.out.println(f);
    }
}
g.carvalho97
fonte
1
Você realmente deve usar em intvez de Integer, mesmo no código de produção. Int é alocado da pilha, enquanto inteiro é da pilha.
seequ
@ Sleg Bem, eu não sabia disso, muito obrigado.
precisa saber é o seguinte
Então algo que você não deve usar na produção. Apenas ligar new Integer(str)terá o mesmo resultado que Integer.parseInt(str). Além disso, por que não usar String f=""(sempre)?
seequ
@ Sieg Obrigado novamente, mas por que isso? Eu sei que new Integer(str)cria um Integerfora de uma string, mas não Integer.parseInt(str)faz a mesma coisa? E a coisa com String f="", eu sei que eu deveria usá-lo mais String f=new String(), mas eu não sei porque eu não, talvez seja um mau hábito: P
g.carvalho97
1
Integer.parseIntrealmente faz a mesma coisa, mas com alguns valores em cache para uma pesquisa mais rápida.
seequ
0

Ruby - 112 caracteres

gé um lambda auxiliar que calcula o GCD de dois números inteiros. frecebe uma fração como uma string, por exemplo '42/14', e gera a fração reduzida ou simplestse o numerador e o denominador são relativamente primos.

g=->a,b{(t=b;b=a%b;a=t)until b==0;a}
f=->z{a,b=z.split(?/).map &:to_i;y=g[a,b];puts y==1?:simplest:[a/y,b/y]*?/}

Alguns casos de teste:

test_cases = ['9/18', '8/12', '50/100', '82/100', '100/100',
              '150/100', '99/100', '-5/10', '-5/18', '0/1']

test_cases.map { |frac| f[frac] }

Resultado:

1/2
2/3
1/2
41/50
1/1
3/2
simplest
-1/2
simplest
simplest

Note que, embora contra as regras, Ruby tenha Rationalsuporte, então poderíamos fazer

a=gets.chomp;b=a.to_r;puts b.to_s==a ?:simplest:b
OI
fonte
0

JavaScript (91) (73)

Retorna '/' quando a fração já está em sua forma mais simples. A função g calcula o gcd. BTW: Existe alguma maneira mais curta para '1 == something' em que algo é um número inteiro não negativo?

function s(f){[n,m]=f.split(b='/');g=(u,v)=>v?g(v,u%v):u;return 1==(c=g(n,m))?b:n/c+b+m/c;}

Obrigado a @bebe por uma versão ainda mais curta:

s=f=>([n,m]=f.split(b='/'),c=(g=(u,v)=>v?g(v,u%v):u)(n,m))-1?n/c+b+m/c:f;
flawr
fonte
use es6 de forma consistente. chame sua função s=f=>...e atribua g ao usá-la (g=...)(n,m), passe-a para c e teste se é igual a 1 por c-1?not_equals:equalse tente evitar o retorno. Resultado: s=f=>([n,m]=f.split(b='/'),c=(g=(u,v)=>v?g(v,u%v):u)(n,m))-1?n/c+b+m/c:f;73 (Devolve a forma mais simples (f), se não puder ser reduzido)
bebe
1
Wow isso é ótimo! Eu não conseguia pensar em uma maneira de agrupar a coisa do shole em uma declaração, é por isso que eu usei functione return. E obrigado pelas -1=)
flawr
0

Lua - 130 115 caracteres

10/10 eu realmente tentei

a,b=io.read():match"(.+)/(.+)"u,v=a,b while v+0>0 do t=u u=v v=t%v end print(a+0==a/u and"reduced"or a/u.."/"..b/u)
  • imprime "reduzido" se a fração estiver na forma mais simples
  • trabalha com negativos
  • trabalha com frações impróprias
  • presumivelmente funciona com decimais (1,2 / 3,6 fornece 5,4043195528446e + 15 / 1,6212958658534e + 16)
  • qualquer número / 0 dá 1/0
  • não reduz para números inteiros

Eu aproveitei totalmente a capacidade de Lua de converter automaticamente uma string em um número ao realizar operações aritméticas em uma string. Eu tive que adicionar "+0" no lugar do número para obter algum código de comparação.

Desculpe, eu não tenho uma versão não-destruída, a descrição acima é como eu a escrevi

Dwayne Slater
fonte
0

Lote - 198

for /f "tokens=1,2delims=/" %%a in ("%1")do set a=%%a&set b=%%b&set/ac=%%b
:1
set/ax=%a%%%%c%&set/ay=%b%%%%c%
if %x%%y%==00 set/aa/=%c%&set/ab/=%c%
if %c% GTR 0 set/ac=%c%-1&goto 1
echo %a%/%b%

Entrada é dividida como a/b, em seguida, para cada cem b,b-1,...1vamos verificar se ae bsão divisíveis por c, e dividi-los por cse eles são. Então voltamosa/b

Furioso
fonte
0

Befunge 93 (192)

&04p~$&14p2       > :24p  v       >34g#v_0"tselpmiS">:#,_@
>134p 24g>        ^+1g42$<>04g`   |    >04g."/",14g.@
^p41/g42p40/g42<         |%g42:g41<
         #     |!%g42:g40<
   0     ^+1g42<
sig_seg_v
fonte
0

C 135

Aceita entrada para 2 números inteiros separados por espaço. Mantém a divisão pelo mínimo de a & b abaixo de 1 para encontrar o GCD.

int a,b,m;
void main()
{
scanf("%d %d", &a, &b);
m=a<b?a:b;
for (;m>0;m--){if (a%m==0&&b%m==0)break;}
printf("%d/%d",a/m,b/m);
}
bacchusbeale
fonte
0

Java (200)

A melhor solução anterior em Java ainda tinha> 300 bytes, esta possui 200:

class M {public static void main(String[]args){String[]s=args[0].split("/");int a=Integer.parseInt(s[0]),b=Integer.parseInt(s[1]),c=a,d=b;while(d>0){int g=c;c=d;d=g%d;}System.out.print(a/c+"/"+b/c);}}

Isso usa o módulo (mais rápido) para determinar o MDC em vez de iterar todos os números.

Roy van Rijn
fonte
1
Você pode remover o espaço depoisclass M
mbomb007