[java] Znalezienie maksymalnej powierzchni na tablicy

Dla specjalistów Programowanie
#1

Witam potrzebuję pewnej funkcji, ale mi nie wychodzi. Wiem że to powinno być w 2 pętlach.

Otóż mam int[][] tablica = new int[15][35] zapłoniony różnymi liczbami. Potrzebowałbym metody która zwracałaby mi maksymalne wymiary prostokąta od zadanych współrzędnych.

int[] maks(int[][] tablica,int x, int y)

przykład:

tab = {

{1, 2, 0, 0, 2, 1},

{0, 2, 0, 0, 4, 3},

{0, 1, 0, 0, 0, 3}

}

maks(tab,2,0) = {2,3}

maks(tab,2,2) = {2,1}

maks(tab,3,1) = {1,2}

wersja na tablicy jednowymiarowej

int maks(int[] tab,int x){

        int wynik =0;

        for(int i=x;i
            if(tab[i]==0) wynik++;

            else break;

        }

        return wynik;

    }
#2

Może wyjaśnisz metodę porównania wymiarów z punktem, bo ja takiej nie znam.

#3

Chodzi o maksymalną powierzchnię prostokąta ułożonego z zer?

To nie jest takie proste.

Zauważ, że dla przykładowej tablicy:

{0, 0, 0, 0, 0,}

{0, 0, 0, 0, 0,}

{0, 0, 1, 0, 3,}

{0, 0, 0, 2, 0,}

{0, 0, 0, 4, 0,}

i brania pod uwagę jej całości (początkowe [0][0]) : wyniki są dwa:

  • [*:2boq4mxg] {5}{2} [*:2boq4mxg] {2}{5}
    W takim wypadku najprostsze zastosowanie dwóch pętli:
for(int j=y;i*nie_wiem_jak_to_obslugiwac*/;j++){


 if(tab[j][i]==0) {


	wynik[0] = wynik[0] + 1 ;

	wynik[1] = 0;

      		  for(int i=x;i*nie_wiem_jak_to_obslugiwac*/;i++){

            	if(tab[j][i]==0) wynik[1] = wynik[1] + 1;

            	else break;

		}

else break;

zwróci, o ile się nie mylę, wynik {5}{2}, czyli maksymalne wartość jednego z wymiarów, drugi dostosowany. Odwrócenie zmiennych w kodzie (pętle i tablice) spowoduje odwrócenie tych wymiarów (wynik prawidłowy dla drugiego prostokąta - {2}{5})

To jednak i tak nie w każdym przypadku będzie odpowiadało największemu prostokątowi, tylko “najdłuższemu” lub “najwyższemu”

Do prawidłowego działania potrzeba dodatkowych warunków.

#4

Dzięki za pomoc.

Na razie udało mi się mniej więcej przepisać twój kod c++ na javę.

public static int[] maks(int[][] tab,int x,int y){

        int[] wynik = new int[]{0,0};

        int maks = tab.length;

        for(int j=y;j
            if(tab[j][x]==0){

                wynik[0]++;

                wynik[1]=0;

                for(int i=x;i
                    if(tab[j][i]==0)

                        wynik[1]++;

                    else {

                        maks = i;

                        break;

                    }

                }

            }

            else break;

        }

        return wynik;

    }

Jednak popełniłeś tam błędy:

  • użyłeś niezadeklarowanej zmiennej “i”, sądzę że powinno być x

  • użycie break z wewnętrzej pętli nie zmienia ograniczenia górnego przy następnej iteracji co powodowało błędny wynik

To że istnieją 2 wyniki to mi nie przeszkadza. Te tablica zbyt często się zmienia. Teraz spróbuje dopisać jeszcze Twój dopisek o wybraniu optymalnego wyniku

#5

To nie był kod C++, pisałem na podobieństwo tego co widziałem w Twoim kodzie javy.

W ogóle tego nie kompilowałem, pisałem w notatniku ;p

Zmienna i w pętli for z j++? Tak, tam nie powinno być i.

A propo 2. “nie zmienia ograniczenia górnego przy następnej iteracji” -> Właśnie po to teraz wszedłem, aby to poprawić ;).

Generowało to błędne wyniki, - nawet prostokąt, którego 2 boki były zerami, ale środek już nie, wiem o tym.

Nie wiem tylko, czy w tym kodzie, który wyszedł, nie trzeba będzie mnożyć wynik[0] * wynik[1] zamiast zmiennych i i j

deklaracja tablicy glowny_wynik

(...)

linijka wynik[1]++

if(wynik[0]*wynik[1]>glowny_wynik[0]*glowny_wynik[1]) {

glowny_wynik[0] = wynik[0]

glowny_wynik[1] = wynik[1]

}

Sprawdź czy dobrze, albo mnie popraw, jeśli możesz.

Wtedy temat na forum będzie rozwiązany do końca.

#6

Wprowadziłem te zmiany i program zaczął chodzić niestabilnie. Dodatkowo chyba coś spaprałem bo dla tablicy prostokątnej to się wysypuje.

Rozbiłem funkcje na 2 osobne przez co nie ma zagnieżdżonych for i mniej if

public static int maks(int[] tab,int x){

        int wynik =0;

        for(int i=x;i
            if(tab[i]==0) wynik++;

            else break;

        }

        return wynik;

    }


    public static int[] maks(int[][] tab,int x,int y){

        int[] wynik = new int[]{0,0};

        int[] wynikGlowny = new int[]{0,0};

        int oldszer = maks(tab[y],x);

        for(int j=y;j
            wynik[0] = Math.min(maks(tab[j], x),oldszer);//mniejsza wartość między aktualnym rozmiarem a starym

            wynik[1] = j-y+1;

            oldszer = wynik[0];

            if(wynik[0]*wynik[1]>wynikGlowny[0]*wynikGlowny[1]){

                wynikGlowny[0] = wynik[0];

                wynikGlowny[1] = wynik[1];

            }

        }

        return wynikGlowny;

    }

program działa poprawnie i generuje sensowne wyniki. Temat do zamknięcia