Witam,
Moim zadaniem jest zaimplementowanie takiego oto programu (Stosując technikę "dziel i zwyciężaj" oraz funkcję rekurencyjną):
Mam prostokątną tabliczkę czekolady. Niektóre kawałki są białe, a niektóre czarne (nie ma żadnej reguły).
Łamiemy czekoladę na dwa kawałki: podział odbywa się wzdłuż jednej z pionowych lub poziomych bruzd.
Następnie te dwa kawałki dzielimy w analogiczny sposób. Kiedy ktoś dostanie pojedynczy kawałek to go zjada (ile można dzielić?).
Dalszy podział nie jest dokonywany też, kiedy jeden z powstałych fragmentów miałby być cały biały lub czarny.
Problem:
Ile jest możliwych różnych podziałów czekolady?
Siedzę od wczoraj nad tym zadaniem, rozrysowuje sobie różne schematy na kartce, ale idzie bardzo słabo.
Z najważniejszych rzeczy, które ustaliłem to, że podziałów (cięć) może być poziomych: m-1 oraz pionowych: n-1.
Nie mogę za bardzo wyobrazić sobie w głowie tych kombinacji wszystkich cięć...
Próbowałem rozwiązać zadanie wpierw w sposób iteracyjny wykorzystując tablice prefiksowe, ale w pewnym momencie pogubiłem się w tym wszystkim...
Jak próbowałem to rozwiązać wpierw iteracyjnie, aby mieć jakiś punkt zaczepienia:
Wczytalem dane z pliku, m - liczba wierszy, n - liczba kolumn, nastepnie stworzylem dwie tablice m x n, jedną dla czarnych kawałków, drugą dla białych kawałków. Jak wystąpił dany kawałek to dawałem 1, jak nie to 0.
W taki sposób otrzymałem wypełnione tablice dla czarnej czekolady i białej: tablica_cz[m][n] oraz tablica_b[m][n].
Następnie przekształciłem te tablice w tablice sum prefiksowych, a następnie chciałem sprawdzać coraz to większe kawałki (zaczynając od prostokąta 1 x 1) i zliczać kombinację, ale pogubiłem się i doszedłem do wniosku, że ten kod zmierza w złym kierunku ;/ Ktoś pomoże?
Kod tej części, gdy: tablica_czarna[m][n] oraz tablica_biala[m][n] są już tablicami sum prefiksowych
int pomPoziom=0;
int pomPion=0;
boolean CzyCz1zawiera = false;
boolean CzyCz2zawiera = false;
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
for(int k=0; k<=i; k++){
for(int l=0; l<=j; l++){
if(tablica_czarna[k][l] != 0 && tablica_biala[k][l] != 0){
/* Poziomy podzial */
// jedna czesc czekolady badanego obszaru
for(int a=0; a<i; a++){
int licznik_cz1=0;
int licznik_cz2=0;
for(int u=0; u<=a; u++){
for(int q=0; q<=j; q++){
/* Sprawdzam czy ta czesc zawiera dwa kolory */
if(tablica_czarna[u][q] != 0 && tablica_biala[u][q] != 0){
CzyCz1zawiera = true;
}
}
licznik_cz1=+1;
}
// druga czesc czekolady badanego obszaru
for(int z=a+1; z<=i; z++){
for(int q=0; q<=j; q++){
if(tablica_czarna[z][q] != 0 && tablica_biala[z][q] != 0){
CzyCz2zawiera = true;
}
}
licznik_cz2=+1;
}
if(CzyCz1zawiera == true && CzyCz2zawiera == true){
System.out.println("BylemTuCieciaPoziome");
pomPoziom = licznik_cz1*licznik_cz2;
CzyCz1zawiera = false;
CzyCz2zawiera = false;
}
}
/* Pionowy podzial */
// jedna czesc czekolady badanego obszaru
for(int a=0; a<j; a++){
int licznik_cz1=0;
int licznik_cz2=0;
for(int u=0; u<=a; u++){
for(int q=0; q<=i; q++){
/* Sprawdzam czy ta czesc zawiera dwa kolory */
if(tablica_czarna[q][u] != 0 && tablica_biala[q][u] != 0){
CzyCz1zawiera = true;
}
}
licznik_cz1=+1;
}
// druga czesc czekolady badanego obszaru
for(int z=a+1; z<=j; z++){
for(int q=0; q<=i; q++){
if(tablica_czarna[q][z] != 0 && tablica_biala[q][z] != 0){
CzyCz2zawiera = true;
}
}
licznik_cz2=+1;
}
if(CzyCz1zawiera == true && CzyCz2zawiera == true){
System.out.println("BylemTuCieciaPionowe");
pomPion = licznik_cz1*licznik_cz2;
CzyCz1zawiera = false;
CzyCz2zawiera = false;
}
}
}
}
}
}
}