Historia
Así que tengo un libro que quiero separar de mi mesa con nada más que otros libros. Quiero saber cuántos libros necesito para lograr esto con longitudes de libros.
Aquí hay una visualización que mi amigo de Wolfram dibujó para mí:
Más información sobre el tema en Wolfram y Wikipedia .
Reto
Dado un número entero de entrada , salida de cuántos libros necesarios para el libro de arriba a ser n extensión de un libro fuera de la mesa horizontal. o
Encuentre el valor entero más pequeño de m para la entrada n en la siguiente desigualdad.
m ∑ i = 1 1
Editar: para fracciones, use al menos un punto flotante de precisión simple IEEE. perdón por el desafío de edición después de publicar
( OEIS A014537 )
Casos de prueba
1 4
2 31
3 227
5 12367
10 272400600
Respuestas:
Octava ,
414033 bytes1 byte guardado gracias a @Dennis
Pruébalo en línea!
Explicación
Esto utiliza el hecho de que los números armónicos pueden estar limitados por una función logarítmica.
Además, la
>=
comparación se puede reemplazar>
porque los números armónicos no pueden ser enteros (¡gracias, @Dennis!).fuente
Python 3 , 35 bytes
Pruébalo en línea!
fuente
Casco , 8 bytes
Pruébalo en línea!
Dado que Husk usa números racionales cuando puede, esto no tiene problemas de coma flotante
Explicación
fuente
JavaScript, 30 bytes
Una función recursiva, por lo que terminará bastante temprano.
Pruébalo en línea
fuente
Haskell, 38 bytes
fuente
Rápido , 65 bytes
Pruébalo en línea!
Sin golf
fuente
R , 39 bytes
Pruébalo en línea!
¡Fuerza bruta!
fuente
Javascript (ES6), 34 bytes
Sin golf
Casos de prueba
Mostrar fragmento de código
fuente
eval
declaración?eval
lai
necesitaría ser variablesreturn
ed al final, a costa de unos cuantos bytes.Jalea , 8 bytes
Esto es muy lento
Pruébalo en línea!
fuente
Haskell,
714948 bytes¡@BMO me ahorró la friolera de 22 bytes!
fuente
Julia 0.6 ,
3027 bytesPruébalo en línea!
Solo funciona
n = 6
, porque Julia no tiene una optimización de llamadas de cola.-3 bytes gracias a Dennis .
fuente
TI-BASIC, 27 bytes
Solicita al usuario la entrada y muestra la salida al finalizar. Nota:
⁻¹
es el token -1 (inverso).fuente
Ans
deN
inmediato, entoncesInput N
oPrompt N
es un método de entrada que le ahorra un byteAns→N
. YM
puede ser sustituido porAns
, por lo que1→M
se hace1
yM+1→M
se haceAns+1
. (Pero soy escéptico acerca de una salidaAns
que no se muestra, vea esto , así que tal vez terminar con:Ans
es apropiado: entonces el valor se mostrará en lugar de "Listo".)Ans→N
sentía divertido. Buenas optimizaciones. También tomé tu consejo sobre la salida solo para estar seguro. Todavía sale con una red -3 bytes: D05AB1E , 11 bytes
Pruébalo en línea!
Explicación
fuente
Pyth , 10 bytes
Pruébalo en línea!
Extremadamente lento
Pyth , 10 bytes
Pruébalo en línea!
fuente
Japt , 12 bytes
La misma longitud que, pero un poco más eficiente que la opción recursiva.
Intentalo
Explicación
fuente
J, 22 bytes
-6 bytes gracias a frownyfrog
Pruébalo en línea!
respuesta original
La respuesta de Luis en J:
Sin golf
Principalmente curioso por ver si se puede mejorar drásticamente ( tos millas de paginación para la )
Explicación
Pruébalo en línea!
fuente
1+]i.~[:<.
->1+]I.~
->I.~0,
I.~0+/\@,
PHP, 35 bytes
Ejecútelo usando la CLI:
fuente
Wolfram Language (Mathematica) , 40 bytes
Pruébalo en línea!
fuente
Java 8, 49 bytes
Explicación:
Pruébalo en línea. (Se agota el tiempo de espera para los casos de prueba anteriores
n=7
).fuente
tinylisp , 98 bytes
La última línea es una función lambda sin nombre que toma el número de libros y devuelve el número de libros necesarios. Pruébalo en línea!
Explicación
El único tipo de datos numéricos que tiene tinylisp son los enteros, por lo que calculamos la serie armónica como una fracción haciendo un seguimiento del numerador y el denominador. En cada paso,
N
es el numerador,D
es el denominador yk
es el índice de suma. Queremos que la nueva suma parcial seaN/D + 1/k
, o(N*k + D)/(D*k)
. Por lo tanto, recurrimos con un nuevo numerador deN*K + D
, un nuevo denominador deD*k
y un nuevo índice dek+1
.La recursión debería detenerse una vez que la suma parcial sea mayor o igual que
#
el número deseado de libros. En este punto, hemos ido un libro demasiado lejos, así que volvemosk-1
. La condicion es1/2 * N/D < #
; multiplicando el denominador, obtenemosN < D*#*2
, que es la forma más elegante de escribirlo.La función auxiliar recursiva
_
hace todos estos cálculos; la función principal es simplemente un argumento de un envoltorio que las llamadas_
con los valores de partida correctos parak
,N
yD
.fuente