Visión general:
De Wikipedia : Una fracción egipcia es la suma de fracciones unitarias distintas. Es decir, cada fracción en la expresión tiene un numerador igual a 1 y un denominador que es un entero positivo, y todos los denominadores difieren entre sí. El valor de una expresión de este tipo es un número racional positivo a / b. Cada número racional positivo puede ser representado por una fracción egipcia.
Desafío:
Escriba la función más corta que devolverá los valores de todos los denominadores para el conjunto más pequeño de fracciones unitarias que suman una fracción dada.
Reglas / Restricciones:
- La entrada será dos valores enteros positivos.
- Esto puede ser en
STDIN
,argv
, separados por una coma, el espacio delimitado, o cualquier otro método que prefiera.
- Esto puede ser en
- El primer valor de entrada será el numerador y el segundo valor de entrada el denominador.
- El primer valor de entrada será menor que el segundo.
- El resultado puede incluir uno o varios valores que exceden las limitaciones de memoria de su sistema / idioma (RAM, MAX_INT o cualquier otra restricción de código / sistema que exista). Si esto sucede, simplemente trunca el resultado al valor más alto posible y ten en cuenta que de alguna manera (es decir
...
). - La salida debe poder manejar un valor de denominador de hasta al menos 2,147,483,647 (2 31 -1, con signo de 32 bits
int
).- Un valor más alto (
long
, etc.) es perfectamente aceptable.
- Un valor más alto (
- La salida debe ser una lista de todos los valores de los denominadores del conjunto más pequeño de fracciones unitarias encontradas (o las fracciones mismas, es decir
1/2
). - La salida se ordenará ascendente de acuerdo con el valor del denominador (descendente por el valor de la fracción).
- La salida se puede delimitar de la forma que desee, pero debe haber algún carácter intermedio para diferenciar un valor del siguiente.
- Este es el código de golf, por lo que gana la solución más corta.
Ejemplos:
Entrada 1:
43, 48
Salida 1:
2, 3, 16
Entrada 2:
8/11
Salida 2:
1/2 1/6 1/22 1/66
Entrada 3:
5 121
Salida 3:
33 121 363
code-golf
math
rational-numbers
Gaffi
fuente
fuente
8, 11
y2, 6, 22, 66
¿verdad?1/2 1/6 1/22 1/66
sería preferible1/2 1/5 1/37 1/4070
para la entrada8/11
.5/121 = 1/33+1/121+1/363
a los casos de prueba. Todos los programas codiciosos (incluido el mío) dan 5 fracciones para ello. Ejemplo tomado de Wikipedia .Respuestas:
Lisp común, 137 caracteres
(z 43/48) -> (2 3 16)
(z 8/11) -> (2 5 37 4070)
(z 5/121) -> (25757 763309 873960180913 1527612795642093418846225)
¡No hay necesidad de preocuparse por números grandes o por manejar la notación fraccional!
fuente
Python 2,
169167 caracteresToma argumentos separados por comas en stdin e imprime una lista de python en stdout.
fuente
PHP 82 bytes
Esto podría hacerse más corto, pero el numerador y el denominador actuales deben mantenerse como números enteros para evitar el error de redondeo de coma flotante (en lugar de mantener la fracción actual).
Uso de la muestra:
fuente
5 121
o31 311
, dará la respuesta incorrecta (después de mucho tiempo).C,
163177 caracteres6/6 : Por fin, el programa ahora maneja correctamente el truncamiento en todos los casos. Tomó muchos más caracteres de los que esperaba, pero valió la pena. El programa debe cumplir al 100% los requisitos del problema ahora.
El programa toma el numerador y el denominador en la entrada estándar. Los denominadores se imprimen en salida estándar, uno por línea. La salida truncada se indica imprimiendo un denominador cero al final de la lista:
Los denominadores en el segundo ejemplo suman 95485142815/107645519046, que difiere de 6745/7604 en aproximadamente 1e-14.
fuente
31 311
por ejemplo).31 311
se desborda, pero el programa no puede marcarlo.Python, 61 caracteres
Entrada de STDIN, separada por comas.
Salida a STDOUT, nueva línea separada.
No siempre devuelve la representación más corta (por ejemplo, para 5/121).
Caracteres contados sin nuevas líneas innecesarias (es decir, unir todas las líneas dentro del
while
uso;
).La fracción es
a/b
.i
estáb/a
redondeado, así que lo sé1/i <= a/b
.Después de imprimir
1/i
, lo reemplazoa/b
cona/b - 1/i
, que es(a*i-b)/(i*b)
.fuente
C, 94 bytes
Pruébalo en línea
editar: se publicó una versión más corta del código en los comentarios, así que lo reemplacé. ¡Gracias!
fuente
for(i=2;n>0&&i>0;i++)
pueden serfor(i=1;n>0&++i>0;)
; los corchetes del bucle for se pueden quitar (porque solo tiene elif
interior);d=d*i;
puede serd*=i;
; y no estoy del todo seguro, pero creo que#include <stdio.h>
puede estar sin espacios:#include<stdio.h>
. Ah, y puede ser interesante leer Consejos para jugar golf en C y Consejos para jugar golf en <todos los idiomas>Stax , 18 bytes
Ejecutar y depurarlo
En cada paso, intenta minimizar el numerador posterior . Parece funcionar, pero no puedo probarlo.
fuente
AXIOM, 753 bytes
La idea sería aplicar el "Algoritmo codicioso" con diferentes puntos iniciales y guardar la lista que tiene una longitud mínima. Pero no siempre encontraría la solución mínima con menos diferido: "la matriz A será menor que la matriz B si y solo si A tiene pocos elementos de B, o si el número de elementos de A es igual al número de elementos de B , que A es menor que B si el elemento más pequeño de A es mayor como número, que el elemento más pequeño de B ". Sin golf y prueba
referencia y números de: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html
para agregar algo, este a continuación sería el optimizado para encontrar la fracción de longitud mínima que tiene el denominador máximo menos (y no está optimizado para longitud)
Los resultados:
Parece que muchos buenos denominadores tienen como divisores de factores del denominador de fracción de entrada.
fuente
C,
8578 bytesMejorado por @ceilingcat , 78 bytes:
Pruébalo en línea!
Mi respuesta original, 85 bytes:
Pruébalo en línea!
Parte del crédito debe ir a Jonathan Frech , quien escribió esta solución de 94 bytes que mejoré.
fuente
APL (NARS), 2502 bytes
Traslación del código AXIOM para este problema, a APL, utilizando por primera vez (para mí) el tipo de fracción (que es bignum ...).
103r233 significa la fracción 103/233. Prueba:
fuente