Gracias por A2A.
Primero permítanme simplificar la declaración del problema en cuestión. Básicamente, lo que tenemos es que tenemos n1 número de objetos ‘X’ y n2 número de objetos ‘Y’ a la mano y queremos todas las permutaciones posibles de colocarlos, pero teniendo en cuenta que en ningún momento k1 deberían Los objetos tipo ‘X’ O k2 del tipo ‘Y’ aparecen consecutivamente. Entonces, por ejemplo:
dejar n1 = 10 y n2 = 10
k1 = 3 y k2 = 2
Por lo tanto, no queremos revestimientos donde tengamos XXXX … o YYY … de acuerdo con la declaración del problema. Ahora básicamente me referiré a un revestimiento correcto como una cadena aceptable de Xs e Ys. Una cosa interesante sobre este problema son las restricciones que se nos dan especialmente los valores de k1 y k2 que son <= 10. Esto hace que el problema sea muy fácil. Este problema tiene una solución basada en la programación dinámica, pero no daré la solución iterativa aquí, ya que la recursiva es mucho más intuitiva y fácil de entender.
- Como estudiante de primer año de una sucursal que no es CS en un IIT, ¿cómo domino las estructuras de datos, los algoritmos y el aprendizaje automático por mi cuenta?
- Explicar cómo funciona el ordenamiento de burbujas. ¿Cuál es su complejidad temporal?
- ¿Cuál es la mejor manera de aprender estructuras de datos y Java?
- ¿Existe un mejor patrón para aprender algoritmos de programación?
- ¿Por qué el NN recurrente agrega el paso T-1 a la entrada actual pero se concatena?
Ahora considere que tenemos i objetos del tipo ‘X’ aún por colocar en la cadena y j objetos del tipo ‘Y’ aún por colocar en la cadena. Deje que la posición actual donde estamos en la cadena se denote por k (Esto significa que ya hemos colocado los objetos k-1 en la cadena correctamente sin ninguna discrepancia).
Ahora en el índice dado k, tenemos dos opciones disponibles con nosotros.
- Podemos colocar un objeto de tipo ‘X’ o
- colocar un objeto de tipo ‘Y’
Pero tenemos que ocuparnos de una cosa importante aquí. Digamos que si los últimos n objetos en la cadena eran del tipo ‘X’, entonces obviamente podemos colocar el objeto ‘Y’ y proceder en la recursión ya que esto no conduciría a ninguna violación. Pero en caso de que queramos colocar otro objeto ‘X’, entonces debemos asegurarnos de que n + 1 <= k1.
Una situación similar surge si los últimos n objetos en la cadena eran del tipo ‘Y’, entonces obviamente podemos colocar el objeto ‘X’ y proceder en la recursión ya que esto no conduciría a una violación. Pero en caso de que queramos colocar otro objeto ‘Y’ entonces debemos asegurarnos de que n + 1 <= k2.
El caso base del problema es cuando i y j (que representan los objetos restantes del tipo ‘X’ e ‘Y’ que se colocarán) se convierten en 0 y para eso el número de formas es 1. A continuación se encuentra un código bien comentado para el mismo.
#include
#include
#define MOD 100000000
memorando int [101] [101] [2] [11];
/ *
El estado del problema está definido por 4 variables
1) rem_X que indica los objetos restantes del tipo X que se colocarán
2) rem_Y que indica los objetos restantes de tipo X que se colocarán
3) prev_type nos dice cuál fue el último conjunto de objetos que colocamos. 1 indica que
habíamos colocado los objetos del tipo 'X' y 1 nos dice que habíamos colocado
objetos del tipo 'Y'
4) prev_quant indica cuántos objetos de tipo anterior hemos colocado consecutivamente
* /
int recursividad (int rem_X, int rem_Y, int prev_type, int prev_quant, int k1, int k2)
{
// Todo listo. Un revestimiento está completo
if (rem_X == 0 && rem_Y == 0)
retorno 1;
// Si ya hemos calculado el resultado, devuélvelo
if (memo [rem_X] [rem_Y] [tipo_previo] [cantidad_antigua]> -1)
volver memo [rem_X] [rem_Y] [tipo_anterior] [cantidad_anterior];
// De lo contrario, calcule el resultado
más
{
int cuenta = 0;
// Si los objetos anteriores fueran de tipo X
if (tipo_previo == 0)
{
// Podemos colocar 'Y', no hay problemas aquí
if (rem_Y> 0)
cuenta + = recursión (rem_X, rem_Y-1, 1, 1, k1, k2);
// Podemos colocar X aquí siempre prev_quant + 1 <= k1
if (anterior_quant 0)
cuenta + = recursión (rem_X-1, rem_Y, 0, anterior_quant + 1, k1, k2);
}
// Otros objetos anteriores eran de tipo Y
más
{
// Podemos colocar 'X', no hay problemas aquí
if (rem_X> 0)
cuenta + = recursión (rem_X-1, rem_Y, 0, 1, k1, k2);
// Podemos colocar X aquí siempre prev_quant + 1 <= k2
if (anterior_quant 0)
cuenta + = recursión (rem_X, rem_Y-1, 1, anterior_quant + 1, k1, k2);
}
// Caché los resultados para uso holandés. Y devolver lo mismo
memo [rem_X] [rem_Y] [tipo_anterior] [anterior_quant] = (cuenta% MOD);
cuenta de retorno% MOD;
}
}
int main ()
{
int n1, n2, k1, k2;
scanf ("% d% d% d% d", & n1, & n2, & k1, & k2);
// Inicializa los valores de la matriz de memorización a -1
memset (memo, -1, sizeof (memo));
// La función principal que calcula nuestro resultado
printf ("% d \ n", recursión (n1, n2,0,0, k1, k2));
devuelve 0;
}
Feliz codificación !!!
