Algunos datos son conocidos, la primera fila es 01, la segunda fila es 10 01, la tercera fila es 01 10 10 01... es decir, los datos de la i-ésima fila son para cambiar el 1 en el i-ésima fila en 01...
Hacía mucho tiempo que no veía una pregunta tan interesante
En primer lugar, siguiendo las reglas y fuera de los hábitos de los programadores, agregaré una línea, la Los datos en la línea 0 son 1. Esto le ayudará a escribir la fórmula más adelante y 1 se convertirá en 01 (es decir, los datos en la primera fila), lo que está en línea con las reglas de la pregunta original.
En segundo lugar, defina algunos métodos de escritura: N(i)(xx) representa el número de veces que aparece el patrón xx en la línea i. Por ejemplo, N(1)(01) = 1 significa que el patrón. 01 aparece en la línea 1. 1 vez. El número de líneas aquí se representa mejor mediante subíndices, que son más claros y se ajustan a las convenciones de derivación matemática, pero desafortunadamente es inconveniente escribir así en la página web.
Después de terminar los preparativos, descubrí que no tenía ni idea, así que escribí un programa.
Se encuentra que N(i)(00) = N(i-1)(00) * 2 ±1, es decir, el número de 00 en la i-ésima fila es 2 veces el número de 00 en la fila anterior, 1 o -1 (dependiendo de la paridad i), la secuencia real es 0, 1, 1, 3, 5, 11, 21, 43, 85,... Probemos esto a continuación
A través de la observación se descubrieron los siguientes puntos:
1 Para que aparezca 00, 01 debe aparecer en la línea anterior, porque 01 se convertirá en 1001, y solo así aparecerá 00
. Entonces el número de 00 en una determinada línea es igual al número de 01 en la línea anterior Número, es decir: N(i)(00) = N(i-1)(01)
2 Si aparece 01, hay dos situaciones: una es que 1 se convertirá en 01 y la otra es 00, porque 00 se convertirá en 1010, por lo que se incluirá un 01.
Entonces, el número de 01 en una determinada fila es. igual al número de unos en la fila anterior más el número de ceros en la fila anterior
Es decir: N(i)(01) = N(i-1)(1) N(i- 1)(00)
3. Respecto al número de unos: en una línea Dentro, 1 se convertirá en 01 y 0 se convertirá en 10, por lo que el número de 0 y 1 es igual al número total de todos los números de la fila anterior y el dato inicial es 01, por lo que se puede resumir:
N(i)(1) = 2^(i-1) [i gt cuando 0]
De esta manera, tenemos tres fórmulas recursivas, más algunas condiciones básicas, para formar algunos sistemas de ecuaciones:
N(i)(00) = N(i-1)( 01)
N(i)(01) = N(i-1) (1) N(i-1)(00)
N(i)(1) = 2^(i-1) [i gt; cuando 0]
N( 0)(1) = 1
N(0)(00) = N(1)( 00) = 0
N(0)(01) = 0
N(1)(01) = 1
Resolviendo esta fórmula recursiva (nada más en lugar de superponerlos, luego eliminarlos y finalmente sumar la secuencia aritmética y la secuencia geométrica), podemos obtener:
Cuando i es un número par: N(i)(00) = [2^( i-1) 1]/3 [i es mayor o igual a 2]
Cuando i es un número impar Cuando: N(i)(00) = [2^(i-1)- 1]/3 [i es mayor o igual a 3]
Caso básico: N(0)(00) = N(1 )(00) = 0
Lo anterior es puramente por interés. Si solo quieres código (por supuesto, no especificaste el lenguaje del código), solo tengo un programa con bajo rendimiento que escribí en Java al principio...
público. prueba de clase
{
public static void main(String[] args) lanza una excepción
{
LinkedListlt; nueva lista enlazada ();
lista enlazada; l2 = nueva lista enlazada ();
lista enlazada l3; .add(1);
for (int i = 1; i lt; 10; i) {
while (l1.isEmpty() == false) {
int n = l1.pollFirst();
si (n == 0)
{
l2.add(1);
l2.add(0);
} más {
l2.add( 0);
l2.add(1);
}
}
System.out.println(foo(l2)
l3 = l1
l1 = l2
l2 = l3
}
; }
private static int foo(LinkedListlt; Integergt; l) {
int last = 1, count = 0
for (Entero n: l) {
if (último == 0 amp; amp; n.intValue() == 0) {
count
}
último = n;
}
recuento de retornos
}
}