Difference between revisions of "Clasa a XI-a lecția 9"

From Algopedia
Jump to: navigation, search
(Created page with "= Programarea Dinamica = == Descrierea metodei == Programarea dinamică, asemenea metodelor divide şi stăpâneşte, rezolvă problemele '''combinând soluţiile unor subpro...")
(No difference)

Revision as of 10:09, 29 November 2019

Programarea Dinamica

Descrierea metodei

Programarea dinamică, asemenea metodelor divide şi stăpâneşte, rezolvă problemele combinând soluţiile unor subprobleme. (În acest context, termenul de “programare” se referă la o metodă tabelară şi nu la scrierea codului pentru un calculator) Algoritmii divide şi stăpâneşte partiţionează problema în subprobleme independente, rezolvă recursiv subproblemele şi apoi combină soluţiile lor pentru a rezolva problema iniţială.

Spre deosebire de această abordare, programarea dinamică este aplicabilă atunci când subproblemele nu sunt independente, adică subproblemele au în comun sub-subprobleme. În acest context, un algoritm de tipul divide şi stăpâneşte ar presupune mai multe calcule decât ar fi necesar dacă s-ar rezolva în mod repetat sub-subproblemele comune. Un algoritm bazat pe programare dinamică rezolvă fiecare sub-subproblemă o singură dată şi, apoi, memorează soluţia acesteia într-un tablou, prin aceasta evitând recalcularea soluţiei ori de câte ori respectiva sub-subproblemă apare din nou. În general, metoda programării dinamice se aplică problemelor de optimizare.

Asemenea probleme pot avea mai multe soluţii posibile. Fiecare soluţie are o valoare, iar ceea ce se doreşte este determinarea soluţiei a cărei valoare este optimă (minimă sau maximă). O asemenea soluţie se numeşte o soluţie optimă a problemei, prin contrast cu soluţia optimă, deoarece pot fi mai multe soluţii care realizează valoarea optimă. Dezvoltarea unui algoritm bazat pe programarea dinamică poate fi împărţită într-o secvenţă de patru paşi.

1. Caracterizarea structurii unei soluţii optime. 2. Definirea recursivă a valorii unei soluţii optime. 3. Calculul valorii unei soluţii optime într-o manieră de tip “bottom-up”. 4. Construirea unei soluţii optime din informaţia calculată.

Paşii 1–3 sunt baza unei abordări de tip programare dinamică. Pasul 4 poate fi omis dacă se doreşte doar calculul unei singure soluţii optime. În vederea realizării pasului 4, deseori se păstrează informaţie suplimentară de la execuţia pasului 3, pentru a uşura construcţia unei soluţii optimale.

Aplicatii

Cladire

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1). Determinați în câte moduri se poate ajunge din camera (1,1) în camera (n,m). Deoarece numărul de posibilități poate fi foarte mare, se cere doar restul acestui număr la împărțirea cu 9901.

#include<cstdio>

int a[1000][1000];

int main(){
  FILE*fin,*fout;
  int n,m,i,j;
  fin=fopen("cladire.in","r");
  fout=fopen("cladire.out","w");
 
  fscanf(fin,"%d%d",&n,&m);
 
  // in orice casuta de pe prima linie sau prima coloanea se poate ajunge doar intr-un mod
  for( i = 0; i < n; i++ )
    a[i][0] = 1; 
  for( i = 0; i < m; i++ )
   a[0][i] = 1;
 
  // intr-o casuta de coordonate i, j se poate ajunge 
  // fie prin casuta de coordonate i-1, j 
  // fie prin casuta de coordonate   i, j-1
  for( i = 1; i < n; i++ )
    for( j = 1; j < m; j++ )
        a[i][j] = ( a[i-1][j] + a[i][j-1] ) % 9901;
  
  fprintf( fout, "%d\n", a[n-1][m-1] );
 
  fclose(fin);
  fclose(fout);
 
  return 0;
}

Cladire1

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Unele camere sunt închise, accesul în ele fiind imposibil. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1), dacă aceasta nu este închisă.

Determinați în câte moduri se poate ajunge din camera (1,1) în camera (n,m). Deoarece numărul de posibilități poate fi foarte mare, se cere doar restul acestui număr la împărțirea cu 9901.

#include<cstdio>

int a[1001][1001];

int main(){
  int n, m, k, i, j, x, y;
  FILE *fin = fopen( "cladire1.in","r" );
  FILE *fout = fopen( "cladire1.out","w" );

  fscanf(fin,"%d%d%d", &n, &m, &k );

  for( i = 1; i <= k; i++ ){
    fscanf( fin, "%d%d", &x, &y );
    a[x][y] = -1;     // casuta inaccesibila
  }  

  // intr-o casuta de coordonate i, j se poate ajunge
  // fie prin casuta de coordonate i - 1, j
  // fie prin casuta de coordonate   i, j - 1
  a[0][1] = 1;
  for( i = 1; i <= n; i++ )
    for( j = 1; j <= m; j++ )
      if ( a[i][j] == -1 )
        a[i][j] = 0;        
      else
        a[i][j] = ( a[i-1][j] + a[i][j-1] ) % 9901;

  fprintf( fout, "%d\n", a[n][m] );

  fclose(fin);
  fclose(fout);

  return 0;
}

Tema

Trepte, Trepte2, Sumtri