Números de Fibonacci y recurrencias lineales

Hoy, mientras hacía este tema, nuestro profesor dio un ejemplo con mosaicos.

El ejemplo: hay 2 tipos de fichas, A= 1 x 1 y B= 2 x 1. ¿De cuántas formas puedes colocar las fichas en una línea de n unidades de largo?

Hay dos casos. Caso 1: la última ficha es 1 x 1 por lo que las fichas anteriores son un arreglo de n-1 unidades. Caso 2: la última ficha es 2 x 1 por lo que la disposición anterior es de n-2 fichas. Llamemos al número de arreglos de tipo uno w norte − 1 y el número de arreglos de tipo dos w norte − 2 . Entonces tenemos una relación de recurrencia w norte = w norte − 1 + w norte − 2 .

Realmente no tengo idea de lo que está pasando aquí, si alguien pudiera explicarme, estaría agradecido.

Respuestas (3)

Supongamos que sus mosaicos forman una línea de longitud norte .

Si la última ficha es de forma de A , entonces estamos concatenando la línea anterior de longitud norte − 1 con A . Por lo tanto, solo tenemos que preocuparnos por el número de formas de formar una línea de longitud norte − 1 usando esos mosaicos, que es w norte − 1 .

Si la última ficha es de forma de B , entonces estamos concatenando la línea anterior de longitud norte − 2 con B . Por lo tanto, solo tenemos que preocuparnos por el número de formas de formar una línea de longitud norte − 2 usando esos mosaicos, que es w norte − 2 .

Por eso

w norte = w norte − 1 + w norte − 2

Acabo de editar la pregunta. Luego señala que w norte = F norte + 1 , donde f denota los números de Fibonacci. yo tampoco entiendo esta parte
Encontramos eso w norte = w norte − 1 + w norte − 2 , w 1 = 1 , w 2 = 2 . también sabemos que F norte = F norte − 1 + F norte − 2 , F 1 = 1 , F 2 = 1 , F 3 = 2 .
¿Hay alguna manera de pensar en esto en términos de coeficientes binomiales?
no es obvio para mí por ahora. ¿Tienes otra forma de contar que se base en eso?
Tenía la idea de que este problema podría traducirse en elegir 2k mosaicos 1x1 donde va de k va de n/2 a 0 y elegir k 2 x 2 mosaicos donde k va de 0 a n/2, pero no pude descifrar cómo esto se traduciría en una ecuación que involucra coeficientes binomiales
no es obvio para mí cómo hacerlo. si seleccionamos la posición inicial para la longitud 2 azulejo, si la posición i es elegido, no debemos elegir posición i + 1 , existe esta complicación que debemos manejar.

Comience con una pequeña cadena.

Para hacer una línea de 1" de largo, use un mosaico pequeño.

Para hacer una línea de 2 "de largo, use 2 mosaicos pequeños o un mosaico grande.

Para hacer una línea de 3" tome una línea de 2" de largo y coloque una loseta pequeña en el extremo, o tome una línea de 1" de largo y coloque una loseta grande en el extremo.

¿De cuántas maneras de hacer una cadena que es norte " de largo? Agrega un mosaico pequeño a una cadena que es ( norte − 1 ) " o un mosaico largo a una cadena que es ( norte − 2 ) "

F norte = F norte − 1 + F norte − 2

En este problema estamos intentando dar una respuesta a la pregunta "¿cuántos arreglos hay, para un arreglo de tamaño n?", y lo hacemos en forma de recursividad.

Eso significa que estamos diciendo algo como "Si supiéramos la respuesta a esta pregunta para un número menor que n, entonces tal vez podríamos representar nuestra respuesta con esa respuesta".

En este caso, sí que podemos.

SUPONE que conoce el número de arreglos para un arreglo de tamaño n-1 y la respuesta para un arreglo de tamaño n-2.

Ahora, mire una matriz de tamaño n, para la cual no conoce la cantidad de arreglos.

Ahora tratamos de representar una respuesta para n por la respuesta (conocida) para n-1 y n-2

Es posible hacerlo separando en dos casos distintos.

  1. La última ficha es 1x1
  2. La última ficha es 2x1

¿Cuántos arreglos para el caso 1? En realidad, esto es como preguntar cuál es el tamaño de la matriz que queda sin el último mosaico. Respuesta: n-1, es decir arreglos f(n-1).

Lo mismo para el caso 2, arreglos f(n-2).

Estos son dos casos distintos, por lo que sumamos el número de opciones que cada uno de ellos produce:

F(n)=f(n-1)+f(n-2)

Números de Fibonacci y recurrencias lineales
RespuestasAquíPolítica de privacidad1y, 0v