15 martie 2010

Probleme cu programare dinamica

1.
//fie un tablou de dimensiune n x m , alcatuit doar din 1 sau 0 .
// de afisat cel mai mare patrat care poate fi asezat doar pe pozitiile de 1 din matrice
//se afiseaza coltul din dreapta jos si dimensiunea patratului
// complexitatea sa fie O(n*m)

#include "stdio.h"
#include "stdlib.h"

int **a, **c, n , m;

int minim(int i, int j) {

int min1=c[i][j-1], min2=0;
if(c[i-1][j] > c[i-1][j-1])
min2 = c[i-1][j-1];
else min2 = c[i-1][j];
return min1>min2? min2:min1;
}

int main() {

FILE *f = fopen("in","r");
int i,j;
fscanf(f,"%d %d",&n,&m);
a = (int **)malloc(n*sizeof(int));
c = (int **)malloc(n*sizeof(int));
for( i=0; i < n; i++) {
a[i]=(int *) malloc(m*sizeof(int));
c[i]=(int *) malloc(m*sizeof(int));
}

for(i=0; i < n ; i++ )
for(j=0; j < m ; j++ )
{fscanf(f,"%d", &a[i][j]);
if(i == 0 || j ==0)
c[i][j] = a[i][j];
}

for(i=1; i < n ; i++)
for(j=1 ; j < m ; j++)
if(a[i][j]) c[i][j] = 1 + minim(i,j);
else c[i][j]=0;

int max =0, ii=0, jj=0;
for(i=0; i < n ; i++)
for(j=0; j < m ; j++)
if(c[i][j]>max) { max = c[i][j]; ii=i; jj=j; }

printf("colt dreapta jos %d %d\nDimensiune %d\n",ii,jj,max);

return 0;
}

2.
// avem N dreptunghiuri de dimensiune variabile,date prin lungime si latime
// de aflat cel mai mare nr de dreptunghiuri incluse unul in altul
//analiza intr-o anumita ordine


#include "stdio.h"
#include "stdlib.h"

typedef struct dr { int x; int y;} drept;

int n;
drept * d;
int *best ;

int maxim (int i) {

int j, max = 0;
for(j=0; j < i ; j++)
if( best[j] > max && d[j].y > d[i].y )
max=best[j];
return max;

}

int main() {

FILE *f = fopen("intr","r");
fscanf(f,"%d",&n);
d = (struct dr*)malloc(n*sizeof(struct dr));
int i,j,k;
for(i=0; i < n ; i++ ) {
fscanf(f,"%d %d", &j, &k);
d[i].x = j; d[i].y=k; }
best = (int *)malloc(n*sizeof(int));

// sortare descrescatoare dupa x
int ok;
drept aux;
do {
ok=0;
for(i = 0; i < n-1; i++)
if( d[i].x < d[i+1].x ) {
ok=1; aux = d[i]; d[i]=d[i+1]; d[i+1]=aux; }
} while(ok);

for(i=0; i < n ; i++ )
best[i]=1;

for(i=1; i < n ; i++ )
best[i] = 1 + maxim(i);

int max=0;
for(i=0; i < n ; i++ )
if(max < best[i]) max = best[i];
printf("Nr max este %d\n", max);
return 0;
}

Niciun comentariu: