Esta questão não precisa ser aplicada apenas ao final de decimais - os decimais repetidos também podem ser convertidos em frações por meio de um algoritmo.
Sua tarefa é criar um programa que use um decimal repetido como entrada e faça a saída do numerador e denominador correspondente (em termos mais baixos) que produz essa expansão decimal. Frações maiores que 1 devem ser representadas como frações impróprias 9/5
. Você pode assumir que a entrada será positiva.
O decimal repetido será fornecido neste formato:
5.3.87
com tudo depois do segundo ponto repetido, assim:
5.3878787878787...
Seu programa produzirá dois números inteiros representando o numerador e o denominador, separados por uma barra (ou a forma equivalente no seu idioma, se você não produzir texto sem formatação):
889/165
Observe que os decimais finais não terão nada após o segundo ponto, e os decimais sem parte decimal não repetida não terão nada entre os dois pontos.
Casos de teste
Esses casos de teste cobrem todos os casos de canto necessários:
0..3 = 1/3
0.0.3 = 1/30
0.00.3 = 1/300
0.6875. = 11/16
1.8. = 9/5
2.. = 2/1
5..09 = 56/11
0.1.6 = 1/6
2..142857 = 15/7
0.01041.6 = 1/96
0.2.283950617 = 37/162
0.000000.1 = 1/9000000
0..9 = 1/1
0.0.9 = 1/10
0.24.9 = 1/4
Se desejar, você também pode assumir que frações sem partes inteiras não têm nada à esquerda do primeiro ponto. Você pode testar isso com estes casos de teste opcionais:
.25. = 1/4
.1.6 = 1/6
..09 = 1/11
.. = 0/1
fonte
9/99
?(in lowest terms)
isto é, a fração deve ser simplificada.13
vez de13/1
?1.9999...
e de saída2/1
1.9999.
é19999/10000
, para2/1
você precisar1..9
, não é?Respostas:
Dyalog APL (
75736968 caracteres)Aqui está outra e quinta tentativa (provavelmente a minha última); Passei o dia tentando escrever um pedaço de código com menos de 80 caracteres e sendo totalmente consistente com as regras. Este desafio fez o meu dia!
Finalmente, recebi uma linha de APL composta por 75 caracteres, trabalhando com o Dyalog APL (mas não na página do interpretador on-line porque usando a função
⍎
execute ), que é a seguinte:É claro que eu poderia torná-lo um pouco mais curto, mas os casos especiais em que um, dois ou três campos estão ausentes. Meu código pode até lidar com o
..
caso de entrada.Sei que a APL é difícil de ler e, como as pessoas gostam de entender como um pedaço de código realmente funciona, aqui estão algumas explicações. Basicamente, calculo o denominador final na variável D e o numerador final na variável N.
O APL é analisado da direita para a esquerda.
I←
).P←'.'=
). Por exemplo, '1.2.3' será mapeado para 0 1 0 1 0.10⊥
); agora '1.2.3' é 1010.1-⍨
ou com¯1+
, aqui eu escolhi o segundo). Agora '1.2.3' é 1009.⍕
), dois dígitos iniciais são removidos (2↓
), o que faz 09 do nosso exemplo inicial '1.2.3'; a string é invertida (⌽
).'0',
fico triste ao usar os quatro caracteres, mas fiz isso para evitar um erro quando os campos segundo e terceiro estão vazios. A sequência é convertida novamente em um número (⍎
) e é armazenada em D, que é o denominador, exceto quando os dois últimos campos estão vazios, porque nesse caso D é igual a 0.D←D+0=
trecho de código definido D como 1 se atualmente for nulo e agora D contém o denominador (antes da divisão GCD).×
) pelo conteúdo da cadeia inicial I até o segundo ponto com o(⍎'0',I/⍨2>+\P)
qual começa novamente P (0 1 0 1 0 no meu exemplo), adiciona os números sucessivos acumulando-os (o que torna 0 1 1 2 2 no meu exemplo), verifique quais valores são menores que 2 (criando o vetor booleano 1 1 1 0 0) e usando os caracteres correspondentes em I; outro 0 é adicionado na frente da sequência para impedir outra interceptação (se os dois campos iniciais estiverem vazios) e o todo é convertido em um número.(⍎'0',1↓I/⍨2=+\P)
, o que leva P novamente, adiciona ao acumular novamente, verifica quais valores são iguais a 2 (veja a explicação anterior), pega os caracteres, remove o primeiro que é um ponto , adiciona um caractere 0 inicial impeditivo e converte em um número.edit: Aqui está uma correção para 73 caracteres:
A idéia desse hack é computar primeiro o caso em que a adição cumulativa tem valores iguais a 2, armazenando-os para mais tarde e invertendo essa máscara bit a bit para obter o primeiro caso; assim, calcular o próximo caso precisa de menos caracteres.
edit: Aqui está outra correção para 69 caracteres:
A idéia desse hack é incorporar o caso especial mais complicado como código APL na string a ser avaliada (no estágio de conversão de string para número).
edit: Aqui está outra correção para 68 caracteres:
A idéia desse hack é substituir a adição de -1 ao valor para subtrair 1 a esse valor pela operação subtrair esse valor para 1 e depois remover mais um caractere no início (que será o sinal de menos).
editar: Mudança cosmética:
Nenhuma melhoria no tamanho, mas mais satisfeito em obter a função máxima do código a ser avaliado.
fonte
INVALID TOKEN
. Você sabe por quê?I
): ver este permalinkPerl 6 (
93101100806866 bytes)O tamanho foi aumentado para lidar com nada, em vez de apenas falhar. Mouq propôs usar
$/
, então agora está sendo usado, e o código é 20 bytes mais curto. Ayiko propôs substituir/
por, então o código é ainda mais curto (em 12 bytes). Então Mouq propôs a substituição
chars
porcomb
(no contexto numérico, eles são idênticos, porque a lista de caracteres após a conversão para número é o número de caracteres).Saída de amostra:
fonte
0..09
retorna1/11
, mas0.0.09
retorna1/110
.0.1 + 0.2 == 0.3
no Perl 6.$/=split ".",get;say join "/",($0+($1+$2/(9 x chars $2 or 1))/10**$1.chars).nude
:)J (
859089 caracteres)Minha função original, que era 5 caracteres menor que a segunda, tinha alguns bugs: não produzia números inteiros como "n / 1" e deu a resposta errada em números com mais de uma dúzia de dígitos. Aqui está uma função corrigida em J que também incorpora a sugestão de Eelvex de salvar um personagem:
Ele recebe uma string e retorna uma string. Aqui está uma sessão de amostra:
fonte
0/1
e3/1
inf dois primeiros casos de teste, consulte este comentário('0','x',~])
e salve um byte.C, 171
Bastante tempo. Pode ser ainda mais reduzido. Não
scanf
, o que realmente não aguenta se não houver números entre os pontos. Nãostrtol
. Apenas trituração de números:Teste:
fonte
DC (não totalmente geral, reduzido para 76 caracteres)
Não totalmente geral, mas, por favor, considere que eu fiz isso com uma das coisas mais antigas do mundo:
Editar: eu edito minha solução; não é mais geral, mas um pouco mais curto:
Use-o como:
O primeiro campo não é obrigatório:
está bem.
O segundo e o campo sede requerem pelo menos um dígito
fonte
Javascript, 203
Muito tempo, mas ainda assim divertido. Novas linhas porque ponto e vírgula são ilegíveis.
fonte
889/NaN
quando corro5.3.87
... Estou fazendo algo errado?"889/165"
no console. Como você está executando isso? @rafaelcastrocoutob=1
peça para dentroprompt()
.f=(P(10,s[2].length)-1)*P(10,l),f=f?f:1
=>f=(P(10,s[2].length)-1)*P(10,l)||1
J (método diferente)
Outra solução baseada em um método muito diferente; desta vez é totalmente geral; somente falta o denominador 1 quando um número inteiro é enviado:
fonte
GolfScript (67 caracteres)
NB Suporta partes inteiras vazias.
Se a sequência for do formato
'n.p.q'
, o valor serán + p/E + q/(DE) = ((nD + p)E + q)/DE
ondeD = 10^(len p)
eE = 10^(len q) - 1
, exceto quandolen q = 0
, nesse casoE = 1
(para evitar a divisão por 0).Dissecação:
Demonstração online que simula a execução do programa com cada uma das entradas de teste, uma de cada vez.
fonte
0.1.
Python
Nenhuma biblioteca - 156 caracteres
Usando
fractions
- 127 caracteresfonte
fractions
versão imprime coisas como "Fração (7, 5)" em vez de "7/5", não é?_=lambda a,b:b and _(b,a%b)or a;a,b,c=raw_input().split('.');d,e=int(a+b+c)-bool(c)*int(a+b),
ValueError: need more than 1 value to unpack
print
usastr
quando disponível, nãorepr
. Esta é a saída do meu lado: puu.sh/7w64w.png_=lambda a,b:b and _(b,a%b)or a;a,b,c=raw_input().split('.');d,e=int(a+b+c)-bool(c)*int(a+b),(10**len(c)-bool(c))*10**len(b);f=_(d,e);print'%i/%i'%(d/f,e/f)
deve ir tudo em uma linha.Mathematica, 143
Como sempre, o Mathematica oferece muitas funções de alto nível para realizar o trabalho, mas fornece nomes detalhados.
Saída de amostra a ser adicionada mais tarde quando tiver tempo.
fonte
n/1
reduzir an
? Adicionarei ~ 50 bytes extras para converter números inteiros mais tarde.FromDigits
então eu decidi publicá-lo também.Ruby - 112
Esta é a minha primeira experiência com ruby, então fique à vontade para sugerir melhorias.
fonte
If you wish
. Eu não desejo, então não estou suportando frações sem o primeiro ou o terceiro grupo de dígitos. No entanto, estou suportando frações sem o segundo grupo de dígitos, que corresponde à especificação.C, 164
Isso é semelhante à solução C da orion, embora eu tenha feito isso do zero. Confesso, no entanto, roubar várias de suas otimizações. Não é muito mais curto, mas suporta 0,25. = 1/4 e 0.000000.1 = 1/9000000.
fonte
Duas respostas em python usando nenhuma biblioteca. Primeiro lida com a entrada opcional sem um dígito antes do primeiro. e é 162 caracteres
O segundo não lida com nada antes do primeiro dígito, mas lida com todas as entradas necessárias corretamente e tem 150 caracteres
fonte
Haskell
fonte
span
implementar s, adicionar aliases curtos para funções, remover espaço sempre que possível.import Data.Ratio v=span(/='.');w=tail;l=length;f n=(r x)%1+(r y)%p+(r z)%((10^t-1)*p)where{(x,b)=v n;(y,d)=v(w b);z=w d;p=10^(l y);r""=0;r n=read n;t=if null z then 9 else l z}
- 178 caracteres, abaixo de 321. NBTrue
é sinônimo deotherwise
,null z
élength z==0
JavaScript (ECMASCript 6)
180175Embora não seja um vencedor claro para a recompensa de 300 ... este é o menor tempo possível:
P
função Power , alterando-a para em+("1e"+a)
vez deMath.pow(10,a)
salvar mais alguns caracteres ...fonte
Mathematica 175
A maior parte da rotina vai para massagear a entrada. Aproximadamente 50 caracteres foram para manipulação de números inteiros.
Exemplos
Mais exemplos:
Como isso normalmente seria realizado no Mathematica
FromDigits
pode obter uma fração diretamente de um decimal recorrente e de repetição, desde que a entrada tenha uma forma específica. Inteiros são exibidos como inteiros.fonte
J (96 caracteres)
Eu não uso o símbolo de barra como separador (mas a solução no Mathematica também não usa, pois usa uma representação gráfica que é melhor de qualquer maneira); em linguagem J a fracção é exibida com
r
em vez de/
:fonte
APL (não totalmente geral)
Não é totalmente geral (como minha solução para dc); funciona com o Dyalog APL (mas não na versão online do Dyalog APL, não sei por que):
O primeiro campo é opcional, mas pelo menos um dígito é necessário para os outros dois campos.
fonte
JavaScript (189)
Exemplo:
Entrada:
Saída:
fonte
C (420 caracteres conforme gravado; menos após remover espaços em branco desnecessários)
Observe que isso assume 64 bits
long
(por exemplo, Linux de 64 bits); falhará no caso de teste0.2.283950617
em sistemas que usam 32 bitslong
. Isso pode ser corrigido com o custo de alguns caracteres, alterando o tipolong long
e alterando aprintf
sequência de formatação de acordo.fonte
'0'
para48
.switch
declaração comoif(c==46) n[++i]=1; else d[i]=10*d[i]+c-48,n[i]*=10;
.GTB , 81
Exemplo
fonte
GTB
link acima se você não acredita em mim. Você obterá algumas informações compactadas para um programa proprietário, depois pesquisará esse programa e descobrirá que o site que pretende fornecer um download diz que não está disponível. Então, como podemos compilá-lo?