[es] - Backtracking & Dinamičko programiranje HELP

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Backtracking & Dinamičko programiranje HELP

^{11.05.2005. u 19:01 - pre 230 meseci}

Pozdrav,
Možda izgleda da ja samo očekujem gotova rešenja, ali stvarno nije tako. Imam problem sa ova dva zadatka. Već pet dana pokušavam da odradim to. Ovo mi je za domaći koji mi utiče na ocjenu iz ovog ispita. Dakle imam neke verzije ovih programa ali to nisu konačne. Treba još da se izmijene. Meni bi ovo trebalo što prije, tj.rok za predaju je sjutra, ali i ako ne odradim to za sjutra svakako me interesuju algoritmi za ova dva problema.

Problem 1.(Backtracking) Napisati rekurzivnu funkciju int NajkraciPut koja izračunava i vraća dužinu najkraćeg puta u lavirintu i štampa najkraći put.
lavirint.cpp Ova verzija ovog problema traži samo put, ali ne i najkraći put.

Problem 2. (Dinamičko programiranje) Dozvoljene operacije nad stringom su: umetanje jednog slova, brisanje jednog slova, izmjena jednog slova i brisanje svih slova do kraja riječi. Svaka od operacija ima zadatu cijenu. Napisati program koji za date stringove P i Q i zadate cijene svih operacija određuje najmanju ukupnu cijenu operacija potrebnih da se od stringa P dobije string Q. Program treba da štampa koje se operacije primjenjuju.
diference.cpp Ova verzija ovog problema ne ispisuje i koje se operacije primjenjuju.

... Mu .... Mu ...

Prikačeni fajlovi

programi.zip - 1.83k

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: Backtracking & Dinamičko programiranje HELP

^{12.05.2005. u 23:51 - pre 230 meseci}

Problem 1
Znaci obican backtrack. Pocnes od pocetka lavirinta, pamtis globalnu promenljivu dubina. Kad si na nekom polju, povecas dubinu, obelezis ga da si ga proso, i obidjes njegova 4 susedna (pretpostavljam da se tako krece kroz lavirint), pa ako neko od njih nije prodjeno pozivas se rekurzivno za njega. Pre izlaska iz rekurzije obelezis polje ponovo kao da ga nisi proso i smanjis dubinu za 1. Ako u nekom trenutku stignes do kraja, samo proveris da li je dubina bolja od dosad najboljeg (najkraceg) resenja, pa ako jeste updateujes resenje.

Problem 2
Prilicno straightforward dinamicki. Pamtimo niz cena [i, j], sto predstavlja minimalnu cenu da se od prvih i karaktera stringa P dobije prvih j karaktera stringa Q. Resenje ce biti cena [x, y], gde je x duzina P, a y duzina Q. Matricu cena pravimo dinamicki trivijalno. Slozenost O (x*y).

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Odgovor na temu