Mogao si samo skenirati ispit/domaću zadaću, na taj način ne bi morao čak ni prepisati zadatak.

A sorry covjece, trazim pomoc oko rjesavanja ovog zadatka, ne moras odmah galamiti :P
i usput ide mogla si :)) :-*

w3bl0rd ti je lepo rekao. Način na koji se postavlja pitanje je u direktnoj vezi s ishodom teme. U normalnim okolnostima, samo bih je obrisao jer autor nije baš nista pokušao sa zadatkom, a to se ovde ne populariše. Naslov teme (MAtricaaaaaa !!!!) da ne pominjem.

Nisi rekao ŠTA je problem... Učitavanje elemenata matrice iz datoteke? Algoritam za određivanje maksimuma?

Da li si bilo šta samostalno zaključio? Na primer, da li je broj prolaza direktno vezan za vrednosti M i N? Bilo kakav komentar na zadatak, da zainteresuješ učesnike...


Takođe, od interesa je da se zna šta ste od oblasti radili pa ste dobili ovaj zadatak. Možda rekurzije ili samo petlje?

Opis zadatka:
Zadata je matrica dimenzija M, N (3£ M, N £100) ciji su elementi cijeli brojevi.
Sa nekog polja matrice iz prve kolone polazi skakac kome je dozvoljeno kretanje
(naravno, po pravilima šaha) ali samo udesno. Pri tome on sakuplja brojeve sa polja na
koja skoči.
Napisati program koji učitava datu matricu i nalazi put za koji je zbir sakupljenih brojeva
maksimalan.
Izvršni program mora se zvati SKAKAC.EXE.

Ulazna datoteka:
U prvom redu redu ulazne tekstualne datoteke SKAKAC.IN se nalazi se brojevi M i N
(broj redova i kolona) razdvojeni jednim razmakom, U sledećih M redova se nalazi N
elemenata (podaci za tabelu) razdvojeni jednim razmakom.

Izlazna datoteka:
U prvom redu izlazne tekstualne datoteke SKAKAC.OUT potrebno ispisati maksimalan
zbir.

Primjeri:
SKAKAC.IN
3 4
1 2 3 4
5 6 7 8
9 10 11 12
SKAKAC.OUT
26

Ovo je zadatak iz dinamičkog programiranja.

Ovo neće biti lako objasniti samo rečima...

Imaš polaznu matricu koja je puna nekih brojeva. Imaš zbirnu matricu istih dimenzija, koja je u početku popunjena nulama, i vrednosti iz prve kolone su iskopirane iz polazne matrice. Cilj je da u zbirnoj matrici "skupljaš maksimalne zbirove". Zbirnu matricu obrađuješ kolonu po kolonu, tako što za svako polje iz tekuće kolone gledaš kuda sve može da se skoči iz tog polja. Svaki put kad obrađuješ novi skok dodaješ novi sabirak iz polazne matrice na postojeću vrednost iz zbirne matrice. Ako je dati zbir veći od onog koji već stoji u doskočenom polju onda postavljaš tu novu vrednost u doskočeno polje. Kada se to desi faktički si pronašla bolje rešenje da se dođe do tog polja od onog koje si nešto ranije našla.

Teško je ovo rečima pojmiti, pa zato hajde da probamo primerom. Polazna matrica je data, i ja ću simulirati svaki od dvanaest koraka.

1 0 0 0   1  0 0 0   1  0  8 0   1 11  8 0   1 11  8  0  .  1 11 14  0   1 11 14  0   1 11 14  0   1 11 14 26   1 11 14 26 . .

5 0 0 0   5  0 8 0   5  0  8 0   5  0 16 0   5  0 16 19  .  5  0 16 19   5  0 16 19   5  0 16 19   5  0 16 19   5  0 16 19 . .

9 0 0 0   9 11 0 0   9 11 16 0   9 11 16 0   9 11 22  0  .  9 11 22  0   9 11 22 26   9 11 22 26   9 11 22 26   9 11 22 26 . .

                                                                                 14           16           22           26

Boldovano je polje koje trenutno obrađujemo, crveno su polja na koja trenutno polje može da utiče. U četvrtom redu je krajnji rezultat. Rešenje za ovaj primer je 26. Tačke između pete i šeste matrice označavaju da nije moguće dopreti do polja u kome stoji vrednost 6. Pošto nije moguće dopreti onda se i ne uzima u obzir. Ovde ima mali problem kako detektovati to polje, ali to ćemo nekom drugom prilikom. Tačkice posle poslednje matrice označavaju da obrada poslednja dva polja neće doneti veći zbir (to jest poslednja matrica bi se ponovila još dva puta, a rezultat bi ostao 26).

Nisam siguran da je Mihajlov algoritam sasvim OK. Ako se matrica popunjava sa leva na desno, onda ne treba posmatrati sva polja na koja se može preći sa trenutnog polja, nego sva polja sa kojih se na trenutno polje može doći.

