Visão global:
Da Wikipedia : Uma fração egípcia é a soma de frações unitárias distintas. Ou seja, cada fração da expressão tem um numerador igual a 1 e um denominador que é um número inteiro positivo, e todos os denominadores diferem entre si. O valor de uma expressão desse tipo é um número racional positivo a / b. Todo número racional positivo pode ser representado por uma fração egípcia.
Desafio:
Escreva a função mais curta que retornará os valores de todos os denominadores para o menor conjunto de frações de unidades que somam uma determinada fração.
Regras / restrições:
- A entrada terá dois valores inteiros positivos.
- Isto pode ser on
STDIN
,argv
, separados por vírgula, espaço delimitado, ou qualquer outro método que você preferir.
- Isto pode ser on
- O primeiro valor de entrada deve ser o numerador e o segundo valor de entrada o denominador.
- O primeiro valor de entrada deve ser menor que o segundo.
- A saída pode incluir um valor que exceda as limitações de memória do seu sistema / idioma (RAM, MAX_INT ou quaisquer outras restrições de código / sistema existentes). Se isso acontecer, basta truncar o resultado no valor mais alto possível e observe isso de alguma forma (ie
...
). - A saída deve poder manipular um valor de denominador até pelo menos 2.147.483.647 (2 31 -1, assinado em 32 bits
int
).- Um valor mais alto (
long
, etc.) é perfeitamente aceitável.
- Um valor mais alto (
- A saída deve ser uma lista de todos os valores dos denominadores do menor conjunto de frações unitárias encontradas (ou das próprias frações, ie
1/2
). - A saída deve ser ordenada ascendente de acordo com o valor do denominador (decrescente pelo valor da fração).
- A saída pode ser delimitada da maneira que você desejar, mas deve haver algum caractere entre eles para diferenciar um valor do outro.
- Isso é código de golfe, então a solução mais curta vence.
Exemplos:
Entrada 1:
43, 48
Saída 1:
2, 3, 16
Entrada 2:
8/11
Saída 2:
1/2 1/6 1/22 1/66
Entrada 3:
5 121
Saída 3:
33 121 363
code-golf
math
rational-numbers
Gaffi
fonte
fonte
8, 11
e2, 6, 22, 66
certo?1/2 1/6 1/22 1/66
seria preferível1/2 1/5 1/37 1/4070
para a entrada8/11
.5/121 = 1/33+1/121+1/363
aos casos de teste. Todos os programas gananciosos (incluindo o meu) fornecem 5 frações por isso. Exemplo retirado da Wikipedia .Respostas:
Lisp comum, 137 caracteres
(z 43/48) -> (2 3 16)
(z 8/11) -> (2 5 37 4070)
(z 5/121) -> (25 757 763309 873960180913 1527612795642093418846225)
Não precisa se preocupar com grandes números ou lidar com notações fracionárias!
fonte
Python 2,
169167 caracteresPega argumentos separados por vírgula no stdin e imprime uma lista python no stdout.
fonte
PHP 82 bytes
Isso pode ser mais curto, mas o numerador e o denominador atuais precisam ser mantidos como números inteiros para evitar erros de arredondamento de ponto flutuante (em vez de manter a fração atual).
Uso da amostra:
fonte
5 121
ou31 311
, ele dará a resposta errada (depois de muito tempo).C,
163177 caracteres6/6 : Finalmente, o programa agora lida corretamente com o truncamento em todos os casos. Demorou muito mais caracteres do que eu esperava, mas valeu a pena. O programa deve 100% aderir aos requisitos do problema agora.
O programa leva o numerador e o denominador na entrada padrão. Os denominadores são impressos na saída padrão, um por linha. A saída truncada é indicada imprimindo um denominador zero no final da lista:
Os denominadores no segundo exemplo somam 95485142815/107645519046, que difere de 6745/7604 em aproximadamente 1e-14.
fonte
31 311
por exemplo).31 311
estouros, mas o programa falha em sinalizá-lo.Python, 61 caracteres
Entrada de STDIN, separada por vírgula.
Saída para STDOUT, nova linha separada.
Nem sempre retorna a representação mais curta (por exemplo, para 5/121).
Caracteres contados sem novas linhas desnecessárias (ou seja, unindo todas as linhas no
while
uso;
).A fração é
a/b
.i
éb/a
arredondado, então eu sei1/i <= a/b
.Após a impressão
1/i
, substituoa/b
pora/b - 1/i
, que é(a*i-b)/(i*b)
.fonte
C, 94 bytes
Experimente Online
edit: Uma versão mais curta do código foi postada nos comentários, então eu a substituí. Obrigado!
fonte
for(i=2;n>0&&i>0;i++)
podem serfor(i=1;n>0&++i>0;)
; os suportes do loop for podem ser removidos (porque ele possui apenas oif
interior);d=d*i;
pode serd*=i;
; e eu não estou totalmente certo, mas acho que#include <stdio.h>
pode ser sem espaços:#include<stdio.h>
. Ah, e pode ser interessante ler Dicas para jogar golfe em C e Dicas para jogar golfe em todos os idiomas <Stax , 18 bytes
Execute e depure
Em cada etapa, ele tenta minimizar o numerador subseqüente . Parece funcionar, mas não posso provar.
fonte
AXIOM, 753 bytes
A idéia seria aplicar o "algoritmo ganancioso" com diferentes pontos iniciais e salvar a lista que tem tamanho mínimo. Mas nem sempre ela encontraria a solução mínima com menos difinida: "a matriz A será menor que a matriz B se e somente se A tiver poucos elementos de B, ou se o número de elementos de A for o mesmo número de elementos de B , que A é menor que B se o menor elemento de A for maior como número, que o menor elemento de B ". Ungolfed e teste
referência e números de: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html
para adicionar algo, este abaixo seria o otimizado para encontrar a fração de comprimento mínimo que possui o denominador máximo menor (e não otimizado para o comprimento)
os resultados:
Parece que muitos bons denominadores têm como divisores de fator o denominador da fração de entrada.
fonte
C,
8578 bytesMelhorado por @ceilingcat , 78 bytes:
Experimente online!
Minha resposta original, 85 bytes:
Experimente online!
Parte do crédito deve ser para Jonathan Frech , que escreveu essa solução de 94 bytes que aprimorei.
fonte
APL (NARS), 2502 bytes
Tradução do código AXIOM para esse problema, para APL, usando pela primeira vez (para mim) o tipo de fração (que é bignum ...).
103r233 significa a fração 103/233. Teste:
fonte