Aathma

Programarea dinamica este o metoda care descompune o problema in mai multe subprobleme si prin rezolvarea lor si combinarea rezultatelor se obtine un rezultat final. Subproblemele nu sunt independente (cum sunt la metoda Divide et impera). Prin urmare, vom rezolva subproblemele o singura data si retinem rezultatele intr-o structura de date suplimentara. Am ales sa fac un tutorial despre PD pentru ca multi considera a fi o metoda grea fata de celelalte. Se iau in considerare urmatorii pasi cand vine vorba despre programarea dinamica: - Se cauta subproblemele problemei - Se alege o structura de date care poate sa retina informatiile din subprobleme - Se foloseste o relatie de recurenta - Pentru a determina solutia finala, se rezolva relatia de recurenta in mod "bottom-up" (Ce-i mai sus e inspirat din Programarea in limbajul C/C++ pentru liceu, volumul II. O carte buna, o recomand. Are cateva greseli care s-ar putea sa va duca in eroare, dar daca esti atent nu apar probleme) Cum prin teorie nu poti intelege informatica am sa prezint doua probleme care sa va lumineze si sa va indrume in magia programarii dinamice. Clasica problema de determinarea celui de-al n-lea termen al sirului Fibonacci. Relatia de recurenta care sta la baza determinarii celui de-al n-lea termen al sirului Fibonacci este: fib(x) = { 1, x<=2 { fib(x-1) + fib(x-2), x>2 Daca am rezolva recursiv ar fi foarte ineficient. int fib(int n) { if(x<=2) return 1; return fib(n-1)+fib(n-2); } Schema apelurilor recursive e in forma de arbore binar si ca sa calculezi fib(4) fib(2) trebuie calculat de 2 ori, fib(1) de 3 ori si fib(0) de 2 ori. Foarte ineficient. In schimb, folosind un vector si metoda programarii dinamice, lucrurile devin mai frumoase: int fib(int n) { int A[50]; //structura de date despre care povesteam unde retinem solutiile if(n<=2) return 1; A[0]=A[1]=0; for(int i=2; i<n; ++i) { A[i]=A[i-1]+A[i-2]; } return A[n-1]; } ATENTIE, NU ARE LEGATURA CU PROGRAMAREA DINAMICA! E DOAR PENTRU CEI CARE DORESC SA INVETE MAI MULT! Pentru cei ce doresc sa invete mai mult, se poate optimiza algoritmul folosind matricea. A=(0 1) (1 1) Termenul (2; 2) din matricea An-1 este al n-lea termen fibonacci. Pentru a optimiza inmultirile faci o ridicare la putere in timp logaritmic si...gata! Lacusta Prima mea problema legata de programarea dinamica. Problema se poate gasi aici: http://varena.ro/problema/lacusta Pentru a retine solutiile subproblemelor (determinarea sumei minime care se poate obtine pronin din coltul din stanga sus pana la fiecare element A[j] al matricei) vom construi o matrice B cu m linii si n coloane, cu semnificatia ca B[j] reprezinta suma minima care se poate obtine din coltul stanga-sus pana la elementul A[j]. Solutia problemei date este min(B[m-1][j]) (unde j=0,1,,2,3,...,n-2) + A[m-1][n-1] Relatia de recurenta: B[0][0] = A[0][0] B[0] = unsigned(-1), unde 0<i<n B[1][0] = unsigned(-1) B[1][j] = A[0][0] + A[0][j] + A[1][j], unde 0<j<n B[j] = A[j + A[i-1][j] + min(B[i-1][k]), unde 0<=k<n Pentru a ajunge in A[j am facut un pas de pe A[i-1][j], iar pentru A[i-1][j] am facut un salt A[i-1][km] de pe care se face saltul este ales astfel incat B[i-1][km] = min(B[i-1][k]), unde 0<=k<n Se gasi o problema in momentu' in care calculezi matricea B. Sunt sanse ca elementul minim de pe coloana i-1 sa se gaseasca pe coloana j de unde faci pasu'. Ca sa evitam calculam min1 si min2, doua valori minime de pe linia i-1. #include <fstream> #define NMAX 101 using namespace std; ifstream in("lacusta.in"); ofstream out("lacusta.out"); int main() { unsigned A[NMAX][NMAX], B[NMAX][NMAX], m, n, min1, min2, jmin; in>>m>>n; for(int i=0; i<m; ++i) { for(int j=0; j<n; ++j) { in>>A[i][j]; } } B[1][0]=unsigned(-1); for(int i=1; i<n; ++i) { B[1][i]=A[0][0]+A[0][i]+A[1][i]; } for(int i=1; i<m-1; ++i) { if(B[i][0]<=B[i][1]) { min1=B[i][0]; min2=B[i][1]; jmin=0; } else { min1=B[i][1]; min2=B[i][0]; jmin=1; } for(int j=2; j<n; ++j) { if(B[i][j]<min1) { min2=min1; min1=B[i][j]; jmin=j; } else { if(B[i][j]<min2) { min2=B[i][j]; } } } for(int j=0; j<n; ++j) { if(j!=jmin) { B[i+1][j]=min1+A[i][j]+A[i+1][j]; } else { B[i+1][j]=min2+A[i][j]+A[i+1][j]; } } } min1=B[m-1][0]; for(int j=1; j<n; ++j) { if(B[m-1][j]<min1) { min1=B[m-1][j]; } } out<<min1+A[m-1][n-1]<<'\n'; return 0; } Poate fi optimizata sursa. Cu mult. Nu este nevoie de o matrice B cu m*n elemente, ci doar de o matrice B cu 2*n elemente. O optimizare si mai buna: poti rezolva problema cu o matrice simpla de n*n elemente. Mai mult decat atat, elementele sunt <= 255. Altceva despre care trebuie sa tineti cont. Puteti incerca sa vedeti daca puteti optimiza sursa pe site-ul infoarena: http://www.infoarena.ro/problema/lacusta

Ador muzica reggae. Sunt o persoana sensibila care nu isi arata cu adevarat emotiile. Din acest motiv emotiile mele functioneaza ca o lovitura : rana se vindeca, dar cicatricea ramane. Dar ca sa-mi vindec "ranile" imi este greu, singurul leac care exista este timpul. Rabdarea nu este intocmai punctul meu forte si in anumite momente ma simt coplesit de situatie. In acele imprejurari ascult muzica reggae si ma calmez, uit de tot si de toate si ma ridic din punct de vedere moral pentru a-mi continua ziua. Ele fac referire in majoritatea cazurilor la pace, iubire si ganja (cannabis), deci nu doar linia melodica ma face sa ma simt bine, ci si versurile.

@Ace Ventura Nu mai zic nimic ! Programul are un algoritm destul de usor. Eu l-am inteles. Bravo pentru "munca" depusa. +1

1 stock de iron ingot? E prea mult (bucurate ca is cinstit xD). 25-30 iron ingot. Cam atat ar fi. Vorbim ingame.

Nickname: Steel_Two Obiect detinut ( care dai la schimb ): Vila (cabana) din lemn. Poze : Casa pe dinafara : Holul : Bucataria : Dormitor : Scari : Dormitor : Baie (are o cada cu apa fierbinte si o cabina de dus) : Terenul de fotbal : Mina (Vreau sa mentionez ca in mina asta am facut 2 stockuri de coal intr-o zi) : Vreau sa mai mentionez ca o sa i-au paturile/cufarele/tablourile cu mine. Obiect dorit ( care ceri la schimb ): Oferiti voi. In special vreau iron ignot. Alte precizari: Contactati-ma ingame sau postati in topicu' asta daca sunteti interesat.

Cand intru pe server nu imi apare toata mapa . Am bugul asta de azi dimineata . Niste poze v-ar ajuta sa intelegeti mai bine : #1. Cadeam si cadeam... si cadeam.... #2. ---------------------||---------------------- #3. ---------------------||---------------------- #4. La un moment dat nu mai cadeam si am "aterizat" pe un brick invizibil cred, dar imi scadea viata. Daca ii de la server faceti-l mai repede, ca vreau sa joc =(. Daca ii de la mine spuneti-mi cum pot rezolva... Steel_Two ©

Ops, n-am vazut ca nu se mai voteaza, vina mea (Edited)

Eu plec 1 saptamana, deci va spun bafta tuturor . Si nb. Ne vedem peste 1 saptamana <'> ( omg, primu meu post la discutii )) )

Bafta, nu o sa va uit . Daca zeby o sa se uite aici, ii multumesc mult ca mi-a acordat o sansa in Corleone. Nu o sa va uit <'>. Succes in continuare

Distractie placuta razvan <'>. Mda, n-am mai putut sta la war . Uitati ceva : 26 User(s) are browsing this forum (3 Visitor/s and 0 Anonymous Members) 23 Members : SteelTwo, Claudiu2010, Snik, ALecSunder, d3m0, Rydder, Smyley, KeNv, Blake, DarkSweeT, UzZi, alxbm, WhiskY, ATI, Familistu, TohaNeaNuVLad, Kaddylack, Rizi, F4L Balon, Blaki, ecKeDu, Trojan, sKillz Asta la "cereri unban" . O gramada, doar pentru ca UzZi a luat ban . UzZi se pare ca este destul de respectat pe sv., ca pun pariu, toti vor sa ia unban (inclusiv eu )

Neata Corleone

Noapte buna corleone. Sper sa ajung la antrenamente . In seara asta nu mai pot intra pe sa-mp, daca intru imi creeaza un lag de speriat . Vise placute <'>

Deci se pare ca n-am intarziat la niciun targ .

Salut. Bine facem, bine bine . Mda, azi nu am putut veni la targ, am fost plecat in oras. Sper sa pot merge maine..

Neata Corleone. Sebi, pacat ca ai plecat din Corleone, iti voi ura succes in continuare si sper ca intr-o zi sa te reintorci. Bafta !! Welcome Bill.

Salut Corleone si Welcome back Michael. .

Din cate vad nu doar eu . Mama, ma uit acum la ceas si nu pot crede ca m-am trezit la 9

Neata Corleone

EzW, da tu la cat te scoli tata? Doamne ce san andreas pot avea.. nu ma lasa sa intru in joc . Single-Player merge, da sa-mp nu . Mi-am reinstalat sa-mpu, da tot asa face.. Nush daca voi fii si maine inactiv .. sper sa nu.. o sa incerc sa downloadez un al sa.. Bafta oricum

Schultz, am citit la "Cereri demisi Corleone" sau cum era titlu.. Iesi din corleone doar ptc n-ai luat rank up? . Nici eu n-am luat.. si nu is suparat . Chiar nu meritam + ca nu prea ma intereseaza rankul . Mai mult ma intereseaza ca am ajuns in Corleone . Mai ramai..?

Neata. Uau, primu meu post la discutii .

e mai tare logou taxi asta . imi place de mii de ori mai mult ca celalalt (celalalt era doar scris) . [G]ood[J]ob

noapte buna tuturor . sa aveti vise placute

salut si bine ai venit . defapt, acum la ora asta ar trebui sa spun nb . Sh mersi pingu . alea is prea faine . o sa pun una din astea la pagina mea b-zone . sper ca nu te superi

Nu s-a mai tinut eventul, pentru ca TOTI cei inscrisi nu au venit.. Am asteptat aprox. 10 minute, si nimeni.. Nu cred ca voi mai tine event, pentru ca chiar daca voi mai tine, nu cred ca veti veni..