Dakle, na početku su polja nepopunjena ili popunjena nekom vrednošću koja nema smisla, npr. -1. Cilj nam je da u svako polje upišemo maksimalan zbir koji se može ostvariti kretanjem sleva nadesno do tog polja. Ako su sva polja sa kojih se može doći na polje P izračunata, onda se na polje P upisuje maksimum vrednosti upisanih u ta polja uvečan za vrednost polja P iz polazne matrice. Naravno, na početku se sva početna polja (polja iz prve kolone) popunjavaju vrednostima iz polazne matrice, a onda se popunjava kolona po kolona.

Evo toka izračunavanja za gornji primer:


1 -1 -1 -1 | 1 11 -1 -1 | 1 11 14 -1 | 1 11 14 26
5 -1 -1 -1 | 5 -2 -1 -1 | 5 -2 16 -1 | 5 -2 16 19
9 -1 -1 -1 | 9 11 -1 -1 | 9 11 22 -1 | 9 11 22 26


Polje u drugoj vrsti i drugoj koloni sam popunio sa -2 kao polje u koje se ne može doći. U opštem slučaju ga treba popuniti nekom besmislenom vrednošću različitom od početne i tako obeležena polja ne uzimati u obzir prilikom obrade sledećih polja.

ovaj zadatak je bio zadan prosle godine na takmicenju iz informatike za srednje skole

Mali Off:

Ovakvi zadaci su redovni na takmicenjima za srednje skole.

Pre 22 godine sam na jednom republickom takmicenju imao skoro isti zadatak, takodje matrica, takodje optimalna putanja, takodje maksimalna suma vrednosti, takodje skup pravila za sumiranje vrednosti.

Tada nisam bio vest sa rekurzijama (nisam ni sada bog zna koliko, al umem da se snađem), pa sam smislio neki "svoj" sistem gde sam koristio veštački "stek" trenutne pozicije i poštovao redosled pravaca, koje definišem vektorski. Kada bih iscrpeo jednu putanju, prelazio bih na novu uzimanjem sledeće moguće pozicije sa tog "steka". Nije lako za objasniti ukratko recima, kao sto rece Mihajlo, ali to je ideja.

Kasnije sam ukapirao da tim "stekom" nisam izmislio toplu vodu, već je to jedan od klasicnih nacina, koji je praktično priprema da se momentalno kod zameni rekurzijom.



Na takmicenjima su u opticaju slicni zadaci s odredivanjem maksimalne sume spojenih "kečeva" među "nulama" i sl. Zatim optimalne putanje unutar matrice ili čak kocke. Ukratko, taj tip zadataka se lako realizuje ako se dobro shvati par algoritama, a kasnije se sve vrti u krug. Ipak, najžalosnije je što na saveznim takmičenjima najšešće mentori samih takmičara daju predlog za neki zadatak, pa pobeđuju uvek iste "škole".

Samo sam jednom imao priliku da vidim da profesor (na veliku žalost, ne znam mu ime da ga pohvalim) odbija da se složi da se neki zadatak uvrsti na listu, jer su njegovi đaci taj zadatak već više puta radili na vežbama i svi znaju da ga urade ?! Za takav gest fer pleja skidam kapu, ovo se ne viđa često.

Inače, u moje vreme je omiljeni lik za davanje "nerešivih" zadataka bio legenda - Jožef Kratica.


@Nedeljko
Pretpostavljam da znas, ali ipak da podsetim, postoje [pre] i [/pre] tagovi za fiksne fontove ako ti zatreba. U okviru njih je moguce i bojenje, kao sto je Mihajlo uradio.

Auu de se njega seti... On je drzao vezbe iz fortrana na MF... kakav nerd, stalno je pricao matematicke viceve...

On je valjda danima smišljao zadatke i rešavao ih, a kasnije "natera" takmičare da za tri sata urade dva zadatka, od kojih je jedan taj "njegov", teži. Ako se dobro sećam, trebalo je imati i dobro znanje matematike, ono kao prethodno utvrditi složenost algoritma i sl. Često se i nije unapred znalo da li zadatak ima rešenje, već je i to trebalo "nekako" kodom i/ili matematički dokazati.

Ovo je zadatak pronalaženja optimalne putanje u orjentisanom grafu. 93' je takav zadatak bio na međunarodnoj olimpijadi u Argentini, a pre toga je u "Računarima" postavljan dva puta u okviru "Dejanovih pitalica".



Rekurzija, ili uopšte pretraga sa vraćanjem (backtracking) je ovde pogrešan pristup zbog eksponencijalne složenosti.

^
Slažem se.

U ličnoj arhivi imam knjigu od Dragana Uroševića:
http://www.elitesecurity.org/t24538
http://www.mikroknjiga.rs/store/prikaz.php?ref=86-7555-055-3
... koja dosta dobro pokriva ovu tematiku i koju sam nekada koristio.