Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Hota si cu filtru ei, cascadorii ...

Accesare conturi e-mail de sub Li...

Recomandare doctor/laborator anal...

Abonament date fara perioada cont...
 Optimizare router pentru torent

Sfat achizitionare smartphone

Laborator Java

acces clicknet mail de pe interne...
 formular taxe USA

Informatica Cluj sau Timisoara

Unde gasesc monitor de 12-13-14&#...

Intreruperi arhitectura 8086.
 Sfat achizitie telefon

Livrarea "gratuita" tocma...

De ce firmele europene si america...

Ce SSD sa aleg ?
 

Forumul Softpedia folosește "cookies" pentru a oferi utilizatorilor o experiență completă. Vezi detalii sau închide mesaj (x)

Tema Programare Dinamica

  • Please log in to reply
11 replies to this topic

#1
Mitza444

Mitza444

    Junior

  • Grup: Members
  • Posts: 123
  • Înscris: 18.05.2011
  • ID membru: 687,927

Buna!! Incerc si eu sa invat programarea dinamica,dar nu am gasit pe net ceva din care sa pot intelege calumea.M-am uitat peste tutorialul de pe topcoder am inteles cat de cat in afara de partea cu grafuri(care nu le stiu pentru ca  nu cred ca trebuie la olimpiada la a X-a),m-am uitat si peste rezolvarea la problema rucsacului de pe infoarena,dar cand incerc sa fac probleme cu programare dinamica nu am nici o idee.....:|

Ma puteti ajuta sa-mi explicati mai bine programarea dinamica si eventual sa-mi dati ceva probleme(pt. incepatori) sa rezolv ??:D

Edited by Mitza444, 02 September 2011 - 20:59.


#2
edy_3dz

edy_3dz

    Rau sau bun

  • Grup: Senior Members
  • Posts: 3,049
  • Înscris: 30.08.2008
  • ID membru: 365,112
  • Locație: Brasov/Cluj-Napoca
Nu exista un algoritm universal, ci mai degraba un mod de gandire. Ia cartea Emanuelei Cerchez, "Programarea in limbajul C/C++ pentru liceu", Editura Polirom, volumul 2, o buna parte e despre programarea dinamica, poate te ajuta mai mult decat te poate ajute cineva pe forum.

#3
secretalex92

secretalex92

    Active Member

  • Grup: Members
  • Posts: 1,496
  • Înscris: 28.12.2008
  • ID membru: 401,522
  • Locație: Timisoara
Programarea dinamica  poate fi considerata cea mai grea metoda de programare. Cum am mai zis, ea presupune sa poti sa abstractizezi problema, sa o imparti in subprobleme pe care le rezolvi independent si le combini dupa o formula/o anumita logca pentru a obtine raspunsul. Cum a zis si @edy_3dz nu exista un anumit tipar, trebuie doar multa munca pentru a-ti da seama cum se pune problema. Acea problema a rucsacului se rezolva ca si prima problema prezentata in tutorialul de pe topcoder. Uite niste probleme de dinamica pentru incepator ( logic ca unele problemele se pot rezolva, poate mai simplu, si fara programare dinamica )  :
http://infoarena.ro/problema/scmax
http://community.top...l...ent&pm=1259
http://community.top...l...402&rd=5009
http://infoarena.ro/problema/ssm
http://infoarena.ro/problema/podm
http://community.top...l...918&rd=5006
http://infoarena.ro/problema/stirling
http://campion.edu.r...g...de&id=32752
http://campion.edu.r...g...de&id=27129
http://campion.edu.r...g...view&id=513
http://campion.edu.r...g...view&id=793
http://campion.edu.r...g...view&id=344
http://campion.edu.r...g...view&id=485
http://campion.edu.r...g...view&id=599
http://campion.edu.r...g...iew&id=1240
http://campion.edu.r...g...iew&id=1079
http://fiicompetitio...t_viena_2_3.pdf
http://fiicompetitio..._sablon_2_4.pdf
http://infoarena.ro/problema/cmlsc
http://infoarena.ro/problema/rmq
http://infoarena.ro/problema/lca
http://infoarena.ro/problema/hamilton

#4
Mitza444

