Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
Palm Treo 500v

Info garantie internationala

M-a ”agatat” una pe F...

Shell root
 Cisco RV180W E-K9-G5

Wi Fi

Sfat.

eroare windows 8.1
 X1 vs P7 vs S4

Pareri despre Cantarul E-Boda BS...

Va merge yotube normal?

living room mansarda
 Accident intersectie Lizeanu

[TEMĂ] Afisare distanța maxima in...

BlitzSound

Olive Kitteridge (2014)
 
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,050
  • Î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