Tome un número entero positivo n como entrada y envíe (algunos de los) números decimales que se pueden crear usando n bits, ordenados de la siguiente manera:
Primero, enumere todos los números que se pueden crear con solo uno 1
, y el resto 0
en la representación binaria (ordenada), luego todos los números que se pueden crear con dos consecutivos 1
, el resto 0
, luego tres consecutivos, 1
etc.
Veamos cómo se ve esto para n = 4 :
0001 - 1
0010 - 2
0100 - 4
1000 - 8
0011 - 3
0110 - 6
1100 - 12
0111 - 7
1110 - 14
1111 - 15
Entonces, la salida para n = 4 es: 1, 2, 4, 8, 3, 6, 12, 7, 14, 15 (formato de salida opcional).
Casos de prueba:
n = 1
1
n = 2
1 2 3
n = 3
1, 2, 4, 3, 6, 7
n = 8
1, 2, 4, 8, 16, 32, 64, 128, 3, 6, 12, 24, 48, 96, 192, 7, 14, 28, 56, 112, 224, 15, 30, 60, 120, 240, 31, 62, 124, 248, 63, 126, 252, 127, 254, 255
n = 17
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 7, 14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 14336, 28672, 57344, 114688, 15, 30, 60, 120, 240, 480, 960, 1920, 3840, 7680, 15360, 30720, 61440, 122880, 31, 62, 124, 248, 496, 992, 1984, 3968, 7936, 15872, 31744, 63488, 126976, 63, 126, 252, 504, 1008, 2016, 4032, 8064, 16128, 32256, 64512, 129024, 127, 254, 508, 1016, 2032, 4064, 8128, 16256, 32512, 65024, 130048, 255, 510, 1020, 2040, 4080, 8160, 16320, 32640, 65280, 130560, 511, 1022, 2044, 4088, 8176, 16352, 32704, 65408, 130816, 1023, 2046, 4092, 8184, 16368, 32736, 65472, 130944, 2047, 4094, 8188, 16376, 32752, 65504, 131008, 4095, 8190, 16380, 32760, 65520, 131040, 8191, 16382, 32764, 65528, 131056,16383, 32766, 65532, 131064, 32767, 65534, 131068, 65535, 131070, 131071
Este es el código de golf , por lo que gana el código más corto en cada idioma .
Se recomiendan buenas explicaciones , también para soluciones en "idiomas regulares".
code-golf
sorting
base-conversion
binary
Stewie Griffin
fuente
fuente
Respuestas:
Python , 53 bytes
Pruébalo en línea!
La función recursiva genera la lista ordenada como un pedido anticipado de este árbol (ejemplo con
n=4
):Las ramas izquierdas duplican el valor, y las ramas derechas
i->i*2+1
existen y existen solo para impari
. Entonces, la caminata de pre-orden para las no hojas esT(i)=[i]+T(i*2)+i%2*T(i*2+1)
.El árbol termina en profundidad
n
, donden
está la entrada. Esto se logra disminuyendon
con cada paso hacia abajo y deteniéndose cuando es 0.Una estrategia alternativa sería terminar con valores que
i
exceden2**n
, en lugar de seguir la profundidad. Encontré que esto es un byte más:fuente
[f]
es un toque divertido, no puedo decir que haya visto eso antes.Jalea , 6 bytes
Esto califica para el bono imaginario .
Pruébalo en línea!
Cómo funciona
fuente
Ẇ
es un complemento ideal para este desafío, y se implementa para que los resultados estén en el orden correcto para este desafío. Bien hecho :-)Mathematica, 40 bytes
Cada número en la lista deseada es la diferencia de dos potencias de 2, por lo que simplemente los generamos en orden usando
Table
y luego aplanamos la lista. Creo que esto gana el bono imaginario de Stewie Griffin :)Mathematica, 35 bytes
Un puerto del algoritmo Jelly de Dennis . ¡No lo sabía
Subsequences
antes de esto! (Tampoco vi que millas habían publicado esta respuesta exacta ... ¡vota!)fuente
JavaScript (ES6),
595855 bytesUn programa completo que recibe información a través de un aviso y alerta cada número sucesivamente. Esto también califica para el bono imaginario .
Fragmento de prueba
(Nota: utiliza en
console.log
lugar dealert
)Mostrar fragmento de código
fuente
JavaScript (ES6),
5551 bytesDevuelve una lista de enteros separados por espacios.
Bono imaginario amigable.
Formateado y comentado
Casos de prueba
Mostrar fragmento de código
fuente
Python 2 ,
6461 bytes-3 bytes gracias a Dennis
Pruébalo en línea!
fuente
Mathematica, 35 bytes
fuente
Python 2 ,
656358 bytesPruébalo en línea!
fuente
(2<<i)-1<<j
... y ya lo has descubierto. ¡Gran trabajo! Además, buen trabajo para deshacerse de los rangos doblesHaskell , 37 bytes
Pruébalo en línea!
fuente
Haskell, 47 bytes
Ejemplo de uso:
f 4
->[1,2,4,8,3,6,12,7,14,15]
. Pruébalo en línea! .Cómo funciona: para cada número
b
en[1..n]
, comenzar con2^b-1
y doblar varias veces el valor y tomarn-b+1
elementos de esta lista.fuente
05AB1E , 6 bytes
Pruébalo en línea! o como un conjunto de pruebas
Explicación
Utiliza el truco de la suma de sublistas como se muestra en la respuesta de Dennis 'Jelly
fuente
Groovy,
9089 bytesLa conversión binaria es tan tonta en groovy.
-1 gracias a Gurupad Mamadapur
fuente
{(1..<2**it)...
Guarda un byte.Pyth, 7 bytes
Pruébalo en línea.
Utiliza el algoritmo de Dennis.
fuente
Utilidades Bash + Unix, 51 bytes
Pruébalo en línea!
La entrada n se pasa en un argumento.
Use seq para imprimir todos los números con no menos dígitos. (Estos son números de base 10, por lo que hay muchos números adicionales aquí. Es un desperdicio y consume mucho tiempo, ¡pero este es el código golf!)
La llamada a grep mantiene solo aquellos números que consisten precisamente en 1s seguidos de 0s.
Luego use sort -r para ordenarlos en orden lexicográfico inverso.
Finalmente, dc se establece en la entrada de base 2: empuja los números ordenados en una pila y luego imprime la pila de arriba a abajo. (Esto imprime el último elemento empujado primero, etc., por eso estoy usando sort -r en lugar de simplemente ordenar).
Se corrigió un error: había omitido la opción -f% .f a seq, que se requiere para el recuento de enteros desde 1000000 en adelante. (Gracias a @TobySpeight por señalar que hubo un problema).
fuente
dc<<<2i`seq $[10**7-1]|grep ^1*0*$|sort -r`f | wc -
solo informa 12 valores. Creo que quieres en sugrep ^1[01]*$
lugar.Mathematica / Mathics , 69 bytes
Pruébalo en línea!
fuente
Perl 6 , 38 bytes
Cómo funciona
Es decir, construye los números así:
El código:
Perl 6 , 44 bytes
Este fue mi primer enfoque antes de pensar en la solución de cambio de bits (en realidad más simple) anterior.
Cómo funciona
Es decir, construye los números así:
fuente
Haskell
5946 BytesEmpecé con
f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]
de la respuesta anterior de nimi obtuvo la idea que
sum.map(2^)$[0..x]
se puede condensar a2^x-1
Terminando con
e n=[1..n]>>= \x->map(\y->2^y*(2^x-1))[0..n-x]
[1..n] - lista con el número de bits consecutivos que queremos recorrer`
>> = - traducido completamente para cada elemento en la lista de la izquierda, pásalo a la función de la derecha y concatena todos los resultados
\ x -> - declaración de función lambda con un argumento
map xy : aplica la función x a todos los miembros de la lista y
En nuestro caso x = (\ y-> 2 ^ y * (2 ^ x-1)) - otra función lambda 2 ^ y * (2 ^ x-1)). Esta fórmula surge de la multiplicación por dos agregando un cero a la derecha en binario (ejemplo 0001 a 0010). 2 ^ x - 1 es el número de bits con los que estamos trabajando. entonces para 11 tenemos 2 ^ 0 * 3 (es decir, no cambiar en absoluto) == 0011, luego 2 ^ 1 * 3 = 0110 luego 2 ^ 2 * 3 - 1100.
[0..nx] Construye la lista de cuántas veces podemos cambiar los bits. Si estamos trabajando con un solo 1, entonces mirando 0001 queremos cambiar 3 veces (4-1). Si estamos trabajando dos 11 queremos 4-2 y así sucesivamente.
fuente
Python 3, 59 bytes
Nota: esto se hizo independientemente de las soluciones de ovs y Dennis , aunque es muy similar a ambas.
Cómo funciona:
Pruébalo en línea!
¡Las propinas (codificación y efectivo) son siempre bienvenidas!
fuente
Japt , 11 bytes
¡Pruébelo en línea!
Explicación
Esto usa más o menos el enfoque de @ Dennis:
fuente
Python ,
6159 bytesPruébalo en línea!
fuente
PHP,
59 5653 bytestoma entrada de STDIN; correr con
-R
.Descompostura
fuente
$argn
Muy buena idea. Después de leer la pregunta, tengo en mi cabeza una solución con más de 200 BytesJ , 19 bytes
Esto usa el mismo método en @Dennis ' solución de .
Pruébalo en línea!
Explicación
fuente
Python 3, 91 bytes
Programa completo, con salida separada por comas y espacios, como se especifica.
Explicación:
La notación en estrella desempaqueta listas. Entonces
print(*[1,2,3])
es lo mismo queprint(1,2,3)
. Pase alint()
constructor una cadena de '1' consecutivos.-~b
evalúa ab+1
, pero no tiene que rodearlo con corchetes al multiplicar una cadena.Bitshift el número entero producido un número creciente de veces.
print()
tiene el argumento opcional sep, que especifica la cadena que se colocará entre cada elemento en una lista desempaquetada.fuente
Java 7, 108 bytes
Duplica el valor inicial siempre que el resultado sea menor que
2^n
. Luego, actualiza el valor inicial a ser(initial_value * 2) + 1
y comienza de nuevo desde allí hasta que finalmente alcanza(2^n)-1
.por ejemplo para
n=4
:Pruébalo en línea!
fuente
Ruby, 50 bytes.
Intenté algunos enfoques "inteligentes", pero este parece ser el más corto (literalmente, siga las instrucciones)
Explicación:
Cada iteración comienza con 2 ^ n-1 y se multiplica por 2 hasta alcanzar el límite superior. Nada lujoso, solo matemática básica.
fuente
QBIC , 37 bytes - bonificación imaginaria = todavía 37 bytes ...
Es una pena que aún no haya incorporado
while-wend
QBIC ... Explicación:EDITAR: QBIC ahora tiene soporte para
WHILE
:¡Esto es solo 26 bytes! Aquí está el
WHILE
:fuente
MATL,
1918 bytes1 byte guardado gracias a @Luis
Pruébalo en línea
fuente
R ,
694846 bytesCada número decimal correspondiente a
i in 1..n
unos en el sistema binario se multiplica por2^(0..n-i)
, es decir, las primerasn-i+1
potencias de dos (1, 2, 4, ...).Pruébalo en línea!
fuente
Stax , 9 bytes
Ejecutar y depurar en línea!
Explicación
Bueno, no hay conversión de base aquí.
Utiliza la versión desempaquetada (10 bytes) para explicar.
fuente
Lote, 92-0 = 92 bytes
Restando 0 para la bonificación imaginaria de @ StewieGriffin.
fuente