Ich habe ein Programm bekommen, das verlangt, dass ich die Anzahl der vorherigen Zustände für eine Matrix zähle.
Die gegebene Matrix ist eine boolesche Matrix. Ich werde 1 für true und 0 für false verwenden, um das Programm zu erklären.
Der nächste Zustand einer Zelle in einer Matrix ist 1 , wenn man diese vier Zellen berücksichtigt:
Wenn die gegebene Matrix (M) ist:
1
Dann sind für die erste Zelle (M [0] [0]) die vier zu berücksichtigenden Zellen M [0] [0], M [0] [1], M [1] [0] und M [1] [1]. Also ist der nächste Zustand der ersten Zelle 0 , weil wir 2 1 in diesen 4 Zellen haben.
Für die zweite Zelle (M [0] [1]) sind die vier zu berücksichtigenden Zellen M [0] [1], M [0] [2], M [1] [1], M [ 1] [2]. Also ist der nächste Zustand für diese Zelle 1 1 0 0
0 0 0 1
0 0 1 0 , weil es nur 1 0 in diesen vier Zellen gibt.
Auf diese Weise wäre der nächste Zustand für diese Matrix (M) die Matrix (N):
1
Der nächste Zustand wird offensichtlich 1 Reihe und 1 Spalte weniger als der vorherige Zustand sein. Somit kann ein gegebener Zustand der Matrix viele vorherige Zustände haben, zum Beispiel zusammen mit der Matrix M die gegebene Matrix:
1
hat auch den nächsten Zustand N.
Ich muss die Anzahl der vorherigen Zustände zählen, die eine gegebene Matrix hat.
Ich habe den folgenden Code geschrieben:
%Vor%Was es grundsätzlich macht, ist, dass es mit einer leeren Matrix beginnt (von angemessener Größe für den nächsten Zustand, um die gewünschte Matrix zu erhalten) und beginnt von der oberen linken Ecke aus, erhöht die effektive Breite und Höhe alternativ um 1, und Überprüfen, ob der nächste Zustand der Matrix bis jetzt dem gegebenen Zustand entspricht. Wenn nicht, überspringt es den Rest der Matrix. Wenn dann eine solche Matrix gefunden wird, deren nächster Zustand der gleiche ist wie der gegebene Zustand, erhöht sie den Zähler um 1.
Dieser Code funktioniert für kleine Matrizen (keine der Zellen & lt; 40), benötigt aber für große Matrizen viel Zeit. Die maximale Breite der Matrix kann 1 und die maximale Höhe 0 1 1
0 1 0 sein. Also, dieser Code passt nicht ganz zu diesem Zweck.
Ich weiß, dass ich Memoization hier verwenden muss (% 1 0 1 0
1 0 0 0
1 1 0 0 tun tausende Male ist einfach nicht richtig!) Aber ich kann mir nicht vorstellen, wie man es benutzt. Ich habe zuvor Programme geschrieben, die dynamische Programmierung verwenden, habe aber keine Ahnung, wo es hier verwendet werden würde. Jede Hilfe wäre willkommen.
Bearbeiten: Die Einreichungsfrist wurde überschritten und ich konnte die Antwort nicht einreichen. : '( Aber ich möchte immer noch die Antwort wissen, damit ich solche Programme in Zukunft lösen kann. Ich brauche nicht den kompletten Code, aber auch ein wenig Hilfe bei der weiteren Vorgehensweise ist willkommen! :)
Es gibt viele mögliche Matrizen, die den nächsten Zustand erzeugen. Wenn die nächste Statusmatrix N angegeben wird und die anfängliche Matrix M teilweise gefüllt ist, z. B. die Elemente m[x][y+1], m[x+1][y] und m[x+1][y+1]
gefüllt sind, werden die Möglichkeiten für das Element m[x][y] mit dem Wert s = m[x][y+1] + m[x+1][y] + m[x+1][y+1] in gewisser Weise überprüft:
Es sieht aus wie Werte 1 in N 'Filter' Kombinationen und Werte 0 in N 'multiplizieren' sie.
Da die Höhe durch einen kleineren Wert begrenzt wird, schlage ich vor, zuerst die letzte Spalte mit möglichen zu füllen Werte, als Spalten rückwärts übergeben, füllen Sie das letzte Spaltenelement und dann von oberen Kontrollkästchen Füllung Element für Element.
Python-Implementierung:
%Vor%Tags und Links java performance matrix dynamic-programming memoization