Considere la siguiente secuencia de números:
Enumera todas las fracciones binarias en el intervalo unitario .
(Para facilitar este desafío, el primer elemento es opcional: puede omitirlo y considerar que la secuencia comienza con 1/2).
Tarea
Escribir un programa (programa completo o una función) que ...
Elija uno de estos comportamientos:
- Entrada n, salida enésimo elemento de la secuencia (indexado 0 o indexado 1);
- Entrada n, salida primeros n elementos de la secuencia;
- No ingrese nada, envíe la secuencia de números infinitos que puede tomar de uno en uno;
Regla
- Su programa debería admitir al menos los primeros 1000 elementos;
- Puede elegir generar decimales o fracciones (incorporado, par entero, cadenas) como desee;
- La entrada / salida como dígitos binarios no está permitida en esta pregunta;
- Este es el código de golf , los códigos más cortos ganan;
- Lagunas estándar no permitidas.
Casos de prueba
input output
1 1/2 0.5
2 1/4 0.25
3 3/4 0.75
4 1/8 0.125
10 5/16 0.3125
100 73/128 0.5703125
511 511/512 0.998046875
512 1/1024 0.0009765625
Estos ejemplos se basan en una secuencia indexada en 0 con el 0 inicial incluido. Debería ajustar la entrada para adaptar su solución.
Lee mas
- OEIS A006257
- Problema de Josefo: . (Anteriormente M2216)
- 0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, ...
- OEIS A062383
- : para n > 0 , a n = 2 ⌊ l o g 2 n + 1 ⌋ o a n = 2 a ⌊ n.
- 1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, ...
A006257 (n) / A062383 (n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumera todas las fracciones binarias en el intervalo unitario [0, 1). - Fredrik Johansson, 14 de agosto de 2006
"1/2" "1/4" "1/8"...
take
n elementos de ella más tarde.int
s, o adouble
en un idioma / implementación dondedouble
usa el formato IEEE binary64 ? Espero que no te refieras a tener que analizar una cadena ASCII si queremos tomar una entrada entera. Los tipos enteros normales son binarios en lenguajes como C. ¿O quiere decir que la entrada / salida no puede ser una matriz o cadena de enteros o ceros / unos ASCII?Respuestas:
Haskell , 25 bytes
Pruébalo en línea!
Produce decimales, indexados en uno sin el término cero inicial.
Agrega 0.5 a la entrada, luego reduce a la mitad hasta que los resultados estén por debajo de 2, luego resta 1. Usar una expresión de punto libre ahorra 1 bytes
fuente
Java 10,
6864 bytes¡Primero prueba en code golf!
Opción 1: encontrar el elemento n -ésimo (indexado 1)
-4 bytes gracias a @Kevin Cruijssen
Este es un método anónimo que encuentra el n -ésimo término quitando el bit más significativo de n , duplicando y añadiendo uno, entonces dividiendo por la siguiente más alta potencia de 2.
Pruébalo en línea!
Tutorial de código:
Se editará si es necesario imprimir el valor final en lugar de devolverlo.
fuente
{}
el bucle posterior puede ser un;
lugar; puedes eliminar el espacio después dereturn
;2.0
puede ser2.
; Y cambiando den>>x!=1;x++
,1<<x
y1<<x+1
paran>>x++!=1;
,1<<x-1
,1<<x
respectivamente, que también ahorra un byte. Pruébelo en línea: 64 bytes . ¡Disfruta tu estancia!MathGolf ,
54 bytesPruébalo en línea!
Cómo se vería si el operador funcionara correctamente
Pruébalo en línea!
Explicación
Me inspiré en esta pregunta para resolver el problema, creo que mi "propia" solución tenía alrededor de 10-12 bytes.
Tenía la intención de que la ronda hasta la potencia más cercana de 2 devolviera el número en sí mismo si era un número de dos, pero debido a un error se redondea a la siguiente potencia de dos (por ejemplo, 4 -> 8 en lugar de 4 -> 4 ) Esto tendrá que arreglarse más tarde, pero ahora me ahorra un byte.
fuente
]
no sirve para otro propósito que formatear la salida, diría que no es necesario incluirlo en el recuento de bytes.Java 10,
8985706968 bytesPort of @Emigma's 05AB1E answer, so outputs decimals indefinitely as well.
-15 bytes thanks to @Arnauld.
Try it online.
Explanation:
fuente
Perl 6, 19 bytes
Try it online!
fuente
Python 3, 33 bytes
Try it online!
Outputs decimals, one-indexed without the initial zero term.
fuente
Java (JDK 10), 30 bytes
Try it online!
Returns the nth item in the sequence.
This answer is originally a succession of golfs of TCFP's Java answer. In the end, the golfs didn't look like the original answer anymore (though the math used is the same) so I decided to post the golfs as a separate answer instead of simply commenting on the TCFP's answer. So if you like this answer, go upvote TCFP's answer as well! ;-)
Intermediate golfs were:
fuente
05AB1E,
118 bytesSaved 3 bytes thanks to Kevin Cruijssen.
Try it online!
Explanation
fuente
∞
(infinite list starting at 1):∞oεDÅÉs/}˜
[1,2,4,4,8,8,8,8,16,16,...,2**n]
and prepending the correct indexed prime followed by a/
... But that wasn't working so well. Well, but not8-bytes
well. Something like9LoDÅP)ζ
.Jelly, 9 bytes
Try it online!
fuente
PowerShell, 40 bytes
Try it online!
Outputs the infinite sequence as decimal values. Given language limitations, will eventually run into precision problems, but easily handles the first 1000 entries.
Starts by setting
$i=2
, then enters afor
loop. Each iteration, we construct a range from1..$i
and pull out the odd values with|?{$_%2}
. Those are fed into their own inner loop, where we divide each to get the decimal|%{$_/$i}
. Those are left on the pipeline and output when the pipeline is flushed after everyfor
iteration. Each iteration we're simply incrementing$i
by$i*=2
to get the next go-round.fuente
Haskell,
3532 bytesEdit: -3 bytes thanks to @Delfad0r.
This is an infinite list of integer pairs.
Try it online!
fuente
Haskell, 40 bytes
Try it online!
Infinite sequence as pairs of integers (starting from
(1,2)
).Quite a bit longer than @nimi's answer, but the approach is completely different, so I decided to post it anyway.
This solution is based on the following observation.
Consider the infinite sequence{12,14,34,18,38,58,78,116,316,…}
and apply the following steps.
Notice how you get back to the sequence you started with!
The solution exploits this fact (together with Haskell's laziness) to compute the sequence
s
.fuente
Python 2 -
6866 bytes-2 bytes thanks to Kevin
Try it Online!
fuente
return 2*(n-a)
toreturn(n-a)*2
. And you could save an additional byte by using Python 2 instead of 3, soreturn
can beprint
(with parenthesis).len
andbin
instead oflog
.Python 3,
5351 bytesn
.Try it online!
fuente
def f(m=2,n=1):n<m and print(n/m)&f(m,n+2)or f(m+m)
R, 42 bytes
Try it online!
Returns a pairN=2∗(n−2⌊log2(n)⌋)+1 from the Josephus sequence and D=2⌊log2(n)⌋+1 from the other sequence. Happily we are able to re-use the denominator as the two formulas have quite a lot in common!
Denominator,Numerator
. Uses the formulafuente
Racket,
9291 bytesTry it online!
fuente
MATL, 8 bytes
Try it online!
Returns Numerator, then Denominator. Uses the same method as my R answer, although it's a bit more efficient.
Explanation, with input
5
:fuente
Shakespeare Programming Language, 426 bytes
Try it online!
Outputs the sequence infinitely as both numbers separated by a space, with each item being separated by a newline.
fuente
You be twice the sum of a cat
Python 2, 44 bytes
Try it online!
Function returns a tuple of (numerator, denominator). An input of 0 is not handled (it was optional).
fuente
return 2*n-m+1,m
can beprint-~n+n-m,m
to save 2 bytes.Excel
4828 BytesSaved 20 bytes (!) thanks to tsh
=MOD(A1+0.5,2^(INT(LOG(A1,2))))/2^INT(LOG(A1,2))Assumes value in A1, output is in decimal. If you want the output to be in fraction, you can create a custom format for the output cell as "0/###0" and it will show it as fraction.
Explanation: Difficult to explain, since there is a shortcut taken to get to this formula. Basically the numerator is a bit shift left of the input, and the denominator is the next power of 2 higher than the number input.
I originally started with Excel built in functions for BITLSHIFT and BITRSHIFT, but they will shift the entire 48 bits which is not what you want. The functions DEC2BIN (and BIN2DEC) have a limit of -512 to 511 (10 bits) so this wouldn't work. Instead I had to rebuild the number with a modulus of the original number, then times two, then add 1 (since the left digit would always be 1 before a shift).
Examples:
fuente
=(A1+0.5)/2^INT(LOG(A1,2))-1
?C++,
977571 bytes-26 bytes thanks to tsh, ceilingcat, Zacharý
Testing code :
fuente
if(!i)return 0;
since 0 is not required in the challenge.while
but tryfor
.for(;exp;)
is as same aswhile(exp)
but you can write two more other statement into it. Prefer?:
instead ofif else
, which would be shorter in most cases.(...)
aroundd-n-1
.C (gcc), 63 bytes
No input, prints infinite sequence:
Try it online!
fuente
JavaScript (ES6), 44 bytes
Returns then -th term, 1-indexed.
Try it online!
fuente
Ruby, 42 bytes
Try it online!
Prints integer pairs infinitely, starting from 1/2.
fuente
JavaScript (Node.js), 30 bytes
Try it online! 0-indexed. Started out as a port of my Batch answer but I was able to calculate in multiples of12 which saved several bytes.
fuente
Ruby, 31 bytes
Try it online!
fuente
><>,
1918 bytesUsing xnor's idea, fixed by Jo King, -1 byte by making better use of the mirrors and another -2 bytes by Jo King because the
!
was superfluous and;
is not required.Try it online!
fuente
-0.25
. Fix for the same amount of bytesWolfram Language (Mathematica), 22 bytes
Try it online!
fuente
APL (Dyalog Unicode), 15 bytes
Try it online!
Anonymous prefix lambda.
Thanks to Adám for 4 bytes and to Cows quack for 2 bytes.
How:
fuente
C# (.NET Core), 69 bytes
Try it online!
Ungolfed:
fuente