Número de combinaciones con ladrillos de plástico LEGO C++

Question

Tiene algunos ladrillos de plástico LEGO, todos los ladrillos son 1x1x1. También tiene una ficha, 1xN (N < = 80), en la que debe colocar los ladrillos LEGO. Puedes ordenarlos en secuencias (una secuencia es correcta si tiene 3 o más ladrillos consecutivos), también debes tener al menos 1 espacio vacío entre 2 secuencias. Debe calcular la cantidad de combinaciones diferentes en las que puede colocar los ladrillos en los mosaicos.

He aquí un ejemplo:

Si la baldosa es 1x7, hay 17 combinaciones diferentes.

de entrada: 7 de salida: 17

pic of the example http://mendo.mk/task_files/kocki.gif

Además, si usted no tiene ladrillos se cuenta como 1 combinación.

He trabajado en este problema y encontré la manera de calcular las posibles combinaciones de si la longitud máxima de la losa es de 14 (3 secuencias). Lo encontré usando bucles.

Mi mayor problema es la gran cantidad de bucles for que necesito para ejecutar. Por ejemplo, para 1 secuencia, uso 1 para bucles, para 2 secuencias 2 bucles + 1 para 1 secuencia ... así que si uso los 80 ladrillos, puedo crear 20 secuencias y tendré que usar más de 210 para bucles, lo cual es numero enorme. Entonces será bueno si puedo anidarlos en uno. Lo intenté y se volvió complicado y no da respuestas correctas.

Nuevo código:

#include <iostream> 
using namespace std; 
int main() 
{ 
    long long int places, combinations = 1; 
    cin >> places; 
    long long int f[80], g[80]; 
    f[0] = 0; 
    f[1] = 0; 
    f[2] = 0; 
    g[0] = 1; 
    g[1] = 1; 
    g[2] = 1; 
    for(int i = 3; i<=places; i++) 
    { 
     f[i] = f[i-1] + g[i-3]; 
     g[i] = f[i-1] + g[i-1]; 
    } 
    combinations = f[places] + g[places]; 
    cout << combinations; 
    return 0; 
} 

Answer 1

Si este problema está contando (combinación no solo outputing contarlos) Es fácil. Asuma que lo ha resuelto para n ≥ 3 ahora quiere resolverlo para n + 1, resuélvalo por inducción:

suponga f es una función que muestra el número de posibles formas en que el último elemento es el ladrillo. y g es una función que muestra el número de formas posibles, por ejemplo, que el último elemento no es de ladrillo. y h = f+g todas las formas posibles.

Así tenemos:

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

Con condición inicial:

for n=0,1,2: g=1, f= 0. 
for n = 3: g=1,f=1 

Muestras:

n=4: g=2,f=2 ==> h=4 
n=5: g=4, f= 3 ==> h=7 
n=6: g=7, f= 4 ==> h=11 
n=7: g=11,f=6 ==> h=17 

Simplemente puede resolver con un bucle for de O(n).

---

qué:

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

primer lugar vamos a demostrar primera parte:

Recuerde que asumimos f (n) es la solución que tiene ladrillos de plástico en el último punto, yg (n) trabajando está funcionando la solución que no tiene ladrillo en el último artículo.

f (n + 1) puede continuar el camino de f (n), significa agregar un ladrillo en el último lugar. También f (n + 1) se puede hacer agregando tres bloques después de g (n-2), significa celdas de n-1, n, n + 1, tenga en cuenta que no podemos agregar bloques de bloques después de g (n-1) og (n) para crear una solución válida para f (n + 1) porque no son soluciones válidas (el número de ladrillos consecutivos es menor que 3). También tenga en cuenta que no es necesario contar la cantidad de formas que surgen al agregar ladrillos después de g (n-3), ya que están enumeradas previamente por f (n). Entonces tenemos f(n+1) = f(n) + g(n-2).

De la misma manera se puede demostrar g(n+1) = f(n)+g(n) este caso es más fácil, porque g (n + 1) puede simplemente hecha de cualquier solución válida hasta n, porque no hay existe límite de 3 ladrillos consecutiva para espacios libres, que pueden venir después de cualquier solución válida.

Answer 2

Como persona con entrenamiento matemático, en lugar de CS, me siento obligado a mencionar eso, mientras que el algoritmo de Saeed Amiri es muy bueno y probablemente funcione lo suficientemente rápido para N hasta unos pocos millones (con memoria constante, por supuesto) , hay un mejor algoritmo desde la perspectiva del tiempo.

voy a continuar donde lo ha dejado:

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

ya que F y G son funciones discretas, se pueden tratar como secuencias. Esto se convierte en un sistema lineal de relaciones de recurrencia, entonces. Afortunadamente, un sistema como este puede resolverse por completo, de modo que se pueda presentar la forma explícita de f y g.
Desafortunadamente, SO no parece ser compatible con MathJax como math.SE, por lo que me disculpo por la baja calidad de las ecuaciones a partir de ahora.
Vamos

  | f(n) | 
    |f(n-1)| 
u(n)=|f(n-2)| 
    | g(n) | 
    |g(n-1)| 
    |g(n-2)| 

Es decir, u (n) es un vector fila. A continuación, lo siguiente es cierto:

 
|f(n+1)| |1 0 0 0 0 1| | f(n) | 
| f(n) | |1 0 0 0 0 0| |f(n-1)| 
|f(n-1)| = |0 1 0 0 0 0| . |f(n-2)| 
|g(n+1)| |1 0 0 1 0 0| | g(n) | 
| g(n) | |0 0 0 1 0 0| |g(n-1)| 
|g(n-1)| |0 0 0 0 1 0| |g(n-2)| 

Lo que sigue de esto es, que u(n) = A * u(n-1), donde A es la matriz anterior.
Luego, u(n) = (A^(n-2)) * u(2), donde u(2) es el vector, que contiene los valores iniciales del problema. Esto, a su vez, proporciona un algoritmo con complejidad O(log(n)), ya que puede usar una exponenciación rápida para calcular (A^(n-2)) y luego multiplicarlo a u(2).

Por supuesto, cualquier técnica de este tipo requeriría probablemente un BigInt de algún tipo, ya que de lo contrario el desbordamiento está garantizado.

También tenga en cuenta que esta técnica se puede aplicar un paso más allá:
Usted puede encontrar los vectores propios y valores propios de A y luego se descomponen en los vectores propios u(2). Luego, tendrá una forma cerrada para ambos f (n) yg (n).

Yo firmemente que desaconsejan un algoritmo basado en la forma cerrada
Es casi seguro que implicará alta precisión de los cálculos de punto flotante (a menos que todos los valores propios son números enteros, lo que es muy poco probable), que son de por lo menos esta complejidad desde la perspectiva de programación, y generalmente no son operaciones de tiempo constante. Por supuesto, tampoco lo son las operaciones BigInt. Por lo tanto, un algoritmo de tiempo constante generalmente no es factible, además probablemente ni siquiera necesite el O(log(n)), ya que para la mayoría de los usos, el lineal es lo suficientemente bueno.

Nota
La técnica descrita aquí se puede utilizar en una variedad de problemas y es de uso extremo en problemas de optimización dinámica. Además, por lo general las personas quedan impresionadas cuando ven esto por primera vez;)