Mitza444

    Junior

  • Grup: Members
  • Posts: 123
  • Înscris: 18.05.2011
  • ID membru: 687,927
Am incercat sa rezolv problema pachete de pe .campion si am gasit o recurenta ,dar nu e chiar buna pt. ca la unele teste cum ar fi exemplul 2 nu merge.......
Va puteti uita un pic peste cod sau sa-mi dati niste indicatii cum sa fac problema:D
#include<cstdio>
using namespace std;
int max(int a, int B){
	if(a>b)return a;
return b;
}
int min[100001],d[100001],i[100001];
int main(){
	int n,k;
	FILE * pFile;
	pFile=fopen("pachete.in","r");
	fscanf(pFile,"%d",&n);
	for(k=1;k<=n;k++){
		fscanf(pFile,"%d%d",&i[k],&d[k]);
	}
	for(k=1;k<=n;k++){
		min[k]=d[k]+max(0,min[k-1]-i[k]);
	}
	pFile=fopen("pachete.out","w");
	fprintf(pFile,"%d",min[n]);
	return 0;
}


Secretalex92 mai poti pune o data linku de la primele 2 probleme de pe .campion pt. ca atunci cand dai click pe link imi intra pe campion si imi da "eroare acces interzis"......

#5
Mitza444

Mitza444

    Junior

  • Grup: Members
  • Posts: 123
  • Înscris: 18.05.2011
  • ID membru: 687,927
Mda am reusit pana la urma sa rezolv problema de 100p dar nu stiu sigur daca am folosit programare dinamica
Va puteti uita peste cod sa-mi ziceti daca e programare dinamica sau nu si daca nu e cum as putea face cu programare dinamica??:D
#include<cstdio>
using namespace std;
int max(int a, int B){
	if(a>b)return a;
return b;
}
int d[100001],i[100001];
int main(){
	int n,k,dif,min;
	FILE * pFile;
	pFile=fopen("pachete.in","r");
	fscanf(pFile,"%d",&n);
	for(k=1;k<=n;k++){
		fscanf(pFile,"%d%d",&i[k],&d[k]);
	}
	min=d[1];
	for(k=2;k<=n;k++){
		dif=d[k]-i[k-1];
		min=min+max(0,dif);
		if(dif<0)i[k]=i[k]-dif;
	}
	pFile=fopen("pachete.out","w");
	fprintf(pFile,"%d",min);
	return 0;
}



#6
secretalex92

secretalex92

    Active Member

  • Grup: Members
  • Posts: 1,496
  • Înscris: 28.12.2008
  • ID membru: 401,522
  • Locație: Timisoara
Da este dianmica
http://campion.edu.r...g...view&id=261
http://campion.edu.r...g...iew&id=1072

#7
Mitza444

Mitza444

    Junior

  • Grup: Members
  • Posts: 123
  • Înscris: 18.05.2011
  • ID membru: 687,927
Imi puteti spune de ce imi da ciclu infinit si dupa aceea eroare??problema este lacusta de  pe .campion
#include<cstdio>
using namespace std;
int A[101][101],B[101][101];
int main(){
	int m,n,i,j,x,y,x1,y1,min;
	FILE * pFile;
	pFile=fopen("lacusta.in","r");
	fscanf(pFile,"%d%d",&m,&n);
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			fscanf(pFile,"%d",A[i][j]);
		}
	}
	B[2][1]=99999;
	min=99999;
	for(i=2;i<=n;i++){
		B[2][i]=A[1][1]+A[1][i]+A[2][i];
		if(B[2][i]<min){x=2;y=i;min=B[2][i];}
	}
	for(i=3;i<=m;i++){
		min=99999;
		for(j=1;j<=n;j++){
			if(y!=j){
			B[i][j]=A[i-1][j]+A[i][j]+B[x][y];
			if(B[i][j]<min){min=B[i][j];x1=i;y1=j;}
			}
		}
		x=x1;y=y1;
	}
	pFile=fopen("lacusta.out","w");
	fprintf(pFile,"%d",B[x][y]);
	return 0;
}



#8
secretalex92

secretalex92

    Active Member

  • Grup: Members
  • Posts: 1,496
  • Înscris: 28.12.2008
  • ID membru: 401,522
  • Locație: Timisoara

