Witam,
Otoz mam taki problem nie wiem skąd to się bierze, ale wygląda to tak:
mam sobie plik tekstowy w ktorym sa liczby naturalne o X rzędach i Y kolumnach np.:
X=5; Y=4
czyli plik tekstowy:
3 5 6 3
4 1 5 4
5 4 3 6
1 5 3 1
3 4 5 1
Zadaniem jest znalezc lewy gorny rog prostokąta o danych wymiarach G x H załóżmy, że G=2, H=2, w którym suma wartosci jest największa.
Oczywiscie ten plik tekstowy co podałem to najprostszy przyklad, ale zadanie wykonuje na pliku tekstowym ktory ma 10000 rzędów i 100 kolumn.
Jeden sposob to po kolei w funkcji sumuję każdy możliwy prostokąt i porównuję czy suma jest wieksza od maksymalnej sumy.
Natomiast drugi sposob to robię tablicę sum prefiksowych, dodatkowo sumuję kolumny i z odpowiedniego wzoru dla kazdego x,y tablicy odejmuje niechciane fragmenty (co jest o wiele bardziej optymalne) i porównuję czy dana suma jest wieksza od sumy maksymalnej. O dziwo wariant z tablicą prefiksową działa o wiele wiele wolniej ... Nie wiem co jest tego powodem.
Oczywiście jeżeli chodzi o znajdywanie maksymalnej sumy to ten wariant który powinien byc bardziej optymalny wykonuje 6 razy mniej operacji elementarnych. Czy to mozliwe zeby sumowanie kolumn bądź wczytywanie z pliku liczb i tworzenie od razu tablicy sum prefiksowych zajmowała o tyle więcej czasu? ;/
0
0
Czy to możliwe? Jasne. Kod można popsuć na wiele sposobów. Jak tobie udało się tego dokonać? Nie wiemy.
0
patrząc na ten tekst zgaduje, że brakuje przecinka :P