Witam,
Mam problem z napisaniem programu, który będzie działał w taki sposób, że:
Załóżmy, że mam tablicę dwuwymiarową liczb int, o wymiarach m=10, n=8.
Teraz chciałbym, aby program zliczał/sumował po kolei wartości każdego prostokąta liczb np.: 2x3 i największą sumę i prostokąt zostawił.
Chodzi o to, że mam np.:
1 2 3 4 5 6 7 8
2 8 7 2 2 1 1 1
3 8 7 6 5 2 1 2
4 9 9 9 1 2 3 1
5 9 9 9 7 4 6 6
6 8 7 7 2 1 1 1
7 9 8 7 2 1 2 3
8 4 5 6 3 4 3 3
9 2 3 4 5 6 7 6
1 1 2 3 4 5 1 5
To widzę, że największą sumę dla prostokąta 2x3 uzyskam w rzędzie 4 i 5 na pozycjach 2 3 4 (licząc od jedynki).
No i właśnie nie mogę do końca wykombinować metody ;/
Myślałem nad stworzeniem dwóch tablic 2x3, w jednej przechowywalbym "maksymalny prostokąt", a druga tablica posłużyła by mi do wklepywania wartosci każdego innego prostokąta liczb i porównywania czy suma wartości jest większa czy mniejsza, ale niestety nie mogę jakoś dobrze wykminić funkcji tzn. pętli do uzupełniania tablic ;/ Ktoś coś pomoże / podpowie?
- Napisz metodę przyjmującą cztery argumenty:
x
,y
,width
orazheight
, która będzie sumować liczby wewnątrz wskazanego prostokąta. - Wywołuj w pętli tę metodę dla każdego punktu tablicy, od
0
dowymiar całej tablicy - wymiar prostokąta
, zapisując największy odnaleziony prostokąt.
Jeśli nie piszesz tego w C na zajecia i musi być na tablicach :P. To możesz zrobić tak. Wczytujesz wymiary prostokąta x,y; tworzysz y kolejek, każda kolejka to jeden rząd tablicy. i jedną zmienną suma. Każde i robisz tak że każde dodanie zmiennej do (jakiejkolwiek) kolejki zwiększa sume, a każde zdjecie wartości z początku ją zmiejsza. Jeśli suma jest większa od największej potrzedniej to robisz kopie kolejek(lub zapisujesz pozycje któregoś rogu) i uaktualniasz sume. Teraz zostaje CI napisanie funkcji. Wystarczy przesunąć ten twór po całej tablicy i wynik sam się znajdzie. Zostaje napisanie funkcji czyszczącej i inicjalizującej kolejki po dojściu do krawędzi.
edit. bo nie byłem pierwszy :P, ma stosowanie kolejek ma taką zaletę nad sprawdzaniem każdego kwadratu że pozwala wykorzystywać wcześniejsze wyniki. i komputer mniej sie poci.