Resumen del problema: comience con el dígito 1. En cada paso, convierta el dígito 0 a 10 y el dígito 1 a 01 para obtener una nueva secuencia de dígitos. Después de N pasos, ¿cuántos pares de ceros consecutivos aparecen en la secuencia?
La idea clave aquí es “¿cómo interactúan las partes de una cadena entre sí?” Es decir, ¿puedo romper una cadena ABCDEFGH y examinar la evolución de ABC y DEFGH por separado confiando en que no perderé un doble cero?
Supongamos que tenemos una secuencia que termina en 1. Luego, según las reglas, sus descendientes siempre terminarán con 1 (ya sea … 11 -> … .0101 o … .01 -> … .1001.). Entonces, si tenemos una cadena [matemática] X1Y [/ matemática] podemos evaluar [matemática] X1 [/ matemática] e [matemática] Y [/ matemática] por separado, porque la primera secuencia nunca tendrá un 0 al final, lo que podría crea un doble cero.
Ahora podemos construir una mesa
- ¿Por qué no se pueden usar los dígitos de pi para hacer un generador de números aleatorios no cíclicos?
- Cómo calcular la probabilidad de ganar en ajedrez
- Para un n dado, ¿es posible elegir uniformemente un número del 1 al n usando un número fijo de bits aleatorios uniformes?
- ¿Cómo resolver problemas de interpolación (por el método de la diferencia dividida de Newton) usando Matlab? ¿Puedo obtener el algoritmo para resolverlo?
- Dado un número M (entero de N dígitos) y operaciones de intercambio K (una operación de intercambio puede intercambiar 2 dígitos), ¿qué es un algoritmo para obtener el máximo entero posible?
[matemáticas] Z (1, n) [/ matemáticas]
[matemáticas] Z (01, n) [/ matemáticas]
[matemáticas] Z (001, n) [/ matemáticas]
[matemática] Z (0001, n) [/ matemática]
etc.
que registra cuántos ceros dobles hay en la expansión de cada cadena [math] n [/ math] pasos más adelante. El primer caso es fácil:
[matemáticas] Z (1,0) = 0 [/ matemáticas]
[matemáticas] Z (1, n) = Z (01, n-1) [/ matemáticas]
El segundo caso comienza a verse un poco más complicado:
[matemáticas] Z (01,0) = 0 [/ matemáticas]
[matemáticas] Z (01, n) = Z (001, n-1) + Z (1, n-1) [/ matemáticas]
Es decir, 01 evoluciona a 1001 en el siguiente paso, pero podemos dividirlo en las subsecuencias 1 y 001.
En el tercer caso, finalmente tenemos un doble cero para contar:
[matemáticas] Z (001,0) = 1 [/ matemáticas] porque tiene un doble cero
001 cambia a 101001 así que,
[matemática] Z (001, n) = [/ matemática] [matemática] Z (001, n-1) + Z (01, n-1) + Z (1, n-1) [/ matemática]
Sorprendentemente, hemos terminado! Y tenemos una prueba de que es imposible obtener un triple cero a partir de 1, como bonificación. Esperemos que esté claro cómo convertir esta recurrencia en un algoritmo de programación dinámico.