algorithm - serie - ¿Contando los bits establecidos en el sistema de números de Fibonacci?

sucesion de fibonacci ejercicios (8)

Sabemos que cada número decimal no negativo se puede representar de manera única por la suma de los números de Fibonacci (aquí nos preocupa la representación mínima, es decir, no se toman números de Fibonacci consecutivos en la representación de un número y cada número de Fibonacci se toma como máximo en la representación).

Por ejemplo:

1-> 1 2-> 10 3->100 4->101, here f1=1 , f2=2 and f(n)=f(n-1)+f(n-2);

por lo tanto, cada número decimal se puede representar en el sistema Fibonacci como una secuencia binaria. Si escribimos todos los números naturales sucesivamente en el sistema de Fibonacci, obtendremos una secuencia como esta: 110100101 ... Esto se llama "secuencia de bits Fibonacci de números naturales".

Mi tarea es contar el número de veces que aparece el bit 1 en los primeros N bits de esta secuencia. Puesto que N puede tomar valor de 1 a 10 ^ 15, ¿puedo hacer esto sin almacenar la secuencia de Fibonacci?

por ejemplo: si N es 5, la respuesta es 3.

Calcule m, el número responsable del bit (N + 1) th de la secuencia. Calcule la contribución de m al conteo.
Hemos reducido el problema a contar el número de bits en el rango [1, m). En el estilo de los árboles de intervalo , divida este rango en subrangos O (log N), cada uno con un globo asociado como 10100 ???? que coincide con las representaciones de exactamente los números que pertenecen a ese rango. Es fácil calcular la contribución de los prefijos.
Hemos reducido el problema a contar el número total T (k) de un bit en todas las palabras Fibonacci de longitud k (es decir, la ???? parte de los globs). T (k) está dada por la siguiente recurrencia.
T(0) = 0 T(1) = 1 T(k) = T(k - 1) + T(k - 2) + F(k - 2)

Mathematica dice que hay una solución de forma cerrada, pero parece horrible y no es necesaria para este algoritmo de tiempo de polilogía (N) .

Aquí está O ((log n) ^ 3).

Permite calcular cuántos números se ajustan en las primeras N bits

Imagina que tenemos una función:

long long number_of_all_bits_in_sequence(long long M);

Calcula la duración de la "secuencia de bits de Fibonacci de números naturales" creada por todos los números que no son mayores que M.

Con esta función podríamos usar la búsqueda binaria para encontrar cuántos números encajan en los primeros N bits.

¿Cuántos bits son 1 en representación de los primeros números M?

Permite crear una función que calcula cuántos números <= M tienen 1 en el k-ésimo bit.

long long kth_bit_equal_1(long long M, int k);

Primero, preprocesamos los resultados de esta función para todos los valores pequeños, digamos M <= 1000000.

Implementación para M> PREPROCESS_LIMIT:

long long kth_bit_equal_1(long long M, int k) { if (M <= PREPROCESS_LIMIT) return preprocess_result[M][k]; long long fib_number = greatest_fib_which_isnt_greater_than(M); int fib_index = index_of_fib_in_fibonnaci_sequence(fib); if (fib_index < k) { // all numbers are smaller than k-th fibbonacci number return 0; } if (fib_index == k) { // only numbers between [fib_number, M] have k-th bit set to 1 return M - fib_number + 1; } if (fib_index > k) { long long result = 0; // all numbers between [fib_number, M] have bit at fib_index set to 1 // so lets subtrack fib_number from all numbers in this interval // now this interval is [0, M - fib_number] // lets calculate how many numbers in this inteval have k-th bit set. result += kth_bit_equal_1(M - fib_number, k); // don''t forget about remaining numbers (interval [1, fib_number - 1]) result += kth_bit_equal_1(fib_number - 1, k); return result; } }

La complejidad de esta función es O (M / PREPROCESS_LIMIT).

Observe que en la recuperación uno de los sumandos es siempre uno de los números fibbonaci.

kth_bit_equal_1(fib_number - 1, k);

Entonces, si memorizamos todos los resultados computados, la complejidad mejorará a T (N) = T (N / 2) + O (1). T (n) = O (log N).

Volvamos a number_of_all_bits_in_sequence

Podemos modificar ligeramente kth_bit_equal_1 por lo que también contaría bits igual a 0.

Entonces esto es solo un boceto preliminar de un algoritmo. Funciona cuando el límite superior es en sí mismo un número de Fibonacci, pero no estoy seguro de cómo adaptarlo para los límites superiores generales. Con suerte, alguien puede mejorar esto.

La idea general es mirar la estructura de las codificaciones de Fibonacci. Aquí están los primeros números:

0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000

La invariante en cada uno de estos números es que nunca hay un par de 1 consecutivos. Dado este invariante, podemos incrementar de un número al siguiente usando el siguiente patrón:

Si el último dígito es 0, establézcalo en 1.
Si el último dígito es 1, entonces ya que no hay 1s consecutivos, establezca el último dígito en 0 y el próximo dígito en 1.
Elimine cualquier doble 1s estableciendo ambos en 0 y estableciendo el siguiente dígito en un 1, repitiendo hasta que se eliminen todos los dobles duplicados.

La razón por la que esto es importante es porque la propiedad (3) nos dice algo acerca de la estructura de estos números. Revisemos los primeros números codificados por Fibonacci una vez más. Mira, por ejemplo, en los primeros tres números:

00 01 10

Ahora, mira todos los números de cuatro bits:

1000 1001 1010

El siguiente número tendrá cinco dígitos, como se muestra aquí:

1011 → 1100 → 10000

El detalle interesante para notar es que la cantidad de números con cuatro dígitos es igual a la cantidad de valores con hasta dos dígitos. De hecho, obtenemos los números de cuatro dígitos simplemente anteponiendo los números a lo sumo de dos dígitos con 10.

Ahora, mira los números de tres dígitos:

000 001 010 100 101

Y mira los números de cinco dígitos:

10000 10001 10010 10100 10101

Observe que los números de cinco dígitos son solo números de tres dígitos con 10 prefijos.

Esto nos da una forma muy interesante de contar cuántos 1s hay. Específicamente, si nos fijamos en los números de (k + 2) dígitos, cada uno de ellos es simplemente un número de k dígitos con un 10 prefijado. Esto significa que si hay B 1 en total en todos los números de k dígitos, el número total de Bs en números que son solo k + 2 dígitos es igual a B más el número de números de k dígitos, ya que solo estamos reproduciendo la secuencia con un 1 adicional antes de cada número.

Podemos explotar esto para calcular el número de 1s en las codificaciones de Fibonacci que tienen como máximo k dígitos en ellas. El truco es el siguiente: si para cada número de dígitos hacemos un seguimiento de

¿Cuántos números tienen como máximo tantos dígitos (llame a esto N (d)), y
Cuantos 1s son números representados con un máximo de d dígitos (llame a esto B (d)).

Podemos usar esta información para calcular estas dos piezas de información para un dígito más. Es una hermosa repetición DP. Inicialmente, lo siembramos de la siguiente manera. Para un dígito, N (d) = 2 y B (d) es 1, ya que para un dígito los números son 0 y 1. Para dos dígitos, N (d) = 3 (hay solo un número de dos dígitos, 10, y los dos números de un dígito 0 y 1) y B (d) es 2 (uno de 1, uno de 10). A partir de ahí, tenemos eso

N (d + 2) = N (d) + N (d + 1). Esto se debe a que la cantidad de números con hasta +2 dígitos es la cantidad de números con hasta +1 dígitos (N (d + 1)), más los números formados por el prefijo 10 en números con d dígitos (N ( re))
B (d + 2) = B (d + 1) + B (d) + N (d) (El número total de 1 bits en números de longitud como máximo d + 2 es el número total de 1 bits en números de longitud a lo sumo d + 1, más el extra que obtenemos de números de solo d + 2 dígitos)

Por ejemplo, obtenemos lo siguiente:

d N(d) B(d) --------------------- 1 2 1 2 3 2 3 5 5 4 8 10 5 13 20

Realmente podemos verificar esto. Para números de 1 dígito, hay un total de 1 bit utilizado. Para números de 2 dígitos, hay dos (1 y 10). Para números de 3 dígitos, hay cinco 1s (1, 10, 100, 101). Para números de cuatro dígitos, hay 10 unidades (las cinco anteriores, más 1000, 1001, 1010). Extendiendo esto hacia afuera nos da la secuencia que nos gustaría.

Esto es extremadamente fácil de calcular: podemos calcular el valor para k dígitos en el tiempo O (k) con solo O (1) uso de memoria si reutilizamos el espacio de antes. Como los números de Fibonacci crecen exponencialmente rápido, esto significa que si tenemos un número N y queremos encontrar la suma de todos los bits 1 al número de Fibonacci más grande más pequeño que N, podemos hacerlo en el tiempo O (log N) y el espacio O (1)

Dicho esto, no estoy seguro de cómo adaptar esto para trabajar con límites superiores generales. Sin embargo, soy optimista de que hay alguna forma de hacerlo. Esta es una bella recurrencia y simplemente tiene que haber una buena forma de generalizarla.

¡Espero que esto ayude! Gracias por un gran problema!

Este problema tiene una solución dinámica, como se ilustra por el algoritmo probado a continuación. Algunos puntos a tener en cuenta, que son evidentes en el código:

La mejor solución para cada número i se obtendrá utilizando el número de Fibonacci f donde f == i O donde f es menor que i, entonces debe ser f y el mayor número n <= f: i = f + n.

Tenga en cuenta que la secuencia fib se memoriza sobre todo el algoritmo.

public static int[] fibonacciBitSequenceOfNaturalNumbers(int num) { int[] setBits = new int[num + 1]; setBits[0] = 0;//anchor case of fib seq setBits[1] = 1;//anchor case of fib seq int a = 1, b = 1;//anchor case of fib seq for (int i = 2; i <= num; i++) { int c = b; while (c < i) { c = a + b; a = b; b = c; }//fib if (c == i) { setBits[i] = 1; continue; } c = a; int tmp = c;//to optimize further, make tmp the fib before a while (c + tmp != i) { tmp--; } setBits[i] = 1 + setBits[tmp]; }//done return setBits; }

Prueba con:

public static void main(String... args) { int[] arr = fibonacciBitSequenceOfNaturalNumbers(23); //print result for(int i=1; i<arr.length; i++) System.out.format("%d has %d%n", i, arr[i]); }

RESULTADO DE LA PRUEBA: tengo x set bits

1 has 1 2 has 1 3 has 1 4 has 2 5 has 1 6 has 2 7 has 2 8 has 1 9 has 2 10 has 2 11 has 2 12 has 3 13 has 1 14 has 2 15 has 2 16 has 2 17 has 3 18 has 2 19 has 3 20 has 3 21 has 1 22 has 2 23 has 2

EDITAR BASADO EN COMENTARIO:

//to return total number of set between 1 and n inclusive //instead of returning as in original post, replace with this code int total = 0; for(int i: setBits) total+=i; return total;

Para resolver 3 problemas. Cada uno es más difícil que el anterior, cada uno usa el resultado del anterior.

1. Cuántas se establecen si anota cada número de 0 a fib [i] -1.

Llamar a este dp[i] . Veamos los números

0 1 10 100 101 1000 1001 1010 <-- we want to count ones up to here 10000

Si escribe todos los números hasta fib [i] -1, primero escribe todos los números hasta fib [i-1] -1 (dp [i-1]), luego escribe el último bloque de números. Hay exactamente fib [i-2] de esos números, cada uno tiene uno en la primera posición, entonces agregamos fib [i-2], y si borras esos

000 001 010

luego quite los ceros a la izquierda, puede ver que cada número de 0 a fib [i-2] -1 está anotado. El número de uno es igual a dp [i-2], lo que nos da:

dp[i] = fib[i-2] + dp[i-2] + dp[i-1];

2. Cuántas se establecen si anota cada número de 0 a n.

0 1 10 100 101 1000 1001 <-- we want to count ones up to here 1010

Permite llamar a este solNumber(n)

Supongamos que su número es f [i] + x, donde f [i] es un número de Fibonacci máximo posible. Entonces anser si dp [i] + solNumber (x). Esto se puede probar de la misma manera que en el punto 1.

3. Cuántas se establecen en los primeros n dígitos.

3a. ¿Cuántos números tienen longitud de representación exactamente?

si l = 1 la respuesta es 1, de lo contrario es fib [l-2] + 1. Puedes notar que si borras los principales y luego todos los ceros iniciales tendrás cada número de 0 a fib [l-1] -1. Exactamente Fib [l] números.

// Fin de 3a

Ahora puede encontrar ese número m que, si escribe todos los números de 1 a m, su longitud total será <= n. Pero si escribe todo de 1 a m + 1, la longitud total será> n. Resuelve el problema manualmente para m + 1 y agrega solNumber (m).

Los 3 problemas se resuelven en O (log n)

#include <iostream> using namespace std; #define FOR(i, a, b) for(int i = a; i < b; ++i) #define RFOR(i, b, a) for(int i = b - 1; i >= a; --i) #define REP(i, N) FOR(i, 0, N) #define RREP(i, N) RFOR(i, N, 0) typedef long long Long; const int MAXL = 30; long long fib[MAXL]; //How much ones are if you write down the representation of first fib[i]-1 natural numbers long long dp[MAXL]; void buildDP() { fib[0] = 1; fib[1] = 1; FOR(i,2,MAXL) fib[i] = fib[i-1] + fib[i-2]; dp[0] = 0; dp[1] = 0; dp[2] = 1; FOR(i,3,MAXL) dp[i] = fib[i-2] + dp[i-2] + dp[i-1]; } //How much ones are if you write down the representation of first n natural numbers Long solNumber(Long n) { if(n == 0) return n; Long res = 0; RREP(i,MAXL) if(n>=fib[i]) { n -= fib[i]; res += dp[i]; res += (n+1); } return res; } int solManual(Long num, Long n) { int cr = 0; RREP(i,MAXL) { if(n == 0) break; if(num>=fib[i]) { num -= fib[i]; ++cr; } if(cr != 0) --n; } return cr; } Long num(int l) { if(l<=2) return 1; return fib[l-1]; } Long sol(Long n) { //length of fibonacci representation int l = 1; //totatl acumulated length int cl = 0; while(num(l)*l + cl <= n) { cl += num(l)*l; ++l; } //Number of digits, that represent numbers with maxlength Long nn = n - cl; //Number of full numbers; Long t = nn/l; //The last full number n = fib[l] + t-1; return solNumber(n) + solManual(n+1, nn%l); } int main(int argc, char** argv) { ios_base::sync_with_stdio(false); buildDP(); Long n; while(cin>>n) cout<<"ANS: "<<sol(n)<<endl; return 0; }

Aquí hay una manera de contar todos los dígitos de un conjunto de números hasta un límite de longitud de un dígito dado. Esto me parece ser un punto de partida razonable para una solución

Considera 10 dígitos. Comience por escribir;

0000000000

Ahora podemos convertir algunos de estos ceros en unos, manteniendo el último dígito siempre como 0. Considere las posibilidades caso por caso.

0 Solo hay una forma de elegir 0 de estos para ser uno. Al sumar los 1 bits en este caso, se obtiene 0.

1 Hay {9 elegir 1} formas de convertir uno de los ceros en uno. Cada uno de estos contribuye 1.

2 Hay {8 elegir 2} formas de convertir dos de los ceros en unos. Cada uno de estos contribuye 2.

...

5 Hay {5 elegir 5} formas de convertir cinco de los ceros en unos. Cada uno de estos contribuye 5 al conteo de bits.

Es fácil pensar en esto como un problema de mosaico. La cadena de 10 ceros es una tabla de 10x1, que queremos combinar con cuadrados de 1x1 y dominós 2x1. Elegir un número de ceros para ser uno es lo mismo que elegir que algunas fichas sean fichas de dominó. Mi solución está estrechamente relacionada con Identity 4 en "Pruebas que realmente cuentan" por Benjamin y Quinn.

Segundo paso Ahora intenta usar la construcción anterior para resolver el problema original

Supongamos que queremos los bits uno en los primeros 100100010 bits (el número está en representación de Fibonacci, por supuesto). Comience por contar de más la suma de todas las maneras para reemplazar las x con ceros y unos en 10xxxxx0. Para sobrecompensar el conteo excesivo, restar el recuento de 10xxx0. Continúe con el procedimiento de sobrecuento y compensación excesiva.

Esta no es una respuesta completa, pero describe cómo puede hacer este cálculo sin usar la fuerza bruta.

La representación Fibonacci de Fn es un 1 seguido de n-1 ceros.

Para los números desde Fn hasta, pero sin incluir, F(n+1) , el número de 1 consta de dos partes:

Hay F(n-1) tales números, entonces hay F(n-1) lideran 1.
Los dígitos binarios después de los números iniciales son solo las representaciones binarias de todos los números hasta, pero sin incluir, F(n-1) .

Entonces, si llamamos al número total de bits en la secuencia hasta, pero sin incluir, el nth número de Fibonacci an , entonces tenemos la siguiente recursión:

a(n+1) = an + F(n-1) + a(n-1)

También puede obtener fácilmente el número de bits en la secuencia hasta Fn .

Si se necesitan k números de Fibonacci para llegar a (pero no pasar) N , entonces puede contar esos bits con la fórmula anterior, y después de alguna manipulación adicional, reducir el problema para contar el número de bits en la secuencia restante.

[Editar]: Básicamente he seguido la propiedad de que para cualquier número n que se represente en la base de Fibonacci, podemos romperlo como n = n - x donde x es el fibonacci más grande menos que n . Usando esta propiedad, cualquier número se puede romper en forma de bit.

El primer paso es encontrar el número decimal de modo que el bit Nth termine en él. Podemos ver que todos los números entre el número F(n) y F(n+1) Fibonacci tendrán el mismo número de bits. Al usar esto, podemos precalcular una tabla y encontrar el número apropiado.

Digamos que tienes el número decimal D en el que está el Nth bit. Ahora, deje que X sea el número más grande de fibonacci menor o igual a D Para encontrar los bits establecidos para todos los números de 1 a D lo representemos como ... X+0, X+1, X+2, .... X + DX . Entonces, todas las X serán repuestas por 1 al final y hemos dividido el problema en un sub-problema mucho más pequeño. Es decir, tenemos que encontrar todos los bits configurados hasta DX . Seguimos haciendo esto recusivamente. Usando la misma lógica, podemos construir una tabla que tenga un número apropiado de bits de conjunto para todos los números de Fibonacci (hasta el límite). Usaremos esta tabla para encontrar el número de bits configurados de 1 a X Asi que,

Findsetbits(D) { // finds number of set bits from 1 to D. find X; // largest fibonacci number just less than D ans = tablesetbits[X]; ans += 1 * (D-x+1); // All 1s at the end due to X+0,X+1,... ans += Findsetbits(D-x); return ans; }

Probé algunos ejemplos a mano y vi el patrón.

He codificado una solución aproximada que he comprobado a mano para N <= 35. Funciona bastante rápido para números grandes, aunque no puedo estar seguro de que sea correcta. Si se trata de un problema de juez en línea, proporcione el enlace.

#include<iostream> #include<vector> #include<map> #include<algorithm> using namespace std; #define pb push_back typedef long long LL; vector<LL>numbits; vector<LL>fib; vector<LL>numones; vector<LL>cfones; void init() { fib.pb(1); fib.pb(2); int i = 2; LL c = 1; while ( c < 100000000000000LL ) { c = fib[i-1] + fib[i-2]; i++; fib.pb(c); } } LL answer(LL n) { if (n <= 3) return n; int a = (lower_bound(fib.begin(),fib.end(),n))-fib.begin(); int c = 1; if (fib[a] == n) { c = 0; } LL ans = cfones[a-1-c] ; return ans + answer(n - fib[a-c]) + 1 * (n - fib[a-c] + 1); } int fillarr(vector<int>& a, LL n) { if (n == 0)return -1; if (n == 1) { a[0] = 1; return 0; } int in = lower_bound(fib.begin(),fib.end(),n) - fib.begin(),v=0; if (fib[in] != n) v = 1; LL c = n - fib[in-v]; a[in-v] = 1; fillarr(a, c); return in-v; } int main() { init(); numbits.pb(1); int b = 2; LL c; for (int i = 1; i < fib.size()-2; i++) { c = fib[i+1] - fib[i] ; c = c*(LL)b; b++; numbits.pb(c); } for (int i = 1; i < numbits.size(); i++) { numbits[i] += numbits[i-1]; } numones.pb(1); cfones.pb(1); numones.pb(1); cfones.pb(2); numones.pb(1); cfones.pb(5); for (int i = 3; i < fib.size(); i++ ) { LL c = 0; c += cfones[i-2]+ 1 * fib[i-1]; numones.pb(c); cfones.pb(c + cfones[i-1]); } for (int i = 1; i < numones.size(); i++) { numones[i] += numones[i-1]; } LL N; cin>>N; if (N == 1) { cout<<1<<"/n"; return 0; } // find the integer just before Nth bit int pos; for (int i = 0;; i++) { if (numbits[i] >= N) { pos = i; break; } } LL temp = (N-numbits[pos-1])/(pos+1); LL temp1 = (N-numbits[pos-1]); LL num = fib[pos]-1 + (temp1>0?temp+(temp1%(pos+1)?1:0):0); temp1 -= temp*(pos+1); if(!temp1) temp1 = pos+1; vector<int>arr(70,0); int in = fillarr(arr, num); int sub = 0; for (int i = in-(temp1); i >= 0; i--) { if (arr[i] == 1) sub += 1; } cout<<"/nNumber answer "<<num<<" "<<answer(num) - sub<<"/n"; return 0; }