Próbowałem rozwiązać this programming problem, ale ponieważ nie mogę tego rozgryźć, znalazłem rozwiązanie online. ale naprawdę nie mogę zrozumieć, dlaczego to rozwiązanie działa albo ..SPOJ: wyjaśnienie rozwiązania M3TILE
zadaniem jest obliczenie na ile sposobów można to 3 * n (n >= 0, n jest tylko wejście) prostokąt być całkowicie wypełniona 2 * 1 domino.
np. (Czerwone linie oznaczają domino):
To właśnie po raz pierwszy zwrócił na kartce papieru, gdy czytam teksty, i widziałem, że istnieją trzy możliwe kombinacje, że 3 * 2 prostokąt może mieć , a jeśli n jest nieparzyste, rozwiązaniem jest 0, ponieważ nie ma możliwości wypełnienia całego prostokąta (jeden element zawsze pozostanie odkryty przez domino).
Więc pomyślałem, że rozwiązanie było po prostu 3^n, jeśli n było parzyste, a 0, jeśli n było nieparzyste. Okazuje się, myliłem się.
znalazłem stosunkowo proste rozwiązanie tutaj:
#include <iostream>
using namespace std;
int main()
{
int arr[31];
arr[0]=1;
arr[1]=0;
arr[2]=3;
arr[3]=0;
for(int i = 4; i < 31; i++) {
arr[i] = arr[i-2] * 4 - arr[i-4]; //this is the only line i don't get
}
int n;
while(1) {
cin >> n;
if(n == -1) {
break;
}
cout << arr[n] << endl;
}
return 0;
}
Dlaczego to działa ?!
Nicea dowód! Więcej informacji dostępnych pod adresem http://oeis.org/A001835 –
@Daniel Czy możesz wyjaśnić przypadek bazowy odpowiadający n = 0. –
@ ATulSingh Dla n = 0, mamy tablicę bez komórek. Jest dokładnie jeden sposób na wyłożenie go: nie kładź na nim kafelków [deska 3 × 0 ma 3 · 0 = 0 komórek, więc potrzebujesz 0/(2 · 1) = 0/2 = 0 płytek]. –