algorithm - traductor - tabla de numeros binarios
Algoritmo para calcular el número de 1s para un rango de números en binario (5)
Creo que es un problema en Matemáticas discretas,
asumiendo que BAJA es 0,
de lo contrario, podemos insertar una función para sumar números debajo de BAJO,
a partir de los números mostrados, entiendo que el número más largo constará de hasta 60 dígitos binarios como máximo
alg(HIGH,k)
l=len(HIGH)
sum=0;
for(i=0;i<l;i++)
{
count=(l choose i);
nwia=numbers_with_i_above(i,HIGH);
if canreach(i,k) sum+=(count-nwia);
}
todos los números aparecen
no aparece dos veces
numbers_with_i_above es trivial
Canreach con números hasta 60 es fácil
len es la longitud de una representación binaria
Así que acabo de regresar para la competencia de Programación ACM y lo hice bastante bien, pero hubo un problema que no tuvo un equipo.
El problema.
Comience con un entero N0 que sea mayor que 0. Sea N1 el número de unos en la representación binaria de N0. Entonces, si
N0 = 27,N1 = 4. Para todoi > 0, sea Ni el número de unos en la representación binaria deNi-1. Esta secuencia siempre converge a una. Para cualquier número inicial, N0, sea K el valor mínimo de i> = 0 para el cual N1 = 1. Por ejemplo, si N0 = 31, entonces N1 = 5, N2 = 2, N3 = 1, entonces K = 3.Dado un rango de números consecutivos y un valor de X, ¿cuántos números en el rango tienen un valor K igual a X?
Entrada
Habrá varios casos de prueba en la entrada. Cada caso de prueba constará de tres enteros en una sola línea:LO HI X
DondeLOyHI(1 <=LO<=HI<= 10 ^ 18) son los límites inferior y superior de un rango de números enteros, yX(0 <=X<= 10) es el valor objetivo para K. La entrada terminará con una línea de tres ceros.Salida
Para cada caso de prueba se genera un entero único, que representa el número de enteros en el rango deLOaHI(inclusive) que tienen un valor de K igual a X en la entrada. Imprima cada entero en su propia línea sin espacios. No imprima ninguna línea en blanco entre las respuestas.
Entrada de muestra
31 31 3
31 31 1
27 31 1
27 31 2
1023 1025 1
1023 1025 2
0 0 0
Muestra de salida
1
0
0
3
1
1
Si quieren, puedo incluir nuestra respuesta o nuestro problema, porque encontrar un rango pequeño es fácil, pero les daré una pista antes de que su programa se ejecute en segundos, no en minutos. Tuvimos una solución exitosa pero no un algoritmo eficiente para usar un rango similar a
48238 10^18 9
De todos modos, buena suerte y si a la comunidad le gusta esto, tenemos algo más que no podríamos resolver que podría ser un buen rompecabezas para ustedes. La competencia le permite usar Python, C ++ o Java; los tres son aceptables en una respuesta.
Así que como sugerencia, mi entrenador me dijo que pensara en cómo cuentan los números binarios en lugar de revisar cada bit. Creo que eso nos acerca mucho más.
Creo que una clave es primero entender el patrón de valores K y qué tan rápido crece. Básicamente, tienes:
K(1) = 0
K(X) = K(bitcount(X))+1 for X > 1
Entonces, al encontrar los valores X más pequeños para un K dado, vemos
K(1) = 0
K(2) = 1
K(3) = 2
K(7) = 3
K(127) = 4
K(170141183460469231731687303715884105727) = 5
Entonces para un ejemplo como 48238 10^18 9 la respuesta es trivialmente 0. K = 0 solo para 1, y K = 1 solo para potencias de 2, entonces en el rango de interés, prácticamente solo veremos los valores K de 2, 3 o 4, y nunca ves K> = 5
editar
Bien, entonces estamos buscando un algoritmo para contar el número de valores con K = 2,3,4 en un rango de valor LO..HI sin iterar sobre el rango completo. Entonces, el primer paso es encontrar el número de valores en el rango con bitcount (x) == i para i = 1..59 (ya que solo nos importan los valores de hasta 10 ^ 18 y 10 ^ 18 <2 ^ 60) . Así que divida el rango lo..hi en subrangos que son una potencia de 2 tamaños y se diferencian solo en sus n bits más bajos, un rango de la forma x * (2 ^ n) .. (x + 1) * (2 ^ n) -1. Podemos desglosar el rango arbitray lo..hi en tales subrangos fácilmente. Para cada subrango, habrá valores de elegir (n, i) con i + bitcount (x) establecer bits. Así que solo sumamos todos los subintervalos para obtener un vector de conteos de 1..59, que luego repetimos, sumando esos elementos con el mismo valor K para obtener nuestra respuesta.
editar (arreglado nuevamente para ser compatible con C89 y trabajar para lo = 1 / k = 0)
Aquí hay un programa C para hacer lo que describí anteriormente:
#include <stdio.h>
#include <string.h>
#include <assert.h>
int bitcount(long long x) {
int rv = 0;
while(x) { rv++; x &= x-1; }
return rv; }
long long choose(long long m, long long n) {
long long rv = 1;
int i;
for (i = 0; i < n; i++) {
rv *= m-i;
rv /= i+1; }
return rv; }
void bitcounts_p2range(long long *counts, long long base, int l2range) {
int i;
assert((base & ((1LL << l2range) - 1)) == 0);
counts += bitcount(base);
for (i = 0; i <= l2range; i++)
counts[i] += choose(l2range, i); }
void bitcounts_range(long long *counts, long long lo, long long hi) {
int l2range = 0;
while (lo + (1LL << l2range) - 1 <= hi) {
if (lo & (1LL << l2range)) {
bitcounts_p2range(counts, lo, l2range);
lo += 1LL << l2range; }
l2range++; }
while (l2range >= 0) {
if (lo + (1LL << l2range) - 1 <= hi) {
bitcounts_p2range(counts, lo, l2range);
lo += 1LL << l2range; }
l2range--; }
assert(lo == hi+1); }
int K(int x) {
int rv = 0;
while(x > 1) {
x = bitcount(x);
rv++; }
return rv; }
int main() {
long long counts[64];
long long lo, hi, total;
int i, k;
while (scanf("%lld%lld%d", &lo, &hi, &k) == 3) {
if (lo < 1 || lo > hi || k < 0) break;
if (lo == 0 || hi == 0 || k == 0) break;
total = 0;
if (lo == 1) {
lo++;
if (k == 0) total++; }
memset(counts, 0, sizeof(counts));
bitcounts_range(counts, lo, hi);
for (i = 1; i < 64; i++)
if (K(i)+1 == k)
total += counts[i];
printf("%lld/n", total); }
return 0; }
que funciona bien para valores de hasta 2 ^ 63-1 (LONGLONG_MAX). Para 48238 1000000000000000000 3 da 513162479025364957 , lo que ciertamente parece plausible
editar
dando las entradas de
48238 1000000000000000000 1
48238 1000000000000000000 2
48238 1000000000000000000 3
48238 1000000000000000000 4
da salidas de
44
87878254941659920
513162479025364957
398959266032926842
Esos se suman a 99999999999999951763 que es correcto. El valor para k = 1 es correcto (hay 44 potencias de dos en ese rango 2 ^ 16 hasta 2 ^ 59). Entonces, aunque no estoy seguro de que los otros 3 valores sean correctos, ciertamente son plausibles.
La idea detrás de esta respuesta puede ayudarlo a desarrollar una solución muy rápida. Tener rangos de 0..2 ^ N la complejidad de un algoritmo potencial sería O (N) en el peor de los casos (suponiendo que la complejidad de una aritmética larga es O (1)) Si se programa correctamente, debería manejar fácilmente N = 1000000 en una cuestión de milisegundos.
Imagina que tenemos los siguientes valores:
LO = 0; (0000000000000000000000000000000)
HI = 2147483647; (1111111111111111111111111111111)
El N1 más bajo posible en el rango LO..HI es 0 El N1 más alto posible en el rango LO..HI es 31
Entonces, el cálculo de la parte N2..NN se hace solo para uno de 32 valores (es decir, 0..31). Lo cual se puede hacer simplemente, incluso sin una computadora. Ahora calculemos la cantidad de N1 = X para un rango de valores LO..HI
Cuando tenemos X = 0 tenemos cuenta (N1 = X) = 1 este es el siguiente valor:
1 0000000000000000000000000000000
Cuando tenemos X = 1 tenemos cuenta (N1 = X) = 31 estos son los siguientes valores:
01 1000000000000000000000000000000
02 0100000000000000000000000000000
03 0010000000000000000000000000000
...
30 0000000000000000000000000000010
31 0000000000000000000000000000001
Cuando tenemos X = 2 tenemos el siguiente patrón:
1100000000000000000000000000000
¿Cuántas cadenas únicas se pueden formar con 29 - ''0'' y 2 - ''1''?
Imagina que el ''1'' derecho (# 1) está circulando de izquierda a derecha, obtenemos la siguiente imagen:
01 1100000000000000000000000000000
02 1010000000000000000000000000000
03 1001000000000000000000000000000
...
30 1000000000000000000000000000001
Ahora tenemos 30 cadenas únicas mientras movemos el ''1'' (# 1) de izquierda a derecha, ahora es imposible crear una cadena única moviendo el ''1'' (# 1) en cualquier dirección. Esto significa que debemos mover ''1'' (# 2) a la derecha, también reiniciemos la posición de ''1'' (# 1) tan solo lo más izquierdo posible, obtenemos:
01 0110000000000000000000000000000
ahora hacemos el ciclo de ''1'' (# 1) una vez más
02 0101000000000000000000000000000
03 0100100000000000000000000000000
...
29 0100000000000000000000000000001
Ahora tenemos 29 cadenas únicas, continuando toda esta operación 28 veces obtenemos la siguiente expresión
count(N1=2) = 30 + 29 + 28 + ... + 1 = 465
Cuando tenemos X = 3, la imagen permanece similar pero estamos moviendo ''1'' (# 1), ''1'' (# 2), ''1'' (# 3)
Mover el ''1'' (# 1) crea 29 cadenas únicas, cuando comenzamos a mover ''1'' (# 2) obtenemos
29 + 28 + ... + 1 = 435 cadenas únicas, después de eso nos dejan procesar ''1'' (# 3) así que tenemos
29 + 28 + ... + 1 = 435
28 + ... + 1 = 406
...
+ 1 = 1
435 + 406 + 378 + 351 + 325 + 300 + 276 +
253 + 231 + 210 + 190 + 171 + 153 + 136 +
120 + 105 + 091 + 078 + 066 + 055 + 045 +
036 + 028 + 021 + 015 + 010 + 006 + 003 + 001 = 4495
Tratemos de resolver el caso general, es decir, cuando tenemos N ceros y M ones. La cantidad total de permutaciones para la cadena de longitud (N + M) es igual a (N + M)!
¡La cantidad de ''0'' duplicados en esta cadena es igual a N! La cantidad de ''1'' duplicados en esta cadena es igual a M!
recibiendo así la cantidad total de cadenas únicas formadas por N ceros y M ones es
(N + M)! 32! 263130836933693530167218012160000000
F(N, M) = ============= => ========== = ====================================== = 4495
(N!) * (M!) 3! * 29! 6 * 304888344611713860501504000000
Editar:
F(N, M) = Binomial(N + M, M)
Ahora consideremos un ejemplo de la vida real:
LO = 43797207; (0000010100111000100101011010111)
HI = 1562866180; (1011101001001110111001000000100)
Entonces, ¿cómo aplicamos nuestra fórmula única de permutaciones a este ejemplo? Dado que no sabemos cuántos ''1'' se encuentran debajo de LO y cuántos ''1'' se encuentran arriba de HI.
Así que contemos estas permutaciones por debajo de LO y por encima de HI.
Vamos a recordar cómo hicimos un ciclo de ''1'' (# 1), ''1'' (# 2), ...
1111100000000000000000000000000 => 2080374784
1111010000000000000000000000000 => 2046820352
1111001000000000000000000000000 => 2030043136
1111000000000000000000000000001 => 2013265921
1110110000000000000000000000000 => 1979711488
1110101000000000000000000000000 => 1962934272
1110100100000000000000000000000 => 1954545664
1110100010000000000000000000001 => 1950351361
Como puedes ver, este proceso de ciclo disminuye los valores decimales suavemente. Entonces, debemos contar la cantidad de ciclos hasta que alcancemos el valor HI. Pero no deberíamos contar estos valores por uno porque el peor de los casos puede generar hasta 32! / (16! * 16!) = 601080390 ciclos, en los que ciclaremos mucho tiempo :) Por lo tanto, necesitamos ciclos de ''1'' '' En seguida.
Teniendo nuestro ejemplo, nos gustaría contar la cantidad de ciclos de una transformación
1111100000000000000000000000000 => 1011101000000000000000000000000
1011101001001110111001000000100
¿Cuántos ciclos provoca la transformación?
1111100000000000000000000000000 => 1011101000000000000000000000000
?
Veamos, la transformación:
1111100000000000000000000000000 => 1110110000000000000000000000000
es igual al siguiente conjunto de ciclos:
01 1111100000000000000000000000000
02 1111010000000000000000000000000
...
27 1111000000000000000000000000001
28 1110110000000000000000000000000
Así que necesitamos 28 ciclos para transformarnos.
1111100000000000000000000000000 => 1110110000000000000000000000000
¿Cuántos ciclos necesitamos transformar?
1111100000000000000000000000000 => 1101110000000000000000000000000
realizando los siguientes movimientos que necesitamos:
1110110000000000000000000000000 28 cycles
1110011000000000000000000000000 27 cycles
1110001100000000000000000000000 26 cycles
...
1110000000000000000000000000011 1 cycle
y 1 ciclo para recibir:
1101110000000000000000000000000 1 cycle
recibiendo así 28 + 27 + ... + 1 + 1 = 406 + 1
pero hemos visto este valor anteriormente y fue el resultado de la cantidad de permutaciones únicas, que se calcularon para 2 ''1'' y 27 ''0''. Esto significa que la cantidad de ciclos mientras se mueve
11100000000000000000000000000 => 01110000000000000000000000000
es igual a mudarse
_1100000000000000000000000000 => _0000000000000000000000000011
más un ciclo adicional
así que esto significa que si tenemos M ceros y N unos y queremos mover el trozo de U ''1'' a la derecha, tendremos que realizar la siguiente cantidad de ciclos:
(U - 1 + M)!
1 + =============== = f(U, M)
M! * (U - 1)!
Editar:
f(U, M) = 1 + Binomial(U - 1 + M, M)
Ahora volvamos a nuestro ejemplo de la vida real:
LO = 43797207; (0000010100111000100101011010111)
HI = 1562866180; (1011101001001110111001000000100)
entonces, lo que queremos hacer es contar la cantidad de ciclos necesarios para realizar las siguientes transformaciones (supongamos N1 = 6)
1111110000000000000000000000000 => 1011101001000000000000000000000
1011101001001110111001000000100
esto es igual a:
1011101001000000000000000000000 1011101001000000000000000000000
------------------------------- -------------------------------
_111110000000000000000000000000 => _011111000000000000000000000000 f(5, 25) = 118756
_____11000000000000000000000000 => _____01100000000000000000000000 f(2, 24) = 301
_______100000000000000000000000 => _______010000000000000000000000 f(1, 23) = 24
________10000000000000000000000 => ________01000000000000000000000 f(1, 22) = 23
lo que resulta en 119104 ciclos "perdidos" que se encuentran por encima de HI
Con respecto a LO, en realidad no hay diferencia en la dirección en la que vamos a realizar el ciclo, por lo que para calcular LO podemos hacer el ciclo inverso:
0000010100111000100101011010111 0000010100111000100101011010111
------------------------------- -------------------------------
0000000000000000000000000111___ => 0000000000000000000000001110___ f(3, 25) = 2926
00000000000000000000000011_____ => 00000000000000000000000110_____ f(2, 24) = 301
De este modo se obtienen 3227 ciclos ''perdidos'' que se ubican debajo de LO, esto significa que
overall amount of lost cycles = 119104 + 3227 = 122331
overall amount of all possible cycles = F(6, 25) = 736281
N1 in range 43797207..1562866180 is equal to 736281 - 122331 = 613950
No proporcionaré la parte restante de la solución. No es tan difícil de comprender la parte restante. ¡Buena suerte!
Puede resolver esto de manera eficiente de la siguiente manera:
ret = 0;
for (i = 1; i <= 64; i++) {
if (computeK(i) != desiredK) continue;
ret += numBelow(HIGH, i) - numBelow(LO - 1, i);
}
return ret;
La función numBelow(high, numSet) calcula el número de enteros menor o igual que high y mayor que cero que tienen numSet bits numSet . Para implementar numBelow(high, numSet) eficiente, puede usar algo como lo siguiente:
numBelow(high, numSet) {
t = floor(lg(high));
ret = 0;
if (numBitsSet(high) == numSet) ret++;
while (numSet > 0 && t > 0) {
ret += nchoosek(t - 1, numSet);
numSet--;
while (--t > 0 && (((1 << t) & high) == 0));
}
return ret;
}
Zobgib,
La clave de este problema es no entender qué tan rápido crece el crecimiento del patrón de K, sino CÓMO crece él mismo. El primer paso en esto es entender (como dijo su entrenador) cómo cuentan los números binarios, ya que esto determina todo sobre cómo se determina K. Los números binarios siguen un patrón que es distinto cuando se cuenta el número de bits positivos. Es un solo patrón repetitivo progresivo. Voy a demostrar de una manera inusual ...
Assume i is an integer value. Assume b is the number of positive bits in i i = 1; b = 1; i = 2; 3; b = 1; 2; i = 4; 5; 6; 7; b = 1; 2; 2; 3; i = 8; 9; 10; 11; 12; 13; 14; 15; b = 1; 2; 2; 3; 2; 3; 3; 4; i = 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; b = 1; 2; 2; 3; 2; 3; 3; 4; 2; 3; 3; 4; 3; 4; 4; 5; I assure you, this pattern holds to infinity, but if needed you should be able to find or construct a proof easily.
Si observa los datos anteriores, notará un patrón distinto relacionado con 2 ^ n. Cada vez que tenga un exponente entero de 2, el patrón se reiniciará al incluir cada término del patrón anterior, y luego cada término del patrón anterior se incrementará en 1. Como tal, para obtener K, simplemente aplique el nuevo número al patrón. patrón de arriba. La clave es encontrar una sola expresión (que sea eficiente) para recibir su número de bits.
Para la demostración, una vez más, puedes extrapolar aún más un nuevo patrón de esto, porque es estático y sigue la misma progresión. A continuación se muestra la información original modificada con su valor K (basado en la recursión).
Assume i is an integer value. Assume b is the number of positive bits in i i = 1; b = 1; K = 1; i = 2; 3; b = 1; 2; K = 1; 2; i = 4; 5; 6; 7; b = 1; 2; 2; 3; K = 1; 2; 2; 3; i = 8; 9; 10; 11; 12; 13; 14; 15; b = 1; 2; 2; 3; 2; 3; 3; 4; K = 1; 2; 2; 3; 2; 3; 3; 2; i = 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; b = 1; 2; 2; 3; 2; 3; 3; 4; 2; 3; 3; 4; 3; 4; 4; 5; K = 1; 2; 2; 3; 2; 3; 3; 2; 2; 3; 3; 2; 3; 2; 2; 3;
Si lo notas, K sigue un patrón similar, con una condición especial ... Cada vez que b es una potencia de 2, en realidad baja el valor K en 2. Así que, si sigues una progresión binaria, deberías ser capaz de mapear fácilmente tus valores K Dado que este patrón depende de potencias de 2, y el patrón depende de encontrar la potencia más cercana de 2 y comenzar allí, propongo la siguiente solución. Tome su valor LOW y encuentre la potencia más cercana de 2 (p) tal que 2^p < LOW . Esto se puede hacer "contando los bits" solo por el número más bajo. Nuevamente, una vez que sepa qué exponente es, no tiene que contar los bits para ningún otro número. Simplemente se incrementa a través del patrón y obtendrá su b y, por lo tanto, K (que sigue el mismo patrón).
Nota: Si eres particularmente observador, puedes usar la b anterior o la K para determinar la siguiente. Si la corriente i es impar, agregue 1 a la b anterior. Si la corriente i es divisible por 4, entonces decrementa b por 1 o 2, dependiendo de si está en la primera mitad del patrón o en la segunda mitad. Y, por supuesto, si i un poder de 2, empiezo de nuevo en 1.
Lógica Fuzzical
Ejemplo de pseudocódigo (no optimizado)
{ var LOW, HIGH var power = 0
//Get Nearest Power Of 2 for (var i = 0 to 60) { // Compare using bitwise AND if (LOW bitAND (2 ^ i) = (2 ^ i)) { if ((2 ^ i) <= LOW) { set power to i } else { // Found the Power: end the for loop set i to 61 } } }
// Automatically 1 at a Power of 2 set numOfBits to 1 array numbersWithPositiveBits with 64 integers = 0 // Must create the pattern from Power of 2 set foundLOW to false for (var j = (2^power) to HIGH) { set lenOfPatten to (power + 1) // Don''t record until we have found the LOW value if ((foundLOW is false) bitAND (j is equal to LOW)) { set foundLOW to true } // If j is odd, increment numOfBits if ((1 bitAND j) is equal to 1) { increment numOfBits } else if (j modulus 4 == 0) { decrement numOfBits accordingly //Figure this one out yourself, please } else if ((j - (2^power)) == (power + 1)) { // We are at the next power increment power // Start pattern over set numOfBits to 1 } // Record if appropriate if (foundLOW is equal to true) { increment element numOfBits in array numbersWithPositiveBits } }
// From here, derive your K values.