Generalización:
Inicialmente se nos da una cuadrícula rectangular de objetos [math] r \ times c [/ math] (donde [math] r, c \ in \ mathbb {N} \ backslash \ {1 \} [/ math]). En cada paso de tiempo, vaciamos [matemáticas] 1 [/ matemáticas] de las celdas [matemáticas] rc [/ matemáticas] de la cuadrícula. Queremos saber la cantidad de formas en que podemos vaciar toda la cuadrícula (celda [matemática] 1 [/ matemática] a la vez) al tiempo que nos aseguramos de que nunca tengamos simetría vertical u horizontal (excepto al principio y al final).
Para nuestra pregunta específica, [matemáticas] r = 2 [/ matemáticas] y [matemáticas] c = 5 [/ matemáticas].
- ¿Sería inmaduro de mi parte cambiar mi especialidad?
- ¿Qué es una explicación intuitiva de un ideal fraccional?
- En la siguiente prueba de que [math] \ sqrt {2} [/ math] no termina, ¿dónde aparece la expresión [math] q = p - \ frac {p ^ {2} - 2} {p + 2} [ / matemáticas]
- ¿Hay algún ejemplo de resultados matemáticos de larga data que luego sean refutados?
- ¿Cuál es la respuesta a la pregunta (ab) ^ 3?
Responder:
A continuación se muestran las formas de vaciar una cuadrícula rectangular [matemática] r \ veces c [/ matemática] mientras se mantiene la condición de nunca tener simetría vertical u horizontal (excepto al principio y al final). Se calcularon en los siguientes tiempos utilizando el código que se muestra a continuación.
Como se observa en la tabla anterior, la respuesta para nuestra pregunta específica es [math] \ boxed {1151488} [/ math].
Código:
El siguiente script de Python calcula la cantidad de formas de vaciar una cuadrícula rectangular, manteniendo la propiedad de que nunca hay simetría vertical u horizontal (excepto al principio y al final). Utiliza un algoritmo de retroceso y elimina gran parte del espacio de búsqueda almacenando en caché el número de formas para cada posición de cuadrícula ya vista (así como su reflexión vertical, reflexión horizontal y rotación [matemática] 180 ^ {\ circ} [/ matemática] )
#! / usr / bin / python
matemáticas de importación
tiempo de importación
def main ():
maxRows = 4
maxCols = 5
imprima “filas \ tcolumns \ tnum ways \ ttime (s)”
para filas en rango (2, maxRows + 1):
para cols en rango (filas, maxCols + 1):
startTime = time.time ()
maneras = getNumWays (filas, cols)
imprimir str (filas) + “\ t” + str (cols) + “\ t” + \
str (maneras) + “\ t” + str (time.time () – startTime)
def getNumWays (filas, columnas):
grid = [[True para col en rango (cols)] para fila en rango (filas)]
return helpGetNumWays (cuadrícula,
conjunto(),
dict (),
dict (),
dict ())
def helpGetNumWays (cuadrícula,
células usadas,
usedRows,
usedCols,
cachedPos):
frozenCurrentUsed = frozenset (usedCells)
si frozenCurrentUsed no está en cachéPos:
filas = len (cuadrícula)
cols = len (cuadrícula [0])
numUsedCells = len (usedCells)
if numUsedCells == filas * cols:
volver 1
numAnswers = 0
if numUsedCells == 0 o isValid (grid, usedRows, usedCols):
para fila en rango (filas):
para col en rango (cols):
si no es grilla [fila] [col]:
Seguir
cuadrícula [fila] [col] = Falso
si la fila no está en filas utilizadas:
usedRows [fila] = 0
usedRows [fila] + = 1
si no está en la columna utilizada:
usedCols [col] = 0
usedCols [col] + = 1
celda = (fila, col)
usedCells.add (celda)
numAnswers + = helpGetNumWays (grid,
células usadas,
usedRows,
usedCols,
cachedPos)
usedCells.remove (celda)
usedCols [col] – = 1
si se usaCols [col] == 0:
del usedCols [col]
usedRows [fila] – = 1
si se utiliza Filas [fila] == 0:
del usedRows [fila]
cuadrícula [fila] [col] = Verdadero
cachedPos [frozenCurrentUsed] = numAnswers
cachedPos [flipVertical (frozenCurrentUsed, rows)] = numAnswers
cachedPos [flipHorizontal (frozenCurrentUsed, cols)] = numAnswers
cachedPos [rotate180 (frozenCurrentUsed, rows, cols)] = numAnswers
return cachedPos [frozenCurrentUsed]
def rotate180 (usedCells, filas, cols):
toReturn = set ()
para pos en usedCells:
toReturn.add ((filas – pos [0] – 1, cols – pos [1] – 1))
volver a congelar (volver)
def flipVertical (usedCells, filas):
toReturn = set ()
para pos en usedCells:
toReturn.add ((filas – pos [0] – 1, pos [1]))
volver a congelar (volver)
def flipHorizontal (usedCells, cols):
toReturn = set ()
para pos en usedCells:
toReturn.add ((pos [0], cols – pos [1] – 1))
volver a congelar (volver)
def isValid (grid, usedRows, usedCols):
return not isSymmetricHorizontal (grid, usedRows, usedCols) y \
not isSymmetricVertical (grid, usedRows, usedCols)
def isSymmetricVertical (grid, usedRows, usedCols):
cols = len (cuadrícula [0])
para col en rango (int (math.floor (cols / 2))):
diffCol = cols – col – 1
si col! = diffCol:
si col en usedCols y diffCol en usedCols:
para fila en usedRows:
if grid [row] [col]! = grid [row] [diffCol]:
falso retorno
elif col en usedCols o diffCol en usedCols:
falso retorno
volver verdadero
def isSymmetricHorizontal (grid, usedRows, usedCols):
filas = len (cuadrícula)
para fila en rango (int (math.floor (rows / 2))):
diffRow = filas – fila – 1
si fila! = diffRow:
si fila en usedRows y diffRow en usedRows:
para col en coles usados:
if grid [row] [col]! = grid [diffRow] [col]:
falso retorno
fila elif en usedRows o diffRow en usedRows:
falso retorno
volver verdadero
if __name__ == ‘__main__’:
principal()