View PostMitza444, on 5th September 2011, 11:38, said:

fscanf(pFile,"%d", &A[i][j]);
Unde ai judecat cazul cand  y == j  ? Da si acesta trebuie tratat :P
PS: Esti sigur ca-ti intra in ciclul infinit ?

Edited by secretalex92, 06 September 2011 - 08:05.


#9
Mitza444

Mitza444

    Junior

  • Grup: Members
  • Posts: 123
  • Înscris: 18.05.2011
  • ID membru: 687,927
Mda ai avut dreptate a trebuit sa iau si cazul y==j

Dar am o alta intrebare la problema jucarii de pe .campion..

Eu m-am gandit asa sa fac un backtracking recursiv care imi genereaza toate solutiile in ordine lexicografica si la fiecare solutie pe care o gasesc sa fac verificarea daca are un subsir crescator de cel putin k elemente si de fiecare data cand gasesc un astfel de sir cresc o variabila care cand este egala cu p afisez solutia.
Problema e ca nu cred ca am facut bine functia care determina subsirul crescator + imi pica la timpul de executie la un test si la unul iau killed by signal 11 :|
Cum as puteam face determina subsirului in alt mod mai eficient??
Aici e codul:
#include<cstdio>
using namespace std;
int a[12],b[12],k,p,nr=0;
FILE * pFile;
void dinamic(int l){
	int s[13],j;
	s[1]=1;
	for(j=1;j<l;j++){
		if(a[j]<a[j+1]){
			s[j+1]=s[j]+1;
		}
	}
	if(s[l]>=k)nr++;
	pFile=fopen("jucarii.out","w");
	if(nr==p){
		for(j=1;j<=l;j++)
			fprintf(pFile,"%d ",a[j]);
	fprintf(pFile,"\n");
	}
}
void back(int x,int len){
	int i;
	if(x-1==len){
		dinamic(len);
	}
	else {
		for(i=1;i<=len;i++){
			if(!b[i]){
				a[x]=i;
				b[i]=1;
				back(x+1,len);
				b[i]=0;
			}
		}
	}
}
int main(){
	int n;
	pFile=fopen("jucarii.in","r");
	fscanf(pFile,"%d%d%d",&n,&k,&p);
	back(1,n);
	return 0;
}



#10
secretalex92

secretalex92

    Active Member

  • Grup: Members
  • Posts: 1,496
  • Înscris: 28.12.2008
  • ID membru: 401,522
  • Locație: Timisoara

Da, nu ai rezolvat bine dinamica. Uite un teste pe care ar pica
1 2 -1 -1 -1 3
Raspuns corect :   1 2 3
Vezi ca faci o confuzie intre subsecventa si subsir. Prima presupune ca elementele pe care le contine sa fie consecutive in sir, iar la subsir nu. Daca avem (xn), n natural nenul,  atunci un subsir este xi, xj, xk, ... cu conditia ca 0<i<j<k<... <=n => elementele unui subsir nu sunt neaparat consecutive.

#11
Mitza444

Mitza444

    Junior

  • Grup: Members
  • Posts: 123
  • Înscris: 18.05.2011
  • ID membru: 687,927
1.Da ai avut dreptate nu era bine programarea dinamica am refacut-o si a mers....
2.La problema suma4 de pe .campion dupa ce determin numara de niveluri sa fac un for(i=1;i<=m;i++) si la fiecare pas sa pun nivelul respectiv in matrice(adica pun prima data 1 care are numai o casuta dupa pun nivelul 2 care are 4 casute si tot asa....) si la fiecare nivel sa adun minimum de pe nivelul anterior in cele 3 casute in care pot merge.Ar fi buna ideea??:D

#12
secretalex92

secretalex92

    Active Member

  • Grup: Members
  • Posts: 1,496
  • Înscris: 28.12.2008
  • ID membru: 401,522
  • Locație: Timisoara

View PostMitza444, on 10th September 2011, 21:50, said:

Ar fi buna ideea?? :D
Poti sa incerci si sa vezi :). Dar, da e buna. Si sper ca atunci cand zici matrice te referi la una cu 3 dimensiuni.

Reclamă

Bun venit pe Forumul Softpedia!

0